多数のノード (バス停) といくつかの特別なノード (バスステーション) があるこのグラフの問題があります。すべてのノードをカバーする必要があります - それらすべてをカバーするバスルートを割り当てます - 駅で開始および終了するときに、使用できるバスの数に制限があります。どのように開始すればよいですか?
質問する
1199 次
2 に答える
1
すべてのノードを接続する最短経路を見つける問題 (バス ステーションの制限あり) は、巡回セールスマン問題から次の削減で還元できます。TSP 問題が与えられた場合、この問題のインスタンスを 1/2 ステーション/"特別なノードで作成します。 」 （同じ駅に戻るかどうかによって異なります）。
この削減を使用すると、この問題が多項式で解決できる場合、TSP も同様です。
したがって - 問題はNP-Hardであり、それに対する既知の多項式解はありません(そして仮定は - まだ証明されていませんが、存在しないということです)
いくつかの代替手段は、遺伝的アルゴリズムやヒル クライミングなどのヒューリスティック アルゴリズム、近似アルゴリズム、または指数アルゴリズム (データが比較的小さい場合に最適解を見つけるために使用できます) や動的計画法や分枝限定などです。
編集: (編集された質問への応答)
複数のバスを使用できる場合でも (バスの数が限られている場合でも)、問題は依然として NP 困難です。なぜなら (バスの数が一定である/単項コーディングで与えられていると仮定すると): グラフをk個別のコンポーネントに「複製」できるからです (はバスの数に制限がkあります) - そして、各コンポーネントに新しい TSP 問題が発生します。
于 2012-11-25T15:20:38.360 に答える
0
簡単なアイデアは次のとおりです。
- グラフから開始ノードと終了ノードを削除します。
- 最小全域木を検索します
- 開始-終了ノードをスパニングツリーに接続します。
それであなたは最小限のカバーソリューションを持つことができます。
もちろん、各ノードに1回アクセスする必要がある場合は、前述のように、これはNP困難な問題です。
于 2012-11-25T15:23:54.293 に答える