2

我有一个随机的无向社交图。

如果可能的话，我想找到一条哈密顿路径。或者如果不可能（或者不可能在多项式时间内知道是否可能）一系列路径。在这个“路径系列”（所有 N 个节点只使用一次）中，我想最小化路径的数量并最大化路径的平均长度。（因此单个节点的 N 条路径没有平凡的解决方案）。

我已经为节点和边生成了一个邻接矩阵。

有什么建议么？指向正确方向的指针？我意识到这将需要启发式方法，因为问题的 NP 完全（？）性质，我可以接受“足够好”的答案。我也想在Java中做到这一点。

谢谢！

4

4 回答 4

2

如果我正确解释了您的问题，那么您所要求的仍然是 NP-hard，因为“多路径”问题的最佳解决方案是哈密顿路径，并且确定是否存在已知是 NP-hard . 此外，即使你保证不存在哈密顿路径，解决这个问题仍然可能是 NP 难的，因为我可以给你一个图，其中有一个在空间中浮动的断开节点，最好的解决方案是包含该节点的平凡路径和剩余图中的哈密顿路径。因此，除非 P = NP，否则不会有多项式时间算法来解决您的问题。

希望这会有所帮助，并对负面结果感到抱歉！

于 2012-02-07T06:13:48.330 回答
2

Angluin 和 Valiant 给出了一个接近线性时间的启发式算法，它几乎总是在足够密集的 Erdos-Renyi 随机图中起作用。Wilf 在第 121 页对此进行了描述。可能您的随机图不是Erdos-Renyi，但启发式方法可能仍然有效（当它“失败”时，它仍然给您（希望）一条长路径；贪婪地走这条路并再次运行 AV）。

于 2012-02-14T14:35:49.220 回答
1

正如您已经意识到在多项式时间内没有精确的解决方案。不过，您可以尝试一些随机搜索方法。我的建议，从遗传算法开始，尝试禁忌搜索。

于 2012-02-14T01:19:05.397 回答
1

使用遗传算法（没有交叉），其中每个个体都是节点的排列。这为您提供了每一代的“一系列路径”，演变为最少数量的路径 (1) 和最大的平均。长度（N）。

于 2012-02-14T14:26:02.160 回答