我被要求为旅行商优化问题和哈密顿路径或循环决策问题实现启发式算法。我不需要在实现本身方面寻求帮助,但我对自己的方向有一些问题。
我已经有了一个基于遗传算法的TSP启发式算法:它假设一个完整的图,从一组随机解作为种群开始,并致力于改进种群一定数量的代数。我能否也用它来解决哈密顿路径或循环问题?我只想检查是否存在路径,而不是优化以获得最短路径。
现在任何完整的图中都会有一个哈密顿路径,因此TSP启发式方法必须扩展到任何图。这可以通过将边设置为无限值来完成,如果两个城市之间没有路径,则返回第一个有效的哈密顿路径。
这是正确的方法吗?还是应该使用不同的启发式方法来解决哈密顿路径问题?我的主要关注点是它是否是可行的方法,因为我可以相当确定TSP优化可行(因为您从解决方案开始并改进它们),但是不能确定哈密顿路径决策者是否能在固定的代数中找到任何路径。
我认为最好的方法是自己测试它,但是我时间有限,所以在走这条路之前想问一下...... (我可以寻找不同的哈密顿路径启发式方法)