2

ポイントのあるマップがあります：

いくつかのノードと、それぞれの隣に緑と赤の数字があるマップ

各ポイントの横にある緑の数字はそのポイントの ID で、赤の数字はそのポイントのボーナスです。ポイント #1 で開始および終了し、少なくとも x (この場合は 15) のボーナス ポイントを獲得する最速のサイクルを見つける必要があります。都市を数回使用できます。ただし、ボーナス ポイントを獲得できるのは 1 回だけです。バックトラッキング アルゴリズムを使用してこれを行う必要がありますが、どこから始めればよいかわかりません。私はそれについて勉強しましたが、これと後戻りとの関係がわかりません。

出力は次のようになります。

(1,3,5,2,1) (11.813 length)

前と同じマップで、予想される出力ルートがオレンジ色で強調表示されています

4

2 に答える 2

1

再帰的なバックトラッキング アルゴリズムを使用して、考えられるすべてのサイクルをリストし、最良の答えを保持できます。

visitCycles(list<Int> cycleSoFar)
{
  if cycle formed by closing (cycleSoFar) > best answer so far
  {
    best answer so far = cycle formed by closing (cycleSoFar)
  }
  if (cannot improve (cycleSoFar))
  {
    return
  }
  for each point that makes sense
  {
    add point to cycleSoFar
    visitCycles(cycleSoFar)
    remove point from cycleSoFar
  }
}

もう少し詳細を追加するには：

1) 少なくとも 15 のボーナス ポイントがなければ、サイクルは適切ではありません。何でもいいなら今までのベストアンサーより短ければ良いです。

2) サイクルにポイントを追加すると、サイクルが長くなるだけで短くはなりません。したがって、考えられる答えを見つけて、cycleSoFar が少なくともその考えられる答えと同じ長さである場合、それを改善することはできず、戻ったほうがよいでしょう。

3) サイクルにすでにあるポイントを再利用してもボーナス ポイントは得られないため、ポイントを 2 回追加しようとしても意味がありません。

4) たとえば、現在のポイントに最も近いポイントを最初に選択するなど、「意味のある各ポイント」を適切な順序で反復することにより、プログラムを高速化できる場合があります。ポイントごとに、距離の昇順で他のすべてのポイントのリストを事前に計算することで、時間を節約できます (そうでない場合もあります。実験によってさまざまなスキームを試す必要がある場合もあります)。

于 2013-01-19T08:37:11.020 に答える
1

Backtracking問題の検索スペースを減らすために適用される手法です。つまり、問題があり、最適な解決策と最適でない解決策がある空間があり、最適な解決策を 1 つ選択する必要があります。

問題における単純な戦略は、考えられるすべての解を生成することです。ただし、このソリューションは、ソリューションの全空間を横断し、場合によっては、最適なソリューションが見つからないことに注意してください。

それが の主な役割ですbacktracking: ソリューションの空間を横断し、検索が同じ経路を続けた場合に最適な答えが得られないことがわかっている特定のポイントに到達すると、行ったステップを単純に悔い改め、元に戻ることができます。たどり、無力であることがわかったステップの直後にあるステップを選択します。

あなたの問題では、ノードを複数回訪問できるため、頂点ごとに、リストの頂点所有者からの距離によって減少するように並べ替えられた頂点のリストを維持することが考えられます。

次に、単純に頂点の 1 つから開始し、グラフを頂点ごとにウォークし、目標がまだ達成可能かどうかを常にチェックし、特定の点から解が得られないことに気付いたときはいつでも解をバックトラックします。点。

于 2013-01-19T01:33:55.557 に答える