• ベストアンサー

経路探索

よろしくお願いします。 現在経路探索問題のプログラムを書いています。 そこでわからない点があったので教えてください。 以下のような(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)) にしか進むことはできません。 このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？ ご解答要路しくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • PED02744
  • ベストアンサー率40% (157/390)
回答No.2

「アルゴリズムを考えること」そのものが勉強なのだと思いますので、 答えになるような事は控えたいと思いますが・・・といいながら、考えてみたけども(笑) (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)の前提条件の事ですから、、、、 ほら、もうわかったでしょ(笑)

その他の回答 (1)

noname#39970
noname#39970
回答No.1

では人がそれを繰り返す場合　どう考えるか箇条書きにしてみよう 質問文にある条件の他に　「書かれていないがじつはこれも条件」　というのがあるのでプログラムやアルゴリズムではそれも必要になる で、ヒトツの経路探索を達成してる間に次の候補というのを頭の中で立てるか分岐用に「分岐候補」をメモすると思う。 それも箇条書き。(●●の場合分岐候補を記録　とか) 基本はそれらを組み合わせて繰り返す事になるけれど、できあがった物は少し複雑かもしれない。 動けば良いって事だろうけど最適化するかどうかは組む人次第。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 最長経路探索

    グラフの最長経路(クリティカルパス)を求めたいのですが、 ・閉路無し有向グラフ ・重み付きグラフ（辺ではなくノードの方に重みがある） ・スタートとゴールのノードが各々1つ与えられている ・スタートからどの経路を辿ってもゴールには辿り着く 以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか？ 幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。 言語はVBAで、そもそも詳しくないのですが、 考え方など教えて頂けないでしょうか。 お願い致します。

  • 最短経路を計算するプログラム

    下の図のようなものを用いて、スタート（S）からゴール（G）までいく最短経路を計算するプログラムをVisual Studio 2005のC++で作ったアルゴリズムが知りたいです。

  • 文字列の探索アルゴリズムについて

    松井勝正といいます。自分なりのアイディアで文字列の探索アルゴリズム を作成したのですが。質問が2点程あります。 1点目：既に世に出回っているアルゴリズムかご教授願えれば幸いです。 2点目：改良の余地やバグ等ございましたらご指摘いただければ幸いです。 それではよろしくお願いいたします。

  • 最短距離を求める問題（ダイクストラ法）の原理

    グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。

  • 巡回セールスマン問題の考え方を使って・・・。

    以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 　 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき 　ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。

  • LISPによる横型探索

    LISPのSchemeをつかって横型探索で探索した経路を出力するプログラムをつくっているのですが、 今は探索が終わると終了するとCLOSEDの中を表示するプログラムしかできていません もしこれに探索した経路の出力をする機能を加える場合どうすればいいですか？ OPEN→待ちリスト CLOSED→展開済みリスト GOAL→目標地点 OP→オペレータの集まり nとopから展開の結果をだす (define (tenkai n op) (tenkai2 n op '())) (define (tenkai2 n op kekka) (if (null? op) kekka (if (= n (car (car op))) (tenkai2 n (cdr op) (cons (car (cdr (car op))) kekka)) (tenkai2 n (cdr op) kekka)))) (define (yokogata open goal op closed) (if (null? open) 'sippai (if (= (car open) goal) (display closed) (yokogata (append (cdr open) (tenkai (car open) op)) goal op (append closed (list (car open)))))))

  • 巡回セールスマン問題を使って・・・

    以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 　 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき 　ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。 文字数の関係で、プログラムをのせれないのでお答えになってくださったときにお礼の場でプログラムをお見せすることができます。

  • ある行が探索できない

    すいませんが、前回同じような質問をしましたが、再度質問します。文字列の探索で、 printf("Input Filename..."); scanf("%s",fname); while(1){ fp = fopen(fname, "r"); if(fp == NULL){ printf("ファイルを開くことができません...\n"); printf("Input Filename..."); scanf("%s",fname); }else break; } // fscanf(fp,"%s",fname); //1行目以外のみ可能 // fread(s1, 1000, 1000, fp); //上記 // s1 = fgetc(fp); fgets(s1, 10000, fp); //1行目のみ可能 // s1 = fscanf(fp); // s1=fp; // printf("文字列1を入力してください："); // scanf("%s",s1); printf("文字列2を入力してください："); scanf("%s",s2); cp = strstr(s1, s2); if(cp == NULL) printf("%sに%sのいずれの文字も含まれない.\n", s1, s2); else printf("%sの中に現れる%sという文字列は%d文字目にある.\n", s1, s2, cp - s1 + 1); free(s1); free(s2); というプログラムを作ったのですが、仮に3行のテキストファイルを読み込ませると、コメントの通り、 fscanf(fp,"%s",fname); //1行目以外のみ可能 fread(s1, 1000, 1000, fp); //上記 とすると、2,3行目のみが探索出来て、 fgets(s1, 10000, fp); //1行目のみ可能 とすると、1行目のみが探索可能になっています。 すべての行を探索可能にするにはどうすれば良いか教えてください。

  • 準ニュートン法の直線探索と収束性

    　プログラムとして直線探索を実装した準ニュートン法を作成しました。 これについて、2次関数で試行すると、ヘッセ行列の逆は理論値の[0.5 0; 0 0.5]に収束することが確認できました。 　他方で、直線探索を外し、一定値の間隔で進む？ようにしますと、逆行列の理論値から外れた値に収束することが見受けられました（探索点は2次関数の最小値に収束します）。 これは、プログラムミスなのか、準ニュートン法で直線探索をしないことによる帰結なのか、どちらなのでしょうか？また、後者であれば、その理由は数学的に明らかにされているのでしょうか？

  • 巡回セールスマン問題を使って・・・

    すいません。数学に関してまったくの素人です。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 「対象地に12の交差点があって １．この交差点全てを最短経路でまわりたい。（スタートとゴールがいっしょ。） ２．交差点全てを最短経路で通過したい。（スタートとゴールはちがう） ということをやるようになってます。 １．に関しては巡回セールスマン問題の分岐限定法でパズル的にとけばいいのでしょうか？ ２．に関してはまったくわかりません。そもそもどのようにスタートとゴールを設定すればいいのか・・・ また上記のような場合に適応できるプログラムは出回っているのでしょうか？もしくは自分で作れるものなのでしょうか？プログラムに関してもまったく素人です。 このように質問ばかりですいません。書いてあることでわからないことがあれば、言ってください。わかるかたご教授ください。お願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する