【what is this】マイクロビット（micro:bit）のプログラミング例題として、有向グラフのハミルトン閉路問題をやってみました。これは（NP完全問題）であり、効率的な解法は無いようです。そこで、全パス検索になるのですが、DNA（分子生物学の）を使って試験管のなかでこの問題を解いたAdelmanに習い、解の候補となる経路を事前に生成して、それをふるいにかける方式としました。この例題作成をとおして、micro:bitのプログラミングシステムが非常に優れていることを再確認しました。
（⇒本記事の続編はこちらにあります。）
■micro:bitでの有向グラフのハミルトン閉路問題
micro:bitは最近Version2が発表され、メモリの増強（RAM 8倍化、Flash 2倍化）、タッチセンサやマイク、スピーカーの内蔵などがなされています。今回、これを記念して？ハミルトン閉路問題（始点ノードから出発して、全てのノードを１度だけ訪問し、始点へ戻る経路を探索）を解いてみます。高校生向け講座などの例題になるかも知れません。
問題設定ですが、micro:bitには、5x5のLED表示しかありませんので、5ノードの有向グラフに限定します。図１のように、ボタンAを押してランダムに５ノード間の接続行列を作るようにします。
次にボタンBを押すとその解を探索し、見つかった解の個数を表示します。解がなければ0個となります。さらにタッチセンサに触れると、解を電光掲示板方式で１文字づつ流して表示します。これだけですが、ちょっと楽しいプログラミングとなるはずです。
この解法は、全パス検索になります。ただし、AdelmanのDNAを利用した（試験管のなかでの）解法を念頭におき、事前に解の候補をすべて生成します。すなわち、ノード1, 2, 3, 4の順列（4! = 24個しかありませんが）を生成し、その先頭と末尾に0を付加した経路シーケンスが、上で生成した接続行列から作れるかを検査します。出題となる接続行列の個数は約100万個（= 2の20乗）あるのですが、そのいずれに対しても24個の可能性を調べれば良いことになります。ランダムに生成した接続行列では、解が存在しない場合も多く、解があっても、数個程度以内となります。
■micro:bitプログラミング
この解法のプログラムの主要部を図３に示します。ブロック形式、μPython、JavaScriptの3種が利用できます。ここで特筆すべきは、大まかには最初にブロック形式で作成して、細部をμPythonで作ることができることです。図ではmakePathという関数を作っているのですが、再帰的構造になり、ブロック形式で作成していると細部が考えにくい状況になりました。そこで、μPythonに切り替えて作成するとかなり楽でした。そして、その後、再度ブロック形式に戻ることができるのです！
さらに素晴らしいと思ったのは、実機のmicro:bitでやる前に、PCでエディタやシュミレータを使えることです。それには、デバッガーやコンソールも使えるという優れた開発環境になっているのです。
この解法のプログラムの主要部を図３に示します。ブロック形式、μPython、JavaScriptの3種が利用できます。ここで特筆すべきは、大まかには最初にブロック形式で作成して、細部をμPythonで作ることができることです。図ではmakePathという関数を作っているのですが、再帰的構造になり、ブロック形式で作成していると細部が考えにくい状況になりました。そこで、μPythonに切り替えて作成するとかなり楽でした。そして、その後、再度ブロック形式に戻ることができるのです！
さらに素晴らしいと思ったのは、実機のmicro:bitでやる前に、PCでエディタやシュミレータを使えることです。それには、デバッガーやコンソールも使えるという優れた開発環境になっているのです。
micro:bitは、通常、小中高生のプログラミング教育などに広く利用されています。大学ではあまり関心は高くないようです。ですが、上記の経験からも、これは大学でも、初級プログラミングにはかなり使えのではないかと思った次第です。
micro:bit単体では、確かに作れるアプリに限界があります。しかし、他の機器やスマホとの連動機能も豊富なので、それを使うとかなり高度なアプリも楽しく作れると思います。
ちょっと手前味噌になりますが、小生がこれまでに、micro:bitと他の機器などと連携させて作成したアプリの情報は以下にあります。ご参考になれば幸いです。
- Demonstrating Block Chain with a set of micro:bits using radio
- BBCのmicro:bitで暗号仮想通貨の基礎を知る
- Consturuct a neural network (multilayer perceptrons) using micro:bit
- BackPropagation in Neural Network with an Example (XOR) Using Multiple Micro:bits
- Cooperation between micro:bit and MIT App Inventor with Eddystone signals (No.1)
- Cooperation between micro:bit and MIT App Inventor with Eddystone signals (No.2)
- Cooperation between micro:bit and MIT App Inventor (No.3)
⇒本記事の続編はこちらにあります。
