飞机轰炸问题-帮助

Question

我正在训练代码问题，在这个问题上我有问题要解决，你能给我一些如何解决它的提示吗？

这个问题是从这里开始的：

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

问题12:愤世嫉俗的时代。

这个问题是这样的(但请参考上面的源问题链接，它有一个图表！)：

你的任务是在地图上找到轰炸机预计要行进的点的序列，这样它就可以击中所有重要的环节。从A到B的链接是至关重要的，当它的缺失将A和B完全隔离时。换句话说，从A到B(或反之亦然)的唯一方法就是通过该链接。

由于敌人的反击，飞机随时可能不得不撤退，所以飞机应该在每一个时刻跟随到尽可能最近的关键环节，即使最后总距离变得更大。

给定所有坐标(平面的初始位置和地图中的节点)和范围R，您必须确定飞机必须投放炸弹的位置序列。

此序列应在初始位置开始(起飞)和结束(着陆)。除了开始和结束之外，所有其他位置都必须精确地落在地图的一个片段中(即，它应该对应于非命中关键链接片段中的一个点)。

使用的坐标系将是UTM (Universal Transverse Mercator)北向和东向，这基本上对应于欧几里得的世界视角(X=Easting；Y=Northing)。

输入每个输入文件将以三个浮点数开始，表示机场的X0和Y0坐标以及范围R。第二行包含整数N，表示道路网络图中的节点数。然后，接下来的N行(<10000)每行都将包含一对浮点数，表示Xi和Yi坐标(1 < i<=N)。请注意，索引i成为每个节点的标识符。最后，最后一个块以整数M开头，表示链接的数量。然后，接下来的M (<10000)行将分别具有两个整数Ak和Bk (1 < Ak，Bk <=N；0

任何两个链接都不会相互交叉。

输出程序将打印坐标序列(成对的浮点数，只有一个小数点)，每一个都在一行上，按照飞机应该访问的顺序(从机场开始到结束)。

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 

Answer 1

我认为笨蛋关于第一部分是正确的，但在第二部分...问题描述没有说明任何关于“最小点数”的内容。它告诉我们飞机飞到了最接近的关键环节。因此，我认为第2部分会简单得多：

• 查找与当前location.
• Travel最接近的非命中线段，以及最近线段上的最接近点。
• 轰炸当前位置(移除所有相交于圆的线段)
• 重复操作，直到没有任何未命中的重要链接。

这种直接算法的复杂度为O(N*N)，但考虑到输入约束，这应该足够了。

Answer 2

1. 首先对输入进行预处理，因此您可以识别阻塞点。像弗洛伊德-沃肖尔这样的算法会对你有所帮助。
2. 将问题建模为启发式搜索问题，你可以计算覆盖所有瓶颈的最小生成树，并将边的成本总和作为启发式。
3. 正如评论者所说，试着在这里或向指导你课程的助教提出具体的问题。
4. 不要忘了说你是从哪里得到这些提示的。

Answer 3

这个问题可以分成两部分。

1)找到关键环节。

这些只不过是图中的Bridges。查看wiki页面(链接到上一句)，它提到了Tarjan的一种算法来找到桥。

2)一旦你有了重要的链接，你需要找到给定炸弹半径的最小数量的点，这些点将覆盖链接。为此，对于每个链接，您将在其周围创建一个区域，在该区域中，投掷炸弹将摧毁它。现在，您可以形成这些区域的图形(如果两个区域相交，则它们是相邻的)。您可能需要在此图中找到最小clique partition。

我还没有想清楚(特别是第2部分)，但希望它能有所帮助。

祝你比赛顺利！