1

在 (a) 和 (b) 中，假设一个 2 交换变换算子，将解决方案 A 和 B，它们是路径表示中的 TSP 旅游，连接到它们在旅游 C、D、E、F、G 中的可能邻居

(a) A: 1 2 3 4 5 6 7

C: 1 3 5 7 2 4 6
D: 1 2 5 4 3 6 7
E: 2 3 1 7 5 4 6
F: 4 1 7 5 3 2 6
G: 1 2 3 7 6 5 4

(b) B: 1 3 2 7 5 4 6

C: 1 3 5 7 2 4 6
D: 1 2 5 4 3 6 7
E: 2 3 1 7 5 4 6
F: 4 1 7 5 3 2 6
G: 1 2 3 7 6 5 4

我不知道这是要我做什么。

4

1 回答 1

2

定义（从问题文本中推断出来，也许你也在课堂上讨论过这个）
路径表示中的 TSP 之旅：
  数字 1 到 7 的有序序列，每个数字引用一次且仅一次。
  每个数字代表旅行推销员访问的城市。
  例如 D: 1 2 5 4 3 6 7，表示销售人员从城市 1 开始，到城市 2，然后到
  城市 5... 并在城市 7 结束。
此时引入“停止”的概念并将其标记为可能很有用小写字母，trhu g。（与用于识别问题中各种路径的大写字母完全没有关系）。
在 D 路径中，a 站是城市 1，c 站是城市 5，依此类推。

a 2-exchange transformation operator
  通过恰好交换两个城市（或更准确地说，将城市交换为两个站点）来转换 TSP 路径的操作。
因此，可以将 2-exchange 转换操作理解为采用三个参数的操作：路径 X、两个停靠点索引 m、n，并返回路径 X'，其中 m 和 n 的城市已被交换。
如果我们调用这个操作 Swp()，我们可以写

   Swp(A, c, e) = 1 2 5 4 3 6 7

任务（你的任务，你会接受吗 ;-)）
将解决方案 A 和 B（它们是路径表示中的 TSP 旅游）连接到它们在旅游 C、D、E、F、G 中可能的邻居
我猜它的要求是在 C、D、EF 和 G（大写，即路径）中识别哪些是 A（或 B）的“邻居”路径，即哪些可以通过单个 Swp 从 A（或 B）派生() 操作（并可能提供上述操作参数）。

通过扩展，人们可以将分配解释为需要以最少的步骤找到从 A 到另一条路径所需的 Swp() 操作列表（而不是可能有多个）。

于 2009-10-20T22:42:13.603 回答