明らかに以下は宿題の問題です。教授の言っていることが理解できないので、この質問の答えを見つけるために必要な情報をどこから探し始めるかさえ知る必要はありません。このようなことについてどこで学ぶべきか、そしてこの問題を解決するためにどのように取り組むことができるかについて、私にいくつかの手がかりを与えることができれば、私は感謝するでしょう。
次のグラフで、2つのノード間の最短経路を見つけます-選択しますが、問題を興味深いものにします。
これは連結グラフですか？
質問する
402 次
2 に答える
1
スターアルゴリズムを使用して、2つのノード間の最短パスを見つける必要があります。 http://en.wikipedia.org/wiki/A_star
メンガーの定理http://en.wikipedia.org/wiki/Menger%27s_theoremを使用して接続しているかどうかを確認できます
于 2013-03-04T19:50:10.477 に答える
1
グラフがメモリ内でどのように表されるかを最初に知っておくことが望ましいでしょう。自分次第の場合は、2次元配列を使用できます。これは、重み付きエッジを表す最も簡単な方法です。
最短経路アルゴリズムを実装するのに最も簡単なのは、おそらくダイクストラ法です。これは、A *よりも少し遅いですが、それほど複雑ではありません。Djikastraを使用するには、最初に優先キューを実装する必要があります。JavaにはPriorityQueueクラスがあります。そうでない場合は、自分で実装する必要があります。その後、ウィキペディアやその他の場所で入手できる擬似コードを使用して、実装をかなり簡単にする必要があります。
于 2013-03-04T20:29:27.627 に答える