Angluin和Valiant给出了一个近似线性的时间启发式算法，该算法几乎总是在足够稠密的Erdos-Renyi随机图中工作。威尔夫在第121页对此进行了描述。也许你的随机图是而不是Erdos-Renyi，但启发式无论如何都可能奏效（当它"失败"时，它仍然（希望）给你一条很长的路；贪婪地走这条路并再次运行A-V）。
我有一个随机的无向社会图。
如果可能的话，我想找到一条哈密顿路径。或者，如果不可能（或者不可能知道在多项式时间内是否可能）一系列路径。在这个"路径系列"（所有N个节点只使用一次）中，我想最小化路径的数量，最大化路径的平均长度。（因此，单个节点的N条路径没有平凡的解）。
我已经为节点和边生成了一个邻接矩阵。
有什么建议吗？指向正确的方向？我意识到这将需要启发式，因为问题的NP完全（？）性质，我对"足够好"的答案是可以的。我也想用Java做这件事。
谢谢！
如果我正确地解释了你的问题，你所要求的仍然是NP难的，因为"多路径"问题的最佳解决方案是哈密顿路径，并且确定是否存在一个路径是已知的NP难的。此外，即使你保证不存在哈密顿路径，解决这个问题仍然可能是NP困难的，因为我可以给你一个图，其中有一个漂浮在空间中的断开连接的节点，对于这个图，最好的解决方案是一个包含该节点的平凡路径和剩余图中的哈密顿路径。因此，除非P=NP，否则就不会有多项式时间算法来解决你的问题。
希望这能有所帮助，并对负面结果感到抱歉！
使用遗传算法（无交叉），其中每个个体都是节点的排列。这会在每一代中为您提供"一系列路径"，演变为最小数量的路径（1）和最大平均长度（N）。
正如您所意识到的，多项式时间中没有精确的解。不过，你可以尝试一些随机搜索方法。我的建议是，从遗传算法开始，尝试禁忌搜索。