使用近似算法的旅行商问题
我们已经讨论了使用贪婪算法和动态规划方法解决旅行商问题，并且已经确定，在多项式中不可能找到完美的最优解。时间。
因此，近似解有望找到该 NP-Hard 问题的近似最优解。然而，只有当问题中的成本函数（定义为两个绘制点之间的距离）满足三角不等式时，才会设计近似算法。
只有当三角形 u、v 和 w 的所有顶点的成本函数 c 满足以下等式时，才满足三角不等式。
c(u, w)≤ c(u, v)+c(v, w)
在许多应用中，它通常自动满足。
旅行商近似算法
旅行商近似算法需要执行一些先决算法，才能获得近似最优解。让我们简要地看一下这些先决算法 −
最小生成树 − 最小生成树是一种树形数据结构，它包含主图的所有顶点，并且连接它们的边数最少。在这种情况下，我们应用 prim 算法来计算最小生成树。
先序遍历 −前序遍历是在树形数据结构中进行的，其中指针按 [根节点 - 左子节点 - 右子节点] 的顺序遍历树的所有节点。
算法
步骤 1 − 随机选择给定图中的任意顶点作为起点和终点。
步骤 2 − 使用 prim 算法构建图的最小生成树，并以该顶点为根节点。
步骤 3 − 构建生成树后，对上一步获得的最小生成树进行前序遍历。
步骤 4 − 获得的前序解即为旅行商的汉密尔顿路径。
伪代码
APPROX_TSP(G, c)
r <- root node of the minimum spanning tree
T <- MST_Prim(G, c, r)
visited = {ф}
for i in range V:
H <- Preorder_Traversal(G)
visited = {H}
分析
如果满足三角不等式，则旅行商问题的近似算法是二阶近似算法。
为了证明这一点，我们需要证明该问题的近似成本是最优成本的两倍。支持这一说法的一些观察结果如下 −
最小生成树的成本永远不会小于最优汉密尔顿路径的成本。即 c(M) ≤ c(H*)。
完整遍历的成本也是最小生成树成本的两倍。完整遍历定义为按序遍历最小生成树时所追踪的路径。完整遍历会恰好遍历图中存在的每条边两次。因此，c(W) = 2c(T)
由于预序行走路径小于完整行走路径，因此算法的输出始终低于完整行走的成本。
示例
让我们通过一个示例图来可视化此近似算法 −
解决方案
将上图中的顶点 1 视为旅行商的起点和终点，并从此处开始算法。
步骤 1
从顶点 1 开始算法，构造一个最小生成树从图中得出树。要了解更多关于构建最小生成树的信息，请点击此处
步骤 2
构建最小生成树后，将起始顶点视为根节点（即顶点 1），并按原序遍历生成树。
为了便于解释，旋转生成树，我们得到 −
原序遍历树的结果为 − 1 → 2 → 5 → 6 → 3 → 4
步骤 3
在追踪路径的末尾添加根节点，我们得到：1 → 2 → 5 → 6 → 3 → 4 → 1
这是旅行商近似问题的输出汉密尔顿路径。该路径的成本将是最小生成树中所有成本的总和，即 55。
实现
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define V 6 // 图中的顶点数
// 从尚未包含在 MST 中的顶点集中查找最小关键顶点的函数
int findMinKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}
// 执行 Prim 算法来查找最小生成树 (MST) 的函数
void primMST(int graph[V][V], int parent[]) {
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = findMinKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++) {
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
}
// 打印最小生成树的前序遍历的函数
void printPreorderTraversal(int parent[]) {
printf("发现树的前序遍历是 − ");
for (int i = 1; i < V; i++) {
printf("%d → ", parent[i]);
}
printf("
");
}
// 旅行商近似算法的主要功能
void tspApproximation(int graph[V][V]) {
int parent[V];
int root = 0; // 选择顶点 0 作为起点和终点
// 使用 Prim 算法查找最小生成树
primMST(graph, parent);
// 打印最小生成树的前序遍历
printPreorderTraversal(parent);
// 打印汉密尔顿路径（前序遍历，在末尾添加起点）
printf("在追踪路径的末尾添加根节点 ");
for (int i = 0; i < V; i++) {
printf("%d → ", parent[i]);
}
printf("%d → %d
", root, parent[0]);
// 计算并打印汉密尔顿路径的成本
int cost = 0;
for (int i = 1; i < V; i++) {
cost += graph[parent[i]][i];
}
// 路径的成本将是最小生成树中所有成本的总和。
printf("Sum of all the costs in the minimum spanning tree %d.
", cost);
}
int main() {
// 以邻接矩阵表示的示例图
int graph[V][V] = {
{0, 3, 1, 6, 0, 0},
{3, 0, 5, 0, 3, 0},
{1, 5, 0, 5, 6, 4},
{6, 0, 5, 0, 0, 2},
{0, 3, 6, 0, 0, 6},
{0, 0, 4, 2, 6, 0}
};
tspApproximation(graph);
return 0;
}
输出
发现树的前序遍历是 − 0 → 0 → 5 → 1 → 2 → 在追踪路径的末尾添加根节点 -1 → 0 → 0 → 5 → 1 → 2 → 0 → -1 Sum of all the costs in the minimum spanning tree 13.
#include <iostream>
#include <limits>
#define V 6 // 图中的顶点数
// 从尚未包含在 MST 中的顶点集中查找最小关键顶点的函数
int findMinKey(int key[], bool mstSet[]) {
int min = std::numeric_limits<int>::max();
int min_index;
for (int v = 0; v < V; v++) {
if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}
// 执行 Prim 算法来查找最小生成树 (MST) 的函数
void primMST(int graph[V][V], int parent[]) {
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++) {
key[i] = std::numeric_limits<int>::max();
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = findMinKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++) {
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
}
// 打印最小生成树的前序遍历的函数
void printPreorderTraversal(int parent[]) {
std::cout << "发现树的前序遍历是 − ";
for (int i = 1; i < V; i++) {
std::cout << parent[i] << " → ";
}
std::cout << std::endl;
}
// 旅行商近似算法的主要功能
void tspApproximation(int graph[V][V]) {
int parent[V];
int root = 0; // 选择顶点 0 作为起点和终点
// 使用 Prim 算法查找最小生成树
primMST(graph, parent);
// 打印最小生成树的前序遍历
printPreorderTraversal(parent);
// 打印汉密尔顿路径（前序遍历，在末尾添加起点）
std::cout << "在追踪路径的末尾添加根节点 ";
for (int i = 0; i < V; i++) {
std::cout << parent[i] << " → ";
}
std::cout << root << " → " << parent[0] << std::endl;
// 计算并打印汉密尔顿路径的成本
int cost = 0;
for (int i = 1; i < V; i++) {
cost += graph[parent[i]][i];
}
// 路径的成本将是最小生成树中所有成本的总和。
std::cout << "最小生成树中所有成本的总和： " << cost << "." << std::endl;
}
int main() {
// 以邻接矩阵表示的示例图
int graph[V][V] = {
{0, 3, 1, 6, 0, 0},
{3, 0, 5, 0, 3, 0},
{1, 5, 0, 5, 6, 4},
{6, 0, 5, 0, 0, 2},
{0, 3, 6, 0, 0, 6},
{0, 0, 4, 2, 6, 0}
};
tspApproximation(graph);
return 0;
}
输出
发现树的前序遍历是 − 0 → 0 → 5 → 1 → 2 → 在追踪路径的末尾添加根节点 -1 → 0 → 0 → 5 → 1 → 2 → 0 → -1 最小生成树中所有成本的总和： 13.
import java.util.Arrays;
public class TravelingSalesperson {
static final int V = 6; // 图中的顶点数
// 从尚未包含在 MST 中的顶点集中查找最小关键顶点的函数
static int findMinKey(int key[], boolean mstSet[]) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int v = 0; v < V; v++) {
if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
// 执行 Prim 算法来查找最小生成树 (MST) 的函数
static void primMST(int graph[][], int parent[]) {
int key[] = new int[V];
boolean mstSet[] = new boolean[V];
Arrays.fill(key, Integer.MAX_VALUE);
Arrays.fill(mstSet, false);
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = findMinKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++) {
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
}
// 打印最小生成树的前序遍历的函数
static void printPreorderTraversal(int parent[]) {
System.out.print("发现树的前序遍历是 ");
for (int i = 1; i < V; i++) {
System.out.print(parent[i] + " -> ");
}
System.out.println();
}
// 旅行商近似算法的主要功能
static void tspApproximation(int graph[][]) {
int parent[] = new int[V];
int root = 0; // 选择顶点 0 作为起点和终点
// 使用 Prim 算法查找最小生成树
primMST(graph, parent);
// 打印最小生成树的前序遍历
printPreorderTraversal(parent);
// 打印汉密尔顿路径（前序遍历，在末尾添加起点）
System.out.print("在追踪路径的末尾添加根节点 ");
for (int i = 0; i < V; i++) {
System.out.print(parent[i] + " -> ");
}
System.out.println(root + " " + parent[0]);
// 计算并打印汉密尔顿路径的成本
int cost = 0;
for (int i = 1; i < V; i++) {
cost += graph[parent[i]][i];
}
// 路径的成本将是最小生成树中所有成本的总和。
System.out.println("最小生成树中所有成本的总和： " + cost);
}
public static void main(String[] args) {
// 以邻接矩阵表示的示例图
int graph[][] = {
{0, 3, 1, 6, 0, 0},
{3, 0, 5, 0, 3, 0},
{1, 5, 0, 5, 6, 4},
{6, 0, 5, 0, 0, 2},
{0, 3, 6, 0, 0, 6},
{0, 0, 4, 2, 6, 0}
};
tspApproximation(graph);
}
}
输出
发现树的前序遍历是 0 -> 0 -> 5 -> 1 -> 2 -> 在追踪路径的末尾添加根节点 -1 -> 0 -> 0 -> 5 -> 1 -> 2 -> 0 -1 最小生成树中所有成本的总和： 13
import sys
V = 6 # 图中的顶点数
# 从尚未包含在 MST 中的顶点集中查找最小关键顶点的函数
def findMinKey(key, mstSet):
min_val = sys.maxsize
min_index = -1
for v in range(V):
if not mstSet[v] and key[v] < min_val:
min_val = key[v]
min_index = v
return min_index
# 执行 Prim 算法来查找最小生成树 (MST) 的函数
def primMST(graph, parent):
key = [sys.maxsize] * V
mstSet = [False] * V
key[0] = 0
parent[0] = -1
for _ in range(V - 1):
u = findMinKey(key, mstSet)
mstSet[u] = True
for v in range(V):
if graph[u][v] and not mstSet[v] and graph[u][v] < key[v]:
parent[v] = u
key[v] = graph[u][v]
# 打印最小生成树的前序遍历的函数
def printPreorderTraversal(parent):
print("发现树的前序遍历是 − ", end="")
for i in range(1, V):
print(parent[i], " → ", end="")
print()
# 旅行商近似算法的主要功能
def tspApproximation(graph):
parent = [0] * V
root = 0 # 选择顶点 0 作为起点和终点
# 使用 Prim 算法查找最小生成树
primMST(graph, parent)
# 打印最小生成树的前序遍历
printPreorderTraversal(parent)
# 打印汉密尔顿路径（前序遍历，在末尾添加起点）
print("在追踪路径的末尾添加根节点 ", end="")
for i in range(V):
print(parent[i], " → ", end="")
print(root, " → ", parent[0])
# 计算并打印汉密尔顿路径的成本
cost = 0
for i in range(1, V):
cost += graph[parent[i]][i]
# 路径的成本将是最小生成树中所有成本的总和。
print("最小生成树中所有成本的总和：", cost)
if __name__ == "__main__":
# 以邻接矩阵表示的示例图
graph = [
[0, 3, 1, 6, 0, 0],
[3, 0, 5, 0, 3, 0],
[1, 5, 0, 5, 6, 4],
[6, 0, 5, 0, 0, 2],
[0, 3, 6, 0, 0, 6],
[0, 0, 4, 2, 6, 0]
]
tspApproximation(graph)
输出
发现树的前序遍历是 − 0 → 0 → 5 → 1 → 2 → 在追踪路径的末尾添加根节点 -1 → 0 → 0 → 5 → 1 → 2 → 0 → -1 最小生成树中所有成本的总和： 13
