使用近似演算法的旅行商問題

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

列印頁面

上一個

下一個