私は学校の数学の授業のプロジェクトに取り組んでおり、巡回セールスマン問題についてのプロジェクトを行うことにしました。ただし、ブルートフォース解決アルゴリズムに問題があります。
*コードの最新バージョンを表示するには、下部の更新に移動してください
巡回セールスマンの問題が何であるかを知っている場合は、この段落をスキップしてください。 可能な限り要約すると、TSP は次のようになります。あなたは地域内の各都市を訪問したいセールスマンです (都市は基本的に地図上のポイントです)。境界のある x および y 領域には「n」個の都市があり、各都市は各都市に接続されています (直線道路を想定)。各都市を訪れることができるように、都市間の最短ルートを見つける必要があります。私が使用したいアルゴリズムの 1 つ (および他のアルゴリズムをテストする必要があります) は、すべての可能なルートをチェックし、最短ルートを返すブルート フォースです。ルート。これが常に使用されるわけではない理由は、(n-1) をチェックする必要があるためです! その数は、「n」が増加するにつれて膨大になります。実際、わずか 50 の都市では、608281864034267560872252163321295376887552831379210240000000000 のルートを確認する必要があります。
この投稿で説明されているすべての例について、4 つの都市を持つ任意の地域を使用することを前提としています (アルゴリズムは n 都市を処理できますが、距離についても気にしません。すべての可能なルートをブルートでヒットしたいと考えています)。力）。
これは、私が話していることをデモする簡単な図です (プロセスが適切に機能しているかどうかを確認するために、4 つの都市から始めています)
ブルート フォース アルゴリズムは次のとおりです (他のすべての呼び出されたメソッドは正しく機能すると仮定します)。
（もう少し詳しい説明については、以下を確認してください）
[コード]
public void BruteForceFindBestRoute(Route r) //Must start r having 1 unflagged city to begin with
{
if(!r.allFlagged() && r.route.size() != m.cities.size())
{
/*STEP 1 Begin with last unflagged city*/
City pivot = r.lastCityAdded();
/*STEP 2: Flag city*/
pivot.visited = true;
/*STEP 3: Find cities "NOT IN ROUTE"*/
ArrayList<City> citiesNotInRoute = new ArrayList<City>();
for(int i = 0; i<m.cities.size(); i++)
{
if(!r.isCityInRoute(m.cities.get(i).name))
{
citiesNotInRoute.add(m.cities.get(i));
}
}
/*STEP 4: Recursively call BruteForceFindBestRoute() using these cities added to the end of our original route*/
for(int i = 0; i<citiesNotInRoute.size(); i++)
{
Route newRoute = r;
newRoute.addToRoute(citiesNotInRoute.get(i));
BruteForceFindBestRoute(newRoute);
}
}
/*STEP 5: If the route is full but the last city isn't flagged, then flag it call BruteForceFindBestRoute() again, with the last city flagged*/
else if(!r.allFlagged() && r.route.size() == m.cities.size())
{
if(r.allFlaggedButLast())
{
Route x = r;
x.flagLastCity();
BruteForceFindBestRoute(x);
}
}
/*STEP 6: If all cities are flagged, the route is full. Check to see if it's the best route.*/
else if(r.allFlagged())
{
if(IsBestRoute(r))
bestRoute = r;
}
else
System.err.println("Error: somehow all cities got flagged, but the route isn't full");
}
ここに私の論理があります：（注：都市オブジェクトには「訪問済み」と呼ばれる「フラグ」ブール変数があります）
(すべてのルートにフラグが設定されておらず、ルートに可能な都市が含まれていない場合)
- フラグのない都市 1 つでルートを開始します。
- 「最後にフラグが立てられていない」都市にフラグを立てる (この都市は「ピボット」です)
- 「NOT IN ROUTE R」である各都市を見つけて、新しいルートに追加します。
- これらの各ルートで BruteForce メソッドを再帰的に呼び出します。
(すべてのルートにフラグが設定されていないが、ルートに各都市が含まれている場合)
- 最後の都市にフラグを立てる
(そうでなければ...これは、ルートに各都市にフラグが立てられ、可能な各都市が含まれていることを意味します)
- これが最短ルートかどうかを確認します。最短ルートの場合は、グローバル変数に保存します
この画像は問題を説明するのに役立ちます...したがって、プログラムは左側を正しく下ります。ただし、最下部に到達すると、再帰がステップ 4 に戻ることが予想されますが、実際に実行されています。ただし、R が都市 A にフラグを立て、都市 B にフラグを立てずに、Aflag と B を含む「新しいルート」で自分自身を再帰的に呼び出す代わりに、R には 4 つの都市すべてが含まれ、4 つすべてにフラグが立てられます。都市 D を「newRoute」に再度追加し、それ自体を再帰的に再度呼び出すため失敗します。別の方法では、私の地域には 5 つの都市がなく、ルート r には誤って 5 つの都市があるため、範囲外の配列エラーが発生します。 (A、B、C、D、D)。
この問題は、ループ内で再帰を呼び出しているか、再帰呼び出し内でルート 'r' が参照されていることに関係しています。
私が何をする必要があるのか 何かわかっている場合は、真剣に助けていただければ幸いです.
私を助けてくれる人に感謝します。プロジェクト全体を、喜んで手伝ってくれる人に送ります。
アップデート
さて、元の方法を短縮して単純化しようとしましたが、これが私が持っているものです:
public void BruteForceFindBestRoute(Route r, ArrayList<City> citiesNotInRoute)
{
if(!citiesNotInRoute.isEmpty())
{
for(int i = 0; i<citiesNotInRoute.size(); i++)
{
City justRemoved = (City) citiesNotInRoute.remove(0).clone();
Route newRoute = (Route) r.clone();
newRoute.addToRoute(justRemoved);
BruteForceFindBestRoute(newRoute, citiesNotInRoute);
citiesNotInRoute.add(justRemoved);
}
}
else //if(citiesNotInRoute.isEmpty())
{
if(IsBestRoute(r))
bestRoute = r;
}
}
問題は、for ループ内の変数 i が、再帰から抜けるとその意味を失ったように見え、ループが継続されないことです。アイデア？