gpt4 book ai didi

algorithm - 2.5-opt 线性搜索如何为 TSP 工作?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:07:15 24 4
gpt4 key购买 nike

我理解执行 2-opt、成对交换以使两条边不交叉背后的逻辑:

只需取出两条边,然后用另外两条代替。如果您有城市列表:

A, B, C, D, E, A,还有ABDE被选中...然后把顺序倒过来BD 之间的城市数因此:

A、E、B、C、D、A

对于 3-opt,同样,我也理解给定 A,B,C,D,E,F,A,有两种可能的变化。例如,如果选择了 ABCDEF,则:

A,C,B,E,D,F,AA,E,D,B,C,F,A 都是 3- 的可能性选择的游览。

但是,2.5 opt 到底是什么,如何实现?我试过寻找有关它的信息,但我不理解我发现的大部分内容......

最佳答案

文档位于 http://www.staff.uni-mainz.de/schneidj/papers/gestatten.pdf似乎相当清楚。

在第 2.2 节中,它描述了节点插入,它从巡回中剪切出一个节点并将其粘贴回之前一个接一个出现的其他两个节点之间(也有一张图片)。

2.3节描述了2-opt,相信你已经看懂了。

第 2.5 节描述了 3-opt 并计算出一些关于它的统计数据。在本节的最后,它表明节点插入可以被视为这种情况的一个特例,统计数据略有不同,因此,节点插入有时被称为 2.5-opt。与 3-opt 一样,它会切断三个链接,但与 2-opt 一样,有大约 O(N^2) 可能的此类移动。

如果链接再次断开,引用是:

论旅游者的邻里结构本地搜索移动产生的推销员问题君特·斯塔腾伯格·马库斯·丹克斯赖特·弗洛里安·鲍姆加特纳·约翰内斯·J·施耐德

关于algorithm - 2.5-opt 线性搜索如何为 TSP 工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21201399/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com