0

巡回セールスマン問題が分かりました。選択した都市だけを訪れて最初に戻りたいとしたら、どうすればよいでしょうか?

私のコストマトリックスは、

  A B C D
A 0 1 2 1
B 1 0 1 2
C 2 1 0 1
D 1 2 1 0

すべての都市を訪れて A に戻りたい場合、最短経路は になりA->B->C->D、最小距離は になります4。

B と D だけに行きたいとします。どうすれば最小距離を見つけることができますか?

これは修正された巡回セールスマン問題ですか? この場合、ブルートフォースアルゴリズムを実行するのを手伝ってくれる人はいますか?

4

2 に答える 2

0

私はコードを手元に持っていませんが、ここにいくつかの提案と疑似コードを示します。ベクトルと上記の距離行列をメモリに保存することでこれを解決します。何かのようなもの：

struct Location{
bool visited;
bool mustVisit;
}

Vector<Location> locationVec;

ベクトルに問題の場所を入力し、訪問する必要があるかどうかをマークし、訪問済みを常に false に設定します。それから楽しい部分が来ます！locationVec の順列を作成する必要があります。これを次のように再帰的に行います。

void addLocation(int & curLength, int & maxLength, int & curDistance, Vector<Location> &locationVec, Location* lastVisited)
if(curLenth == maxLength){
//check if currentDistance is less than the previously generated best difference, if so
//replace it
lastVisited->visited=0;
return;
}

//Add the next location
for (int& i : locationVec){
//Check if the location has been visited, and if it must be visited.
//If so: mark as visited, point lastVisited to it, and break
//Also add from lastVisited to the new location to your curDistance
curLength++;
}

addLocation(curLength, maxLength, curDistance, locationVec, lastVisited);
return;
}

これで始められるはずです。訪問済み = 1 から訪問済み = 0 に変更するときは、currentDist から減算することを忘れないでください。これは、都市を本質的に「訪問していない」ためです。正確な実装によっては、lastlastvisited も追跡する必要がある場合があります。

スピードアップする必要がある場合 (セールスマンの移動は非常に遅くなります)、Branch and Bound を調べてください: http://en.wikipedia.org/wiki/Branch_and_bound

于 2013-08-07T07:28:41.903 に答える