使用近似算法的旅行商问题

Table of content

旅行商近似算法
实施

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

因此，期望近似解能够找到此 NP-Hard 问题的近似最优解。但是，只有当问题中的成本函数（定义为两个绘图点之间的距离）满足三角不等式时，才会设计近似算法。

只有当成本函数 c 对于三角形 u、v 和 w 的所有顶点都满足以下等式时，才满足三角不等式

                 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

打印页面

上一个

下一个