迷路の表わしかたには、どういうものがあるでしょうか？ 『マイコンとパズルの世界　BASICプログラミング頭の体操』から拝借してですが、このような迷路があったとします:

 

この迷路をコンピュータに解かせるには、どうにかしてこの迷路をコンピュータの中に再現してやる必要があります。どのように再現すればいいでしょうか？

一つには、次のようなかなり直接的な方法があります:
＃＃＃＃＃＃＃＃　＃
＃　　　＃　　　　＃
＃　＃＃＃＃　＃＃＃
＃　　　＃　　＃　＃
＃　＃　＃＃　＃　＃
＃　＃　　　　　　＃
＃　＃＃＃＃＃＃＃＃

壁を “＃” で、通路を “　” で書いたものです。これは、 “＃” と “　” ではなくてもよくて、数値として “1” と “0” でもかまいません。いずれの場合でも、2次元の配列で迷路を表わしています。この場合、探索して行き止まりだったというような部分には、 “Ｘ” とか “2” とか、迷路を描くのに使っていない記号や値を入れてやると、その箇所を再度探索するというような無駄が、直接的に省けます。

では、これ以外の方法はなにかあるでしょうか？ 入口、分岐点、行き止まり、出口に、次のように番号を付けたとしましょう:
＃＃＃＃＃＃＃＃⑩＃
＃　　③＃⑨⑧　　＃
＃　＃＃＃＃　＃＃＃
＃　②　＃⑦⑥＃⑤＃
＃　＃　＃＃　＃　＃
＃　＃　　　④　　＃
＃①＃＃＃＃＃＃＃＃

この番号を、迷路を再現するように繋げてみると、次のようになります:

なんか手抜き風のグラフになりましたが。このようにグラフとして現わすことも可能です。この図では矢印を使っていますが、迷路を行きつ戻りつするだろうことを考えると、矢印ではなくただのリンクにするか、あるいは矢印でもノード間に双方向の矢印として書いてもかまわないでしょう。

元の迷路の図とグラフではまったく見た目が違うと思われるかもしれません。ですが、先に上げた、入口、分岐点、行き止まり、出口に注目すると、同じであることがわかるかと思います。

また、このグラフだと入口から出口までが一直線になっていますが、それは私の手抜きによるものです。グラフで現したとしても、探索が必要なことに変わりはありません。

もっとも「ガジェット・コンピューティング」に挙げたスキャン画像の方に含まれる、紐を使ったものとしてグラフを表現するとします。すると、入口に対応する結びめを持って垂らしてやると、長さはともかく、出口が下のどれかに来ているはずです。ノードを結びめで現わしてやっていれば、入口から出口までにある結びめ、およびそれが対応するノードを読んでやれば、それで入口から出口までの経路もわかります。

あるいは、書き方をすこし変えてやると、いびつではありますが、次のように木構造でもあります:

このように、データの表しかたにはいくつか(あるいは、いくつも)方法がありますし、どのデータ構造を採用するかで、問題の解き易さも変わってきます。そのあたりを考えるのも、プログラミングの楽しさであり、難しさでもあるかと思います。

なお、最初に「この迷路をコンピュータに解かせるには、どうにかしてこの迷路をコンピュータの中に再現してやる必要があります」と書きましたが、これはロボットを使う場合でも同じで、探索した経路をロボットに、あるいはロボットが繋がっているコンピュータに記録させてやる必要があります。それをやらないと、同じ行き止まりに何回も行くというようなことが起こりますので。それを避けるためには、ロボットを使う場合でも、やはりどういう形にしろ迷路を再現してやる必要があります。

興味を持たれましたら、ぜひご支援や、コメントをお願いいたします。

プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。

また、私個人についてはこちらをご覧ください。