关于有向图的 TSP 变体,两个相邻节点之间可能有两条边

问题描述 投票:0回答:1

我正在寻找关于有向图的 TSP(旅行商问题)的变体,其中任意两个相邻节点之间可能存在两条边。 注意:一个节点应该至少被访问一次,并且每两个相邻节点之间的两条平行边方向相反。

有这样的算法吗?

algorithm graph-theory
1个回答
0
投票

可以将有向图转化为无向图。

获取每个节点

u
并添加一个新节点
u'
。将它们与边权重连接起来,强制边
u-u'
始终成为 TSP 实例解决方案的一部分。任何替代边
u-v
都被分配了原始权重
u->v
并且每个替代边
u'-v
被分配了原始权重
v->u
.

然后,在解决对称问题之后,您可以通过将所有

u
u'
再次合并为一个来在原始图中导出TSP。

© www.soinside.com 2019 - 2024. All rights reserved.