0

私が書いたアルゴリズムが、グラフ内のすべてのノードを訪問するための最適なパスを返すかどうかを調べようとしています。芝生を刈ったり、掃除機で家を掃除したり、畑を耕したりするように、グラフをトラバースしようとしています。パスを取得しましたが、最適かどうかを確認する方法はありますか。それを確認するために使用できる API またはオンライン サービスはありますか?

Dijkstra と A* アルゴリズム、BFS と DFS を見てきましたが、取得したパスが最も効率的であることを検証する方法がわかりません。

与えられたグラフから、すべてのノードにアクセスする最も速くて効率的なパスを見つけるにはどうすればよいですか?

ありがとう

4

1 に答える 1

2

残念ながら、これは巡回セールスマン問題として知られる NP Hard 問題にあります。

したがって、既知の多項式時間解はありません。ソリューション スペース全体をトラバースするには、!N 回の反復が必要です (N はノードの数です)。ただし、最善ではないにしても、良い解決策を提供できる解決策がいくつかあります。

すべてのノード間の短いパスを取得する方法として、シミュレーテッド アニーリングを検討します。

http://en.wikipedia.org/wiki/Simulated_annealing

于 2013-08-24T22:00:08.980 に答える