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

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

假设城市为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）：

S是一个有限集。
I是S的一个非空子集, 称为S的独立子集, 因此, 如果B∈I和A∈I。我们说I是世袭的, 如果它满足此性质。请注意, 空集合necessarily一定是I的成员。
如果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。