gru*_*czy 7 algorithm a-star traveling-salesman
可能重复:
使用A*解决旅行商问题
我最近了解到A*算法可以应用于旅行商问题.我们如何确定这里的起点和目标,以及如何将权重应用于节点(什么是启发式)？
有人会向我解释如何在这里应用A*吗？
dfb*_*dfb 10
A*是Dijsktra的衍生物,我认为不能以这种方式使用.首先,TSP通常从任何节点开始.更重要的是,这些算法试图找到两点之间的最短路径,而不管访问的节点数量.实际上,它们取决于通过某个节点A从S到T的最短路径,从S到A的路径是相同的,如果它是相同的成本.
我看到这种功能的唯一方法是,如果您生成了一个表示访问过的节点的新图.例如,在优先级队列中,您将放置访问的节点集和当前节点.这将导致可能检查$ n2 ^ n $节点(这不是动态编程解决方案对TSP的运行时间http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/ BOOK2/NODE49.HTM).到目前为止,并不是很好,但通过使用A*而不是Dijsktra,您可能能够找到在合理的时间内运行的启发式算法.
要实现这一点,您的起始节点将是(1,{}),结束节点将是(1,{1..n}).您将模仿原始图形的边缘权重.关于启发式的建议,你是自己的..
这里可以应用A*,但它可能不是最好的算法.
你将不得不离开它们之间的城市和道路图.相反,定义一个有向图,其中部分路径是节点,如果y可以通过在原始城市图中添加单个"步骤" 从x构造,则连接两个节点x和y.起始节点是空路径.目标节点是访问所有城市的路径.(此路径的最优性由启发式和A*算法本身的属性保证.)
[ 编辑:起初我认为路径应该是一个有序的城市列表,但我现在相信@ spinning_plate建议用一对(长度,一组城市)来表示路径就足够了.
路径成本是行进的总距离.启发式算法必须是总的最小旅行长度的一些可接受的估计(通常是低估).
这种估计的良好候选者可能是TSP的快速近似(松弛问题的解决方案).您将在尚未覆盖的城市集上为每个节点(部分路径)运行近似算法.这为算法提供了销售员仍需要的距离的必要上限.
如果我有一把锤子（A* 搜索），那么每个问题（TSP）都是一颗钉子（寻路）。
是的，理论上可以将 TSP 问题转换为更大的图并对其使用A* 搜索。但遗憾的是它没有用，因为它不会扩展（见 spin_plate 的评论）。即使是小实例也可能需要数年时间才能在现代硬件上以这种方式解决。
TSP 是NP-complete，寻路不是。
如果是螺丝（NP完全问题），请使用螺丝刀（元启发式，...）。
使用元启发式算法（禁忌搜索、遗传算法、模拟退火等）。有关软件示例，请参阅Drools Planner、openTS、jgap、cpsolver、...