graph-theory - 多次访问 tsp

Question

有没有人遇到过“多次访问不对称旅行推销员问题”的解决方案？

正常的旅行推销员问题参见（http://en.wikipedia.org/wiki/Travelling_salesman_problem），从 A->B 获取的成本与从 BA 获取的成本相同，不对称版本处理从from A->B 与 B->A 不同，但我有一个问题，即最佳旅行情况需要通过重复节点旅行。

假设网络有四个节点 A、B、C、D，这可以表示为距离矩阵

{{0,7,99999,2},{4,0,2,3},{99999,2,0,,2},{1,3,2,0}}

如果从 AB 出发的成本是 7 从 B->A 出发的成本是 4

最好的解决方案是 5 次 Internet 节点跳转 A->D D->C C->D ->D->B BA 正常的不对称版本不会从 C 返回到 D

有什么建议么

戴夫

Answer 1

我的猜测是您可以使用非对称解决方案，但只需保持权重相同。通过复制节点，您应该能够备份一次。当然，这不再是哈密顿循环，这就是为什么它被排除在常见解决方案之外的原因。