代码之家 › 专栏 › 技术社区 › Firas Assaad

利用旅行商解算器确定哈密顿路径

traveling-salesman genetic-algorithm language-agnostic algorithm

5

Firas Assaad · 技术社区 · 17 年前

这是一个项目,在这个项目中,我被要求实现一个启发式的旅行商优化问题,以及哈密顿路径或周期决策问题。我不需要实现本身的帮助,但对我将要进入的方向有一个问题。

我已经有了一个基于遗传算法的TSP启发式算法:它假设一个完整的图,以一组随机解作为总体,并致力于为数代改进总体。我也可以用它来解决哈密顿路径或循环问题吗?我不想优化以得到最短的路径,只想检查是否有路径。

现在,任何完整的图中都有哈密顿路径,因此TSP启发式必须扩展到任何图中。如果两个城市之间没有路径,可以将边设置为无穷大的值,然后返回第一条有效哈密顿路径。

这是接近它的正确方法吗?还是应该对哈密顿路径使用不同的启发式?我主要关心的是它是否是一个可行的方法,因为我可以肯定TSP优化是可行的(因为你从解决方案开始并改进它们),但如果哈密顿路径决策器在固定的几代中找到任何路径,就不行了。

我认为最好的方法是自己测试它,但是我受时间的限制,我想在走这条路之前我会问…(我可以为哈密顿路径找到不同的启发式方法)

2 回复 | 直到 16 年前

1

7

Grembo 16 年前

不知道你有没有答案。简单的技巧是添加一个距离所有其他点为零的虚拟点。求解TSP并去掉虚点——剩下的是哈密顿路径。简单!

2

4

Patrick Cornelissen 17 年前

这两个问题都是NP完全问题,因此根据定义,您可以转换输入并使用相同的算法;-)

但基本的想法应该是可行的。当然,您可能需要更改新路径的生成和成功标准。