C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[4]: パズルのアルゴリズムについて質問

(過去ログ 27 を表示中)

[トピック内 10 記事 (1 - 10 表示)]　 << 0 >>

■12503 / inTopicNo.1)

　パズルのアルゴリズムについて質問

▼■

□投稿者/ com (1回)-(2008/01/10(Thu) 18:05:49)

分類:[Java]　

授業でパズルを作るのですが、アルゴリズムが思いつかず悩んでいます
作り方、もしくは考え方を教えて頂けると幸いです
パズルの内容は
テキストデータからマップを読み込み、人、荷物、ゴールをマップに配置し
人が荷物を押して、ゴールまで運び、その荷物の移動距離を表示すると言うものです

要はドラクエの岩運びですね
例えば、マップは以下のように設定されます
０：床　１：人　２：荷物　３：ゴール

４４１４００
４４２４００
３０００００
０４０４００
０００４００

荷物が移動するだけのパズルならば、ゴールから荷物への最短ルートを探索しますが
人が後ろから押す制約のせいで随分と混乱しています
もっと単純な例ならば、人が押す制約があっても、ゴールから荷物への最短ルートを探し
逐一、荷物の最短ルートの１マス先に人が押すスペースがあるか、をチェックしていけば出来ると思います
しかし、少なくとも、この例ではゴールと荷物を結ぶ最短ルートを押していくことが不可能です
自分には、このような複雑な例でも荷物の動きを追うことが出来るアルゴリズムが思いつきませんでした

やはり、考え方を大きく変えなければ駄目でしょうか？

引用返信 編集キー/

■12504 / inTopicNo.2)

　Re[1]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ Hirotow (135回)-(2008/01/10(Thu) 18:12:45)

「倉庫番+アルゴリズム」で検索したら解説してあるサイトが幾つか見つかります。

引用返信 編集キー/

■12505 / inTopicNo.3)

　Re[1]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ Tom Yama (6回)-(2008/01/10(Thu) 18:15:29)

■No12503 (com さん) に返信
荷物を押していく「向き」は、どうやって変えるのですか？
荷物の周りを、人が移動するのですか？

引用返信 編集キー/

■12506 / inTopicNo.4)

　Re[2]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ com (3回)-(2008/01/10(Thu) 18:28:16)

■No12504 (Hirotow さん) に返信
> 「倉庫番+アルゴリズム」で検索したら解説してあるサイトが幾つか見つかります。
有難うございます。今から検索してみますね。

＞Tom Yama さん
荷物を押していく「向き」は、どうやって変えるのですか？
荷物の周りを、人が移動するのですか？

はい、人が単独で移動します

引用返信 編集キー/

■12507 / inTopicNo.5)

　Re[1]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ れい (362回)-(2008/01/10(Thu) 18:35:03)

■No12503 (com さん) に返信
> 授業でパズルを作るのですが、アルゴリズムが思いつかず悩んでいます

パズルを解くアルゴリズムでいいのでしょうか？

> ４４１４００
> ４４２４００
> ３０００００
> ０４０４００
> ０００４００

とりあえず私にはこのパズルが解けません…。
ゴールの上は歩けるのかしら？
画面外に出たらどうなるのかしら？

引用返信 編集キー/

■12515 / inTopicNo.6)

　Re[2]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ 凪瀬 (2回)-(2008/01/10(Thu) 21:47:10)

倉庫番か…。
授業でやるにしては難しすぎるかもしれませんね。

単純には可能手を総当たりで調べていき、嵌ったらNG、ゴールにたどり着けたらOKとするわけですが、
同一局面が繰り返し現れると無限ループになるので、同一局面を排除する工夫が必要です。

あとは、解ける見込みのない手順をどこで切り上げるが（ハッシュの枝刈り）が高速化のカギです。
このあたりに工夫を入れないと、現実的な時間で解いてくれないところが難しいですね。

引用返信 編集キー/

■12545 / inTopicNo.7)

　Re[2]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ y4yama (51回)-(2008/01/11(Fri) 14:10:58)

>>４４１４００
>>４４２４００
>>３０００００
>>０４０４００
>>０００４００
> とりあえず私にはこのパズルが解けません…。
これは、解なしの例だと、理解しました。

４４１４００
４４２４００
３０００００
０４０４００
００００００
これだったら、１つの解決ルートがあるということかと。（１の人は０床を手ぶらで行ったり回ったり戻ったりしますが・・）
３の下からはNGですよね。（直角の左下で１は下に行けないので押せない）・・でいいのかナ？

「倉庫番+アルゴリズム」をぐぐったら、10年以上前からコンテストがあるような「研究」なのですねぇ～
すごいです
目に付いたのは、デッドゾーンは計算できるから事前に除外するとか
ゴールから逆に引っ張って戻るロジックで優勝したソフトとか
総当り・・といっても凪瀬さんの言われているように大変そうで・・萎えました

引用返信 編集キー/

■12577 / inTopicNo.8)

　Re[3]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ れい (363回)-(2008/01/11(Fri) 19:43:43)

2008/01/11(Fri) 19:45:46 編集(投稿者)
2008/01/11(Fri) 19:44:43 編集(投稿者)

倉庫番なつかしいですねぇ。
苦労しました。いろいろ。

> 荷物が移動するだけのパズルならば、ゴールから荷物への最短ルートを探索しますが
> 人が後ろから押す制約のせいで随分と混乱しています

荷物が動くと考えるとだめでしょうねぇ。
人が動く、と考えると比較的楽です。

人は4方にしか歩けませんから、
自由に動けたとしても一歩あたり4つの場合しかないので、
各節から枝が4つ生えた木を作って探索すればよさそうです。

もし解があるなら、この木を幅優先探索すれば絶対に求まります。
最短手順がn歩だとすると、4^nの深さまで探索すればOK。
これでもう累乗のオーダーまでアルゴリズムを絞れました:D

ただ、全く同じ状態の節がありますので、無限に大きい木になっていて、
解が無いときは探索が終わりませんし、あまりにあほなので、次に枝狩りです。

同じ状態の節をびしばし枝狩りしてやると、
盤は有限ですから、かならず有限木になります。

あとは計算する前に要らないとわかる枝をいろいろ省いたり、
幅や深さで計算せずに、最もありそうなものから順に計算したり。

最終形から逆算すると空間計算量を最大半分にできますが
きちんと枝狩りできればあまり効果がないはずですね。
深さも変わらないし。

まぁいずれにせよ、高々でn^5ですから対したことないでしょう（嘘

引用返信 編集キー/

■12579 / inTopicNo.9)

　Re[3]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ Hirotow (136回)-(2008/01/11(Fri) 20:16:57)

遠まわしに壁の値が定義されていないという意味だと思います。
もし間違っていたらごめんなさい。
■No12545 (y4yama さん) に返信
> >>４４１４００
> >>４４２４００
> >>３０００００
> >>０４０４００
> >>０００４００
>>とりあえず私にはこのパズルが解けません…。
> これは、解なしの例だと、理解しました。

引用返信 編集キー/

■12841 / inTopicNo.10)

　Re[4]: パズルのアルゴリズムについて質問

▲▼■

□投稿者/ おきやす (1回)-(2008/01/18(Fri) 14:27:49)

検索してたら辿り着きました。（笑


本気でやったら死にそうになるので、簡易バージョンで良いのではないでしょうか？
・大きさ８ｘ８（外周含む）で、荷物を3個まで。
に制限すれば実用的なのが出来ると思いますよ。

○重複チェック
○田の地固めチェック
を実装すれば、秒以下で解けるのではないかと。


でもまぁ、今のPCの性能なら、大きさ32ｘ20でも人を超えるようなのが出来そうですけどねー。

引用返信 編集キー/

トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

- Child Tree -