旅行推销员近似算法

我们已经使用贪心和动态规划方法讨论了旅行商问题，并且确定在多项式时间内解决旅行商问题以获得完美的最优解是不可能的。

因此，近似解有望找到该 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}

分析

如果满足三角不等式，旅行商问题的逼近算法就是2-逼近算法。

为了证明这一点，我们需要证明问题的近似成本是最优成本的两倍。支持这一说法的观察结果如下：

最小生成树的成本永远不会小于最优哈密顿路径的成本。即，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。

例子

C C++ Java Python

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define V 6 // Number of vertices in the graph
// Function to find the minimum key vertex from the set of vertices not yet included in 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;
}
// Function to perform Prim's algorithm to find the Minimum Spanning Tree (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];
            }
        }
    }
}
// Function to print the preorder traversal of the Minimum Spanning Tree
void printPreorderTraversal(int parent[]) {
    printf("The preorder traversal of the tree is found to be − ");
    for (int i = 1; i < V; i++) {
        printf("%d → ", parent[i]);
    }
    printf("\n");
}
// Main function for the Traveling Salesperson Approximation Algorithm
void tspApproximation(int graph[V][V]) {
    int parent[V];
    int root = 0; // Choosing vertex 0 as the starting and ending point
    // Find the Minimum Spanning Tree using Prim's Algorithm
    primMST(graph, parent);
    // Print the preorder traversal of the Minimum Spanning Tree
    printPreorderTraversal(parent);
    // Print the Hamiltonian path (preorder traversal with the starting point added at the end)
    printf("Adding the root node at the end of the traced path ");
    for (int i = 0; i < V; i++) {
        printf("%d → ", parent[i]);
    }
    printf("%d → %d\n", root, parent[0]);
    // Calculate and print the cost of the Hamiltonian path
    int cost = 0;
    for (int i = 1; i < V; i++) {
        cost += graph[parent[i]][i];
    }
    // The cost of the path would be the sum of all the costs in the minimum spanning tree.
    printf("Sum of all the costs in the minimum spanning tree %d.\n", cost);
}
int main() {
    // Example graph represented as an adjacency matrix
    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;
}

输出

The preorder traversal of the tree is found to be − 0 → 0 → 5 → 1 → 2 → 
Adding the root node at the end of the traced path -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 // Number of vertices in the graph
// Function to find the minimum key vertex from the set of vertices not yet included in 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;
}
// Function to perform Prim's algorithm to find the Minimum Spanning Tree (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];
            }
        }
    }
}
// Function to print the preorder traversal of the Minimum Spanning Tree
void printPreorderTraversal(int parent[]) {
    std::cout << "The preorder traversal of the tree is found to be − ";
    for (int i = 1; i < V; i++) {
        std::cout << parent[i] << " → ";
    }
    std::cout << std::endl;
}
// Main function for the Traveling Salesperson Approximation Algorithm
void tspApproximation(int graph[V][V]) {
    int parent[V];
    int root = 0; // Choosing vertex 0 as the starting and ending point
    // Find the Minimum Spanning Tree using Prim's Algorithm
    primMST(graph, parent);
    // Print the preorder traversal of the Minimum Spanning Tree
    printPreorderTraversal(parent);
    // Print the Hamiltonian path (preorder traversal with the starting point added at the end)
    std::cout << "Adding the root node at the end of the traced path ";
    for (int i = 0; i < V; i++) {
        std::cout << parent[i] << " → ";
    }
    std::cout << root << " → " << parent[0] << std::endl;
    // Calculate and print the cost of the Hamiltonian path
    int cost = 0;
    for (int i = 1; i < V; i++) {
        cost += graph[parent[i]][i];
    }
    // The cost of the path would be the sum of all the costs in the minimum spanning tree.
    std::cout << "Sum of all the costs in the minimum spanning tree: " << cost << "." << std::endl;
}
int main() {
    // Example graph represented as an adjacency matrix
    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;
}

输出

The preorder traversal of the tree is found to be − 0 → 0 → 5 → 1 → 2 → 
Adding the root node at the end of the traced path -1 → 0 → 0 → 5 → 1 → 2 → 0 → -1
Sum of all the costs in the minimum spanning tree: 13.

import java.util.Arrays;
public class TravelingSalesperson {
    static final int V = 6; // Number of vertices in the graph
    // Function to find the minimum key vertex from the set of vertices not yet included in 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;
    }
    // Function to perform Prim's algorithm to find the Minimum Spanning Tree (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];
                }
            }
        }
    }
    // Function to print the preorder traversal of the Minimum Spanning Tree
    static void printPreorderTraversal(int parent[]) {
        System.out.print("The preorder traversal of the tree is found to be  ");
        for (int i = 1; i < V; i++) {
            System.out.print(parent[i] + " -> ");
        }
        System.out.println();
    }
    // Main function for the Traveling Salesperson Approximation Algorithm
    static void tspApproximation(int graph[][]) {
        int parent[] = new int[V];
        int root = 0; // Choosing vertex 0 as the starting and ending point
        // Find the Minimum Spanning Tree using Prim's Algorithm
        primMST(graph, parent);
        // Print the preorder traversal of the Minimum Spanning Tree
        printPreorderTraversal(parent);
        // Print the Hamiltonian path (preorder traversal with the starting point added at the end)
        System.out.print("Adding the root node at the end of the traced path ");
        for (int i = 0; i < V; i++) {
            System.out.print(parent[i] + " -> ");
        }
        System.out.println(root + "  " + parent[0]);
        // Calculate and print the cost of the Hamiltonian path
        int cost = 0;
        for (int i = 1; i < V; i++) {
            cost += graph[parent[i]][i];
        }
        // The cost of the path would be the sum of all the costs in the minimum spanning tree.
        System.out.println("Sum of all the costs in the minimum spanning tree: " + cost);
    }
    public static void main(String[] args) {
        // Example graph represented as an adjacency matrix
        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);
    }
}

输出

The preorder traversal of the tree is found to be  0 -> 0 -> 5 -> 1 -> 2 -> 
Adding the root node at the end of the traced path -1 -> 0 -> 0 -> 5 -> 1 -> 2 -> 0  -1
Sum of all the costs in the minimum spanning tree: 13

import sys
V = 6  # Number of vertices in the graph
# Function to find the minimum key vertex from the set of vertices not yet included in 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
# Function to perform Prim's algorithm to find the Minimum Spanning Tree (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]
# Function to print the preorder traversal of the Minimum Spanning Tree
def printPreorderTraversal(parent):
    print("The preorder traversal of the tree is found to be − ", end="")
    for i in range(1, V):
        print(parent[i], " → ", end="")
    print()
# Main function for the Traveling Salesperson Approximation Algorithm
def tspApproximation(graph):
    parent = [0] * V
    root = 0  # Choosing vertex 0 as the starting and ending point
    # Find the Minimum Spanning Tree using Prim's Algorithm
    primMST(graph, parent)
    # Print the preorder traversal of the Minimum Spanning Tree
    printPreorderTraversal(parent)
    # Print the Hamiltonian path (preorder traversal with the starting point added at the end)
    print("Adding the root node at the end of the traced path ", end="")
    for i in range(V):
        print(parent[i], " → ", end="")
    print(root, " → ", parent[0])
    # Calculate and print the cost of the Hamiltonian path
    cost = 0
    for i in range(1, V):
        cost += graph[parent[i]][i]
    # The cost of the path would be the sum of all the costs in the minimum spanning tree.
    print("Sum of all the costs in the minimum spanning tree:", cost)
if __name__ == "__main__":
    # Example graph represented as an adjacency matrix
    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)

输出

The preorder traversal of the tree is found to be − 0  → 0  → 5  → 1  → 2  → 
Adding the root node at the end of the traced path -1  → 0  → 0  → 5  → 1  → 2  → 0  →  -1
Sum of all the costs in the minimum spanning tree: 13