2

ByteLand Bytelandは、1..Nの番号が付けられたNの都市で構成されています。いくつかの都市のペアを結ぶM本の道路があります。王国を守るAとBの2つの軍隊があります。各都市は、陸軍師団Aまたは陸軍師団Bのいずれかによって保護されています。  

あなたは敵の王国の支配者であり、バイトランドを破壊する計画を考案しました。あなたの計画は、バイトランドのすべての道路を破壊し、すべての通信を妨害することです。いずれかの道路を攻撃すると、道路が接続する両方の都市の軍隊が防御のためにやって来ます。いずれかの道路を防御しているA軍とB軍の両方の兵士がいる場合、攻撃は失敗することに気づきます。  

したがって、この計画を実行する前に、いくつかの都市を攻撃し、都市にある軍隊を打ち負かして計画を可能にすることにします。ただし、これはかなり困難です。あなたは都市iにいる軍隊を倒すとci量の資源を消費すると見積もっています。今のあなたの目的は、あなたのコストが最小になり、軍AとBの両方から道路が保護されないように、攻撃する都市を決定することです。  

----このアプローチが正しいかどうか教えてください----

都市を破壊するために必要な資源の観点から都市を分類する必要があります。各都市について、次の質問をする必要があります。

1）前の都市を削除しても、バイトランドを破壊できる状態にはなりませんでしたか？

2）道路を接続していますか？

3）別の都市が武装している道路を接続していますか？

これらの条件がすべて当てはまる場合は、都市の破壊に進み、これまでに発生した総コストを記録し、この都市の破壊がバイトランドの全体的な破壊につながるかどうかも判断します。

都市は発生したコストの昇順で配置されているため、必要な削除のセットが見つかった場合はいつでも停止できます。

4

2 に答える 2

2

軍隊が異なる2つの都市を結ぶ道路（AとBの間のリンク、またはBとAの間のリンク）だけを気にする必要があるので、AからAまたはBからBのすべてのリンクを削除しましょう。

各リンクに少なくとも1つのポイントが含まれるようなポイントのセットを見つけたいと考えています。これは、最小の重みの頂点被覆です。任意のグラフでは、これはNP完全になります。ただし、グラフには、タイプAのノードがタイプBのノードにリンクされているか、またはその逆しかありません。これは、これら2つのタイプのノードを2つのパーティとして持つ2部グラフです。したがって、2部グラフで最小重み頂点被覆を見つけるためのアルゴリズムを使用して、最小重み頂点被覆を見つけることができます。これを検索すると、たとえばhttp://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2008/assignments/sol5.pdfが見つかります。

于 2013-01-18T14:09:39.727 に答える
1

mcdowella、

ただし、頂点にはコストがかかり、最小頂点被覆では、削除する適切な頂点が生成されません。2つの頂点（A軍）が3番目の頂点（B）を指していると想像してください。最初の2つの頂点のコストはそれぞれ1で、3番目の頂点のコストは5です。最小の頂点被覆は3番目の頂点を返しますが、3番目の頂点を削除すると、コスト1+1で両方のノードを削除するよりもコストがかかります。

ここでは、最小頂点被覆の修正バージョンが必要になる可能性があります。

于 2013-07-10T17:12:45.030 に答える