プログラミング例題（ハミルトン閉路問題）：Android版+RNN学習

   【what is this】小規模（５ノード）の有向ハミルトン閉路問題を、前回はマイクロビット（micro:bit）単体で解きました。今回は、それをAndroidスマホで実現しました。MIT App Inventorを用いて、チェックボックスによる接続指定や矢印付きグラフの描画も含めて見やくしました。さらに、Deep Learning（RNN(LSTM)）を用いて、グラフとそのハミルトン閉路の個数の対を、多数学習させる実験も行いました。

■MIT App Inventorを用いたハミルトン閉路解法アプリ
　micro:bit単体では、出力表示が5x5のLEDに限られますが、Androidスマホを使えば、入出力とも、大幅に改善できます。また、この解法は全パス検索となるのですが、具体的なその方法は（順列生成を含めて）、それほど自明ではありません。ですから、スマホでこの解法アプリを設計製作することは、高校〜大学初級におけるプログラミング題材の候補になるはずです。小生のアイディアを以下にご紹介します。
　例えば、以下のような４ノードの有向ハミルトン経路を調べるとします。（目視ですぐに分かるのですが）

　図１(a)のようにして、このアプリで解くことができます。4x4のチェックボックスにチェックを入れることで、ノード間の有向接続を指定します。ボタン"genGraph"によって、それを矢印付きのグラフで表示します。そして、ボタン"solve"を押すと、解が得られます。この例では、解は存在しませんでしたが。

　では次に、ノード数を６に設定して、別のグラフでやってみます。図１(b)の通りです。この例では解は２つ見つかりました。そのうちの一つについては、グラフ上に赤い矢印を付してその経路を明示しています。

■ディープラーニングでハミルトン閉路の個数を学習させる
　次にやってみたのは、「ディープラーニングでハミルトン閉路の個数を発見させる」試みです。５ノードの場合でも、それから作られる有向グラフは、約100万個になります。そのうちの、20万個をランダムに選択します。その各グラフ（接続情報）に対して、上記のような方法で求めたハミルトン閉路の個数をラベルとして付与し、学習させました。図２がその場合の学習データです。

　この学習データをある構造のRNN(LSTM)で学習させた結果を図３に示します。20万件のうち、18万件を学習（訓練）データに、2万件をテストデータとした場合の、テストデータの正解率は、50エポックで99.75%に達しました！
　すなわち、「５ノードのどんな有向グラフを与えても99.7％程度の確率でハミルトン閉路の個数を正答する」ように学習できた、と言えるでしょう。

（注）この学習は、スマホではなく、PCで行いました。