経路探索について(3/3)

ちょっと考えてみました．この問題は，グラフ理論でよく知られている
「ハミルトン路問題」を，若干弱めたものになっていると思います．

・ロボットが取り得る位置を，無向グラフの節点とする．
・ロボットが位置Ａから，その隣の位置Ｂに移動可能 (壁がない) ならば，
　節点Ａと節点Ｂを辺で結ぶ．

「一筆書き」は「すべての辺を１回ずつ通る」という問題ですが，
「ハミルトン路問題」は「すべての節点を１回ずつ通る」という問題です．
だから今回の問題で「最大２回まで」という条件ではなく，「必ず１回」
であればハミルトン路問題になります．

ハミルトン路問題は，効率的なアルゴリズムが存在しない (NP完全) であることが
知られています．したがって制約のない一般のハミルトン路問題で，Ｎがある程度
大きい場合には実用的な時間内でプログラムが終了しなくなります．

今回の問題の場合は，１つの節点に接続する辺が最大４本しかないことを利用すれば，
効率的なプログラムが書けるかもしれません．あと，最適化をどこまで妥協するかも
ポイントでしょうね．

↓の26～27ページを参照
アルゴリズム設計 (9) グラフアルゴリズム (続き)
http://www.logos.t.u-tokyo.ac.jp/www/home/chik/algorithm-design/09%20Graph%20Algorithms.pdf

ハミルトン閉路問題をなぜ始めたか (ほか)
http://www.geocities.com/babalabo/HamiltonJ/DraftIndexJ.html

「+ハミルトン +グラフ +アルゴリズム」で Google 検索
http://www.google.co.jp/search?sourceid=navclient-ff&ie=UTF-8&rls=GGGL,GGGL:2006-34,GGGL:ja&q=%2B%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3+%2B%E3%82%B0%E3%83%A9%E3%83%95+%2B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

投稿日時 - 2006-12-31 17:32:39

> できればアドバイスお願いできないでしょうか？

面白そうなので考えてみるつもりです．(笑)
回答には何日か時間をいただくかもしれませんが…．

Ｎ×Ｎというサイズは当然，事前に与えられていると思いますが，壁の位置はどうでしょうか？
事前に (「掃除」＝移動を始める前に) 知らされているんでしょうか？
それとも移動しながら自分で調べないといけないんでしょうか？
市販のお掃除ロボットのようなものであれば，知らされていないわけですが．

どちらの場合かで，アルゴリズムは全然異なります．
事前に壁の位置がわかっていれば，移動を始める前にコンピュータ内で
シミュレーションして最適経路を求め，それに従って移動することができます．
そうでなければ，移動しながら壁の位置を見つけなければならず，
最適にはなりません (２回通らなければならないマスが増えてしまうかもしれません)．

それから，移動終了後の位置に関してリクエストはあるんでしょうか？
例えば，スタート位置に戻れ，とか．

投稿日時 - 2006-12-31 15:39:25

> お掃除をしてくれるロボットといったとことでしょうか。
> そのためにすべての空間をとおる必要があるのです。

> すべての空間を一回しかとおれない場合、または最大二回まで
> 通れる場合ですべてのマスを通れるかどうか調べたいのです。

ふーむ，「任意図形の塗りつぶし」と「一筆書き」を一緒にしたような
アルゴリズムになりそうですね．「一筆書きによる塗りつぶし」かな？

投稿日時 - 2006-12-31 01:00:40

No.1の方が仰るところの、マイクロマウス作ってます。
マイクロマウスで使われる迷路探索アルゴリズムの基本は、

http://www.informatics.tuad.ac.jp/tenji/tenji03/shiragami-lab/199970120/3.doc

の解説が秀逸。

マイクロマウスでないのでしたら、

> 広い空間があるのです。

空間はどのように定義しますか？
また、空間の広さの最大はどれくらい？
スタート地点とゴール地点（？）の与え方は？

> その空間をすべて通るかどうかを調べて表示したいのです。

全ての経路を網羅したかどうか確認したいということですか？
スタート地点からゴール地点までの最短経路が求まってしまうと、他の経路は通るだけ無駄ですよね。例えば袋小路とかは、行く意味が無い。

最短経路計画の定番は、数学的にはダイクストラ法とか、A*アルゴリズムとか。
http://research.nii.ac.jp/~uno/MP2/MP2_8shortestpath.ppt
これらは数学的に経路が最短であることを証明できます。

投稿日時 - 2006-12-30 04:57:27

マイクロマウスの話でしょうか？


> 迷路の探索のようなものなのですが、

道は一方通行 (有向グラフ) でしょうか，双方向 (無向グラフ) でしょうか？
普通の迷路探索であれば後者だと思いますが．


> その空間をすべて通るかどうかを調べて表示したいのです。

意味がよくわからないのですが，これは出発点とゴールが指定されていて，
それを結ぶ (１つの) 経路を見つけたいということでしょうか？


> 普通の迷路だったら左手法とかでいけるのだと思うのですが、
> 同じようにやってもうまくいかなくて。。。

合流点またはループがあるということですね？
だとしたら左手法 (右手法) は無限ループします．


ご質問の問題は，典型的な (無向または有向) グラフの深さ優先探索
(縦型探索ともいう) で解決できますが，マイクロマウスであれば色々な
探索法があるようですので，とりあえず↓

迷路を脱出する経路探索プログラムをＣ言語で作成するには？
http://oshiete1.goo.ne.jp/kotaeru.php3?qid=1553632

「+"左手法" +"迷路"」で Google 検索 (関連する探索法もあります．)
http://www.google.co.jp/search?q=%2B%22%E5%B7%A6%E6%89%8B%E6%B3%95%22+%2B%22%E8%BF%B7%E8%B7%AF%22&hl=ja&lr=&rls=GGGL,GGGL:2006-34,GGGL:ja&start=10&sa=N

投稿日時 - 2006-12-30 03:08:22