![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
A 回答 (15件中11~15件)
- 最新から表示
- 回答順に表示
No.5
- 回答日時:
ちょっと考えてみました.この問題は,グラフ理論でよく知られている
「ハミルトン路問題」を,若干弱めたものになっていると思います.
・ロボットが取り得る位置を,無向グラフの節点とする.
・ロボットが位置Aから,その隣の位置Bに移動可能 (壁がない) ならば,
節点Aと節点Bを辺で結ぶ.
「一筆書き」は「すべての辺を1回ずつ通る」という問題ですが,
「ハミルトン路問題」は「すべての節点を1回ずつ通る」という問題です.
だから今回の問題で「最大2回まで」という条件ではなく,「必ず1回」
であればハミルトン路問題になります.
ハミルトン路問題は,効率的なアルゴリズムが存在しない (NP完全) であることが
知られています.したがって制約のない一般のハミルトン路問題で,Nがある程度
大きい場合には実用的な時間内でプログラムが終了しなくなります.
今回の問題の場合は,1つの節点に接続する辺が最大4本しかないことを利用すれば,
効率的なプログラムが書けるかもしれません.あと,最適化をどこまで妥協するかも
ポイントでしょうね.
↓の26~27ページを参照
アルゴリズム設計 (9) グラフアルゴリズム (続き)
http://www.logos.t.u-tokyo.ac.jp/www/home/chik/a …
ハミルトン閉路問題をなぜ始めたか (ほか)
http://www.geocities.com/babalabo/HamiltonJ/Draf …
「+ハミルトン +グラフ +アルゴリズム」で Google 検索
http://www.google.co.jp/search?sourceid=navclien …
No.4
- 回答日時:
> できればアドバイスお願いできないでしょうか?
面白そうなので考えてみるつもりです.(笑)
回答には何日か時間をいただくかもしれませんが….
N×Nというサイズは当然,事前に与えられていると思いますが,壁の位置はどうでしょうか?
事前に (「掃除」=移動を始める前に) 知らされているんでしょうか?
それとも移動しながら自分で調べないといけないんでしょうか?
市販のお掃除ロボットのようなものであれば,知らされていないわけですが.
どちらの場合かで,アルゴリズムは全然異なります.
事前に壁の位置がわかっていれば,移動を始める前にコンピュータ内で
シミュレーションして最適経路を求め,それに従って移動することができます.
そうでなければ,移動しながら壁の位置を見つけなければならず,
最適にはなりません (2回通らなければならないマスが増えてしまうかもしれません).
それから,移動終了後の位置に関してリクエストはあるんでしょうか?
例えば,スタート位置に戻れ,とか.
この回答への補足
ありがとうございます。
壁の位置は事前に与えられています。移動終了後の位置に指定はありません。ただすべての空間をとおり、その通った順を表示したいのです。ちなみにC言語でやっています。
No.3
- 回答日時:
> お掃除をしてくれるロボットといったとことでしょうか。
> そのためにすべての空間をとおる必要があるのです。
> すべての空間を一回しかとおれない場合、または最大二回まで
> 通れる場合ですべてのマスを通れるかどうか調べたいのです。
ふーむ,「任意図形の塗りつぶし」と「一筆書き」を一緒にしたような
アルゴリズムになりそうですね.「一筆書きによる塗りつぶし」かな?
No.2
- 回答日時:
No.1の方が仰るところの、マイクロマウス作ってます。
マイクロマウスで使われる迷路探索アルゴリズムの基本は、
http://www.informatics.tuad.ac.jp/tenji/tenji03/ …
の解説が秀逸。
マイクロマウスでないのでしたら、
> 広い空間があるのです。
空間はどのように定義しますか?
また、空間の広さの最大はどれくらい?
スタート地点とゴール地点(?)の与え方は?
> その空間をすべて通るかどうかを調べて表示したいのです。
全ての経路を網羅したかどうか確認したいということですか?
スタート地点からゴール地点までの最短経路が求まってしまうと、他の経路は通るだけ無駄ですよね。例えば袋小路とかは、行く意味が無い。
最短経路計画の定番は、数学的にはダイクストラ法とか、A*アルゴリズムとか。
http://research.nii.ac.jp/~uno/MP2/MP2_8shortest …
これらは数学的に経路が最短であることを証明できます。
この回答への補足
自分のコトバ足らずだったようですいません…マイクロマウスとはまた違うんです。。。迷路という言葉を使った自分が悪いですね。あえて言うならば、お掃除をしてくれるロボットといったとことでしょうか。そのためにすべての空間をとおる必要があるのです。
すべての空間および壁は、二次元配列でN×Nますのフロアとして定義しています。その中に壁を設定します。つまりスタートとゴールがあるというよりは、すべての空間を一回しかとおれない場合、または最大二回まで通れる場合ですべてのマスを通れるかどうか調べたいのです。ただスタートは一番左上のマスからです。
No.1
- 回答日時:
マイクロマウスの話でしょうか?
> 迷路の探索のようなものなのですが、
道は一方通行 (有向グラフ) でしょうか,双方向 (無向グラフ) でしょうか?
普通の迷路探索であれば後者だと思いますが.
> その空間をすべて通るかどうかを調べて表示したいのです。
意味がよくわからないのですが,これは出発点とゴールが指定されていて,
それを結ぶ (1つの) 経路を見つけたいということでしょうか?
> 普通の迷路だったら左手法とかでいけるのだと思うのですが、
> 同じようにやってもうまくいかなくて。。。
合流点またはループがあるということですね?
だとしたら左手法 (右手法) は無限ループします.
ご質問の問題は,典型的な (無向または有向) グラフの深さ優先探索
(縦型探索ともいう) で解決できますが,マイクロマウスであれば色々な
探索法があるようですので,とりあえず↓
迷路を脱出する経路探索プログラムをC言語で作成するには?
http://oshiete1.goo.ne.jp/kotaeru.php3?qid=1553632
「+"左手法" +"迷路"」で Google 検索 (関連する探索法もあります.)
http://www.google.co.jp/search?q=%2B%22%E5%B7%A6 …
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 飛行機・空港 羽田空港で京浜急行に乗り換えに必要な時間があるか心配しています。 ロスから関西空港経由(JAL069 5 2023/03/07 10:54
- その他(法律) 路側帯に駐車したら駄目って本当? 5 2022/05/26 13:32
- 運転免許・教習所 車の右折先が渋滞している場合 10 2023/07/29 10:08
- Excel(エクセル) エクセル 行番号を自動で振るには 3 2022/08/08 20:19
- その他(法律) 2車線以上であっても、歩行者は横断歩道がない道路を横断できますよね? 3 2022/04/19 15:58
- その他(法律) 自動車の点灯義務について 6 2023/02/24 15:01
- HTML・CSS Chrome のキャッシュについて 3 2022/05/26 07:50
- その他(交通機関・地図) 高速道路の料金の調べ方 1 2023/06/19 20:02
- その他(車) 煽り運転の定義 10 2022/09/26 06:47
- 伝統文化・伝統行事 祭りの神輿バトルで公道を占拠、どう思うか 8 2022/11/04 18:17
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
OpenCVのライセンスについて
-
期間重複チェックがわかりません
-
ハードディスクの完全消去方式...
-
アルゴリズムとプロトコールの違い
-
BCDについて
-
[ EXCEL VBA ] 図形を読み込む...
-
ドロネー三角形のプログラム
-
gooという検索エンジンの後にGo...
-
退化木をバランス木にしたい
-
巡回セールスマン問題
-
多変数関数の最小値を求めるプ...
-
CRC-CCITT16の算出法
-
パソコン
-
65536は2の何乗なのでしょうか?
-
Excelで4096点以上のFFTの方法
-
VBAで仕様書は書きますか?
-
VBAで関数をつくる
-
あるプログラムのコマンドライ...
-
0除算して、落ちるプログラムと...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
アルゴリズムとプロトコールの違い
-
BCDについて
-
[ EXCEL VBA ] 図形を読み込む...
-
Stuck
-
グループを均等に分けるには?...
-
画像から文字を認識してテキス...
-
Dijkstraて
-
期間重複チェックがわかりません
-
JPEG圧縮で8×8に分割する理由に...
-
多変数関数の最小値を求めるプ...
-
OpenCVのライセンスについて
-
データを圧縮したい
-
ルービックキューブを揃えるた...
-
5人のテストの点数を入力すると...
-
C♯で電卓を作成しています。演...
-
ドロネー三角形のプログラム
-
vbaで、連立方程式を解く方法に...
-
動画で間違ったこと言っている
-
トップダウン解析とボトムアッ...
おすすめ情報