飛機轟炸問題 - 幫助

我正在訓練代碼問題，在這一個我有問題解決它，你能給我一些提示如何解決它請。飛機轟炸問題 - 幫助

的問題就是從這裏取：

https://www.ieee.org/documents/IEEEXtreme2008_Competitition_book_2.pdf

問題12：玩世時代。

的問題是這樣的（但參考源的問題上面的鏈接，它有圖！）：

你的任務是找到點的序列中的地圖上，該轟炸機預計旅行，使其擊中所有重要的環節。從A到B的鏈接是至關重要的，因爲它不存在從B完全隔離A的情況。換句話說，從A到B（或相反）的唯一途徑是通過該鏈接。

由於敵人的反擊，飛機可能隨時需要撤退，所以飛機應該在每個時刻跟隨最接近的重要環節，即使最後總距離會變大。

給定所有座標（地圖的初始位置和地圖中的節點）和範圍R，必須確定飛機必須放置炸彈的位置順序。

該序列應該在起始位置開始（起飛）和完成（着陸）。除了開始和結束之外，所有其他位置都必須完全落在地圖的一部分中（即，它應該對應於未命中的重要鏈接部分中的一個點）。

使用的座標系統將是UTM（通用橫軸墨卡託投影機）北向和東向，它基本上對應於世界的歐幾里得視角（X =東向; Y =北向）。

輸入每個輸入文件將以三個浮點數字開頭，表示機場的X0和Y0座標以及範圍R.第二行包含一個整數N，表示道路網絡圖中節點的數量。然後，下一個N（< 10000）行將包含一對浮點數，指示Xi和Yi座標（1 < i < = N）。請注意，索引i成爲每個節點的標識符。最後，最後一個塊以整數M開始，表示鏈接的數量。然後，下一個M（< 10000）行將分別具有與鏈接在一起的點的標識符相對應的兩個整數Ak和Bk（1,< Ak，Bk < = N;M）。

沒有兩個鏈接會彼此交叉。

輸出程序將按照飛機應該訪問的順序（在機場開始和結束）打印每行一行的座標序列（具有小數點後一位的浮點數）。

Sample input 1 

102.3 553.9 0.2 
14 
342.2 832.5 
596.2 638.5 
479.7 991.3 
720.4 874.8 
744.3 1284.1 
1294.6 924.2 
1467.5 659.6 
1802.6 659.6 
1686.2 860.7 
1548.6 1111.2 
1834.4 1054.8 
564.4 1442.8 
850.1 1460.5 
1294.6 1485.1 
17 
1 2 
1 3 
2 4 
3 4 
4 5 
4 6 
6 7 
7 8 
8 9 
8 10 
9 10 
10 11 
6 11 
5 12 
5 13 
12 13 
13 14 

Sample output 1 
102.3 553.9 
720.4 874.8 
850.1 1460.5 
102.3 553.9

來源

2010-05-31 Peiska

你應該使用什麼語言？另外，不要指望任何人爲你做。人們可以給你提示，但就是這樣。 – 2010-05-31 15:05:49

嗯。你試過什麼了？你卡在哪裏？ – karim79 2010-05-31 15:06:10

http://en.wikipedia.org/wiki/Travelling_salesman_problem – tvanfosson 2010-05-31 15:06:30

我覺得倫'是說得對的第一部分，但第二部分... 問題描述不告訴‘最小數量的點’東西。它告訴飛機飛到最近的重要環節。因此，我認爲第二部分將會簡單得多：

查找距離當前位置最近的未命中區段。
前往最近段最近的點。
炸彈當前位置（移除所有與圓相交的線段）
重複，直到沒有未命中的重要鏈接爲止。

這種直接算法的複雜度爲O（N * N），但考慮到輸入約束條件，這應該足夠了。

來源

2010-05-31 16:36:54 Rotsor

我相信目的是放棄最少數量的炸彈，而不管總行程。最接近的鏈接僅僅是根據到機場的距離來排列積分以最小化攻擊的風險。（至少這是我的解釋） – 2010-05-31 16:47:54

謝謝你的提示。 – Peiska 2010-05-31 16:52:05

@Moron：拋出最少數量的炸彈（問題陳述中沒有明確要求）將要求你違反「最接近的鏈接」要求（**是**明確的）。所以，除非我錯過了問題陳述的某些部分，否則丟棄的炸彈數量不應該很少。 – Rotsor 2010-05-31 16:59:37

處理前輸入的第一，所以你找出瓶頸。像Floyd-Warshall算法會幫助你。
將問題建模爲啓發式搜索問題，您可以計算覆蓋所有阻塞點的MST，並將邊緣成本的總和作爲啓發式算法。
正如評論者所說，試着提出具體的問題，無論是在這裏，還是由TA來監督你的班級。
不要忘記提及這些提示。

來源

2010-05-31 15:27:38 miquelramirez

對不起，這似乎並不明顯。你能否詳細說明一下？ – 2010-05-31 16:19:38

根據我在發佈問題陳述指針之前所瞭解的內容，這完全是爲了找到飛機的計劃：即從機場飛到位置X，在X處放下炸彈，從位置X飛到位置Y，將炸彈放在Y等等。你的回答給出了確定這些位置的非常可靠的方法。 – miquelramirez 2010-06-01 13:48:12

搜索空間將包括已經轟炸過的地點和當前的計劃位置，從一個國家轉移到另一個國家（飛向或炸彈）的行動，轟炸行動的成本爲零，飛行行動費用爲INV。與當前平面位置和目標位置之間的距離成比例。 – miquelramirez 2010-06-01 13:48:42

該問題可以分解爲兩部分。

1）找到重要的鏈接。

這些只不過是上述圖表中的Bridges。請參閱wiki頁面（鏈接到前一句），它提到了Tarjan找到的橋樑算法。

2）一旦你有重要的鏈接，你需要找到給定的炸彈半徑的最小點數，將覆蓋鏈接。爲此，對於每一個環節，你都會在其周圍創建一個區域，在那裏放置炸彈將會破壞它。現在你形成這些區域的圖形（如果它們相交，則兩個區域相鄰）。您可能需要在此圖中找到最低clique partition。

有沒有想過它（特別是第2部分），但希望它有幫助。

祝你好運！

來源

2010-05-31 16:10:17

飛機轟炸問題 - 幫助

回答

相關問題