← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3744.c

禁忌表防止TSP重复选城

理解等级:中级

TSP 要求经过每座城市恰好一次再回到起点。蚂蚁 k 用路径记忆向量 R 按访问顺序记下已走过的城市;从当前城 i 出发,候选集合 Jk(i) 只含“可直达、且还不在 R 里”的城市。按式(5-1)选出下一城 j 后,立刻把 j 写入禁忌表(即更新 R)。概率因此只在未访问城市之间分配,构造出的路线天然满足“每城一次”,不必先随便生成再修补。

示例(补充教学示例,非书中数据):4 城,已走 R=(1, 3),当前在 3。Jk(3)={2, 4}。若选中 2,禁忌表变为 (1, 3, 2),下一轮不能再选 1 或 3。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 5 . 2 蚁 群 算 法 实 现 · 查看原书依据

      首先,在构建路径的过程中,每只蚂蚁都随机选择一个城市作为其出发城市,并维护一个路径记忆向量,用来存放该蚂蚁依次经过的城市,蚂蚁在构建路径的每一步中,按照随机比例规则选择下一个将要到达的城市。

    参考来源

    - 位置:《智能算法导论》第 5 章“5.2 蚁群算法实现”(源文件:EPUB/xhtml/chapter5_0003.xhtml)。 - 结论依据:原文定义 TSP 须经过各城当且仅一次并回到出发城;R 记录已访顺序,Jk(i) 为可直达且不在 R 中的城市,流程在选城后修改禁忌表。四城示意为依据该定义补充的教学示例,非书中数据。 - 原始内容:每只蚂蚁都随机选择一个城市作为其出发城市,并维护一个路径记忆向量,用来存放该蚂蚁依次经过的城市,蚂蚁在构建路径的每一步中,按照随机比例规则选择下一个将要到达的城市