経路探索

質問

よろしくお願いします。
現在経路探索問題のプログラムを書いています。
そこでわからない点があったので教えてください。

以下のような(n行,m列)の経路があります。

(0,0)－(0,1)－(0,2)－(0,3)
(1,0)－(1,1)－(1,2)－(1,3)
(2,0)－(2,1)－(2,2)－(2,3)
(3,0)－(3,1)－(3,2)－(3,3)
(4,0)－(4,1)－(4,2)－(4,3)

スタートを(4,3)としてゴール(0,0)にたどり着く全ての経路を求めたいです。

条件としてある点から
左(例えば(4,3)⇒(4,2))
上(例えば(4,3)⇒(3,3))
斜め(例えば(4,3)⇒(3,2))
にしか進むことはできません。

このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？
ご解答要路しくお願いします。

回答No.2

PED02744 · ベストアンサー

「アルゴリズムを考えること」そのものが勉強なのだと思いますので、
答えになるような事は控えたいと思いますが・・・といいながら、考えてみたけども(笑)

(1)左に移動できるというのはどういうことか？→mが -1できるということ。0未満なったら移動できないとみなす。

(2)上に移動できるというのはどういうことか？→nが -1できるということ。0未満なったら移動できないとみなす。

(3)斜め(多分左上だけですよね)に移動できるというのはどういうことか？→mが-1, nが-1できるということ。mかnのどちらか一方が0未満になったら移動できないとみなす。

ここまでは前提条件だから、そのままですね？
答えの求める内容を数学的に書くと
x(1) = [4,3]として
x(2) = f(x(1))
x(3) = f(x(2))
: :
x(n) = f(x(n-1))
となる時、解が[0,0]となるものを全てあげるということです。
そして、f(x)のf()は(1)～(3)の前提条件の事ですから、、、、
ほら、もうわかったでしょ(笑)

回答No.1

noname#39970

では人がそれを繰り返す場合　どう考えるか箇条書きにしてみよう

質問文にある条件の他に　「書かれていないがじつはこれも条件」　というのがあるのでプログラムやアルゴリズムではそれも必要になる

で、ヒトツの経路探索を達成してる間に次の候補というのを頭の中で立てるか分岐用に「分岐候補」をメモすると思う。
それも箇条書き。(●●の場合分岐候補を記録　とか)

基本はそれらを組み合わせて繰り返す事になるけれど、できあがった物は少し複雑かもしれない。
動けば良いって事だろうけど最適化するかどうかは組む人次第。