- 締切済み
任意の2地点間の全経路探索について
secretdの回答
- secretd
- ベストアンサー率39% (50/126)
あまり詳しいわけではないですが． ダイクストラアルゴリズムで問題になるネットワークには大概閉路があったりするわけですが，そこの辺りはどのように考えていらっしゃるのでしょう．閉路をぐるぐる回ったら，コストは無限大になりますよね． そうではなく，一筆書きみたいなものを考えるんだったら，巡回セールスマン問題みたいな考え方をすればいいんじゃないのでしょうか．
関連するQ&A
- ベルマンフォードのアルゴリズム
このカテゴリーであってる・・・かな・・。 とりあえず、ネットワークのアルゴリズムなので。 最短経路を求めるアルゴリズムは、 ダイクストラしか知らなかったのですが、 ベルマンフォードというアルゴリズムがあると知りました。 どのようなアルゴリズムなのでしょうか？ ダイクストラと比較してどうなのでしょうか？
- ベストアンサー
- その他（インターネット接続・通信）
- 最短経路問題のアルゴリズム
最短経路問題のアルゴリズムにはどのようなものがありますか？ ダイクストラくらいしか知りません。教えてください。 カテゴリー違いだったら書き直します。
- ベストアンサー
- 数学・算数
- 最長経路探索
グラフの最長経路(クリティカルパス)を求めたいのですが、 ・閉路無し有向グラフ ・重み付きグラフ（辺ではなくノードの方に重みがある） ・スタートとゴールのノードが各々1つ与えられている ・スタートからどの経路を辿ってもゴールには辿り着く 以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか？ 幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。 言語はVBAで、そもそも詳しくないのですが、 考え方など教えて頂けないでしょうか。 お願い致します。
- ベストアンサー
- その他（プログラミング・開発）
- 経路探索
よろしくお願いします。 現在経路探索問題のプログラムを書いています。 そこでわからない点があったので教えてください。 以下のような(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)) にしか進むことはできません。 このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？ ご解答要路しくお願いします。
- ベストアンサー
- C・C++・C#
- ルーティングプロトコルの実装
アドホックネットワークのルーティングプロトコルのプログラムをCで作成し、 ダイクストラの経路選択法を用いてサーバまでの最短経路を求めています。 ／[端末A]－・・＼ [サーバ] [クライアント] ＼[端末B]－・・／ 最短経路以外の予備経路も保持したいのですが、ダイクストラ法では 最短経路しか保持しないので困っています。第一経路＋第二経路 を作りたいのですが・・ よい案がないか、どなたかご指南いただけないでしょうか。
- ベストアンサー
- C・C++・C#
- 最短距離を求める問題（ダイクストラ法）の原理
グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。
- 締切済み
- C・C++・C#
- 最短経路表示の追加プログラム
下のリンク先のプログラムはダイクストラを用いた最短”距離”を求めるプログラム何ですが、このプログラムに最短距離の最短”経路”を表示する追加のプログラムを求めているんでけど、よろしければお答えしてもらえませんか？http://www.nda.ac.jp/~yamada/programs/programs.html
- 締切済み
- C・C++・C#
- 最短経路のアルゴリズム
このジャンルでお願いします。 左下の座標を(1,1)として ○(4,4)が△(7,2)に辿りつく最短経路のアルゴリズムが知りたいです。 ■は通れない場所です。 □□□□□□□ □□■■□□□ □□□□■□□ □■□○■□□ □■□■■□□ □□■□□△□ □□□□□□□ ↑ (1,1)
- ベストアンサー
- C・C++・C#