1

問題はこれです：

グラフG=（V、E）があります。頂点U<=Vのサブグループ、および開始頂点s。エッジの重み関数w。

Uのすべての頂点を通過する「s」からの最短経路を見つける必要があります。

  • 計算は概算できます。計算時間とパスの長さの間にはある程度のバランスが必要です。最短経路の細かい近似を生成する高速アルゴリズム/ヒューリスティックが必要です。
  • このアルゴリズムは、（C ++で）実装するのにそれほど複雑であってはなりません。たとえば、これを巡回セールスマン問題にし、TSPソルバーライブラリなど、ある種のヒューリスティックを使用するものを使用する方法をすでに考えましたが、何も見つかりませんでした。ヒューリスティックを自分で実装することもできます。難しい。

よろしくお願いします！=]

4

2 に答える 2

3

これは、SetTSP問題またはGeneralizedTSPと呼ばれる巡回セールスマン問題の変形です。これがウィキペディアのリンクです。

上記の記事からの参照は、グラフ内のノード数を2倍にすることなく一般化TSP問題をTSP問題に変換する方法にリンクしています。

記録保持TSPソルバーは無料で入手でき、Concordeと呼ばれ、ここからダウンロードできます。コマンドラインツールとして実行できます（ライブラリとして実行できるかどうかはわかりません）。

最小限のボタンを押すだけで各レベルのすべてのお金を獲得することで、ゲームRevolvoMan4kのソルバーを作成しようとしたときに、GTSPに出くわしました。（これは楽しいゲームですが、レベル50以降はレベルがランダムになるため、不可能なものもあり、「N」でスキップする必要があります）。

于 2012-08-23T03:37:21.440 に答える
0

S、A、B の 3 つの頂点があるとします。ここで、S から A と B を通る最短経路を見つける必要があるとします。これを行う最も簡単な方法は、S に近い点を見つけることです。 B. グラフに実際に空間データがある場合は、頂点の座標を使用してこれを概算できます。そうでない場合は、S から各目的地までの最短経路を取得する必要があります。最も近い目的地を選択します。この場合、それが A であるとしましょう。そこに移動します。あとは B だけです。A から B までの最短経路を計算し、そこに行きます。

現在、2 つ以上の宛先がある状況では、これを再帰的に行うことができます。私は C++ を知りませんが、ここにいくつかの疑似コードを示します。

function pathThrough(startNode,destinationNodes[])
    closestNode = getClosestNode(startNode,destinationNodes)
    newDestinations = removeFromArray(destinationNodes,closestNode)
    return joinPaths(getShortestPath(startNode,closestNode),pathThrough(closestNode,newDestinations.))

closestNode および getShortestPath 関数については、グラフ、A*、ダイクストラのアルゴリズムなどに適した検索アルゴリズムを使用できます...

于 2012-08-23T03:22:58.513 に答える