algorithm - 飞机爆炸问题——求助

Question

我正在训练代码问题，在这个问题上我有问题要解决，你能给我一些解决方法吗？

问题取自这里:

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

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

问题是这样的(但请引用上面的源问题链接，它有图表!):

您的任务是在 map 上找到轰炸机预计飞行的点序列，以便它击中所有重要链接。从 A 到 B 的链接是至关重要的，因为它的缺失将 A 与 B 完全隔离开来。换句话说，从 A 到 B(或从 A 到 B)的唯一途径就是通过该链接。

由于敌人的反击，飞机随时可能不得不撤退，所以飞机应该每时每刻跟随到尽可能最近的要害点，即使最后总距离变大。

p>

给定所有坐标(飞机的初始位置和 map 中的节点)和范围R，您必须确定飞机必须投弹的位置顺序。

这个序列应该在初始位置开始(起飞)和结束(降落)。除了起点和终点，所有其他位置都必须恰好落在 map 的一个片段中(即它应该对应于非命中重要链接片段中的一个点)。

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

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

没有两个链接会相互交叉。

输出该程序将按照飞机应该访问的顺序(在机场开始和结束)打印坐标序列(一对正好有一位小数的 float )。

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

1. 首先对输入进行预处理，以便识别阻塞点。像 Floyd-Warshall 这样的算法会帮助你。
2. 将问题建模为启发式搜索问题，您可以计算覆盖所有阻塞点的 MST，并将边的成本总和作为启发式。
3. 正如评论者所说，尝试提出具体问题，无论是在这里还是向监督您类(class)的助教。
4. 不要忘记说明您是从哪里获得这些提示的。