旅行售货员问题和贪婪算法

旅行售货员的问题由推销员和一组城市遵守。推销员必须从某个城市(例如家乡)开始访问每个城市, 然后返回同一城市。问题的挑战在于, 旅行售货员需要使旅行的总长度最小化。

假设城市为x1 x2 ….. xn, 其中成本cij表示从城市xi到xj的旅行成本。旅行售货员的问题是找到一条始于x1的路线, 该路线将以最低的成本在所有城市中行驶。

示例:一家报纸代理商每天将报纸丢到指定的区域, 这样他必须以最小的旅行费用覆盖相应区域中的所有房屋。计算最低旅行成本。

图中显示了分配给代理商必须放置报纸的区域:

旅行售货员问题

解决方案:图G的成本邻接矩阵如下:

Costij =

旅行售货员问题

游览从区域H1开始, 然后选择从区域H1可以到达的最低费用区域。

旅行售货员问题

标记区域H6, 因为它是从H1可以到达的最小成本区域, 然后选择可以从H6到达的最小成本区域。

旅行售货员问题

标记区域H7, 因为它是从H6可以到达的最小成本区域, 然后选择可以从H7到达的最小成本区域。

旅行售货员问题

标记区域H8, 因为它是从H8可以到达的最小成本区域。

旅行售货员问题

标记区域H5, 因为它是从H5可以到达的最小成本区域。

旅行售货员问题

标记区域H2, 因为它是从H2可以到达的最小成本区域。

旅行售货员问题

标记区域H3, 因为它是从H3可以到达的最小成本区域。

旅行售货员问题

标记区域H4, 然后从H4选择可以到达的最小成本区域为H1。因此, 使用贪婪策略, 我们得到以下结果。

4    3    2    4    3    2   1    6
H1 → H6 → H7 → H8 → H5 → H2 → H3 → H4 → H1.

因此, 最低旅行成本= 4 + 3 + 2 + 4 + 3 + 2 +1 + 6 = 25

拟阵

拟阵是满足以下条件的有序对M(S, I):

  1. S是一个有限集。
  2. I是S的一个非空子集, 称为S的独立子集, 因此, 如果B∈I和A∈I。我们说I是世袭的, 如果它满足此性质。请注意, 空集合necessarily一定是I的成员。
  3. 如果A∈I, B∈I和| A | <| B |, 那么有元素x∈B? A∪{x}∈I。我们说M满足交换性质。

我们说如果有关联权重函数w为每个元素x∈S分配严格的正权重w(x), 则对拟阵M(S, I)加权。权重函数w通过求和扩展到S的子集:

w (A) = ∑x∈A w(x)

对于任何A∈S。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?