旅行商問題（貪心演算法）

Table of content
上一頁
下一頁

旅行商問題是一個圖計算問題，其中推銷員需要只訪問一次列表中的所有城市（用圖中的節點表示），並且已知所有這些城市之間的距離（用圖中的邊表示）。這個問題需要找到的解是推銷員訪問所有城市並返回原城市的最短路線。

如果您檢視下面的圖表，假設推銷員從頂點“a”開始，他們需要遍歷所有剩餘的頂點b、c、d、e、f並返回“a”，同時確保成本最小。

salesman_graph

有各種方法可以找到旅行商問題的解決方案：樸素方法、貪心方法、動態規劃方法等。在本教程中，我們將學習如何使用貪心方法解決旅行商問題。

旅行推銷員演算法

正如貪心方法的定義所述，我們需要找到區域性最優解來找出全域性最優解。演算法的輸入是圖G{V, E}，其中V是頂點集，E是邊集。從一個頂點開始返回同一頂點的圖G的最短路徑作為輸出獲得。

演算法

  • 旅行商問題將圖G{V, E}作為輸入，並宣告另一個圖作為輸出（例如G'），該圖將記錄推銷員從一個節點到另一個節點的路徑。

  • 該演算法首先將輸入圖G中的所有邊從最短距離到最長距離排序。

  • 選擇的第一個邊是最短距離的邊，兩個頂點之一（例如A和B）是起點節點（例如A）。

  • 然後，在除起點節點（B）之外的節點的相鄰邊中，找到成本最低的邊並將其新增到輸出圖中。

  • 繼續使用其他節點進行此過程，確保輸出圖中沒有迴圈，並且路徑返回到起點節點A。

  • 但是，如果問題中提到了起點，則解決方案必須始終從該節點開始。讓我們看一些示例問題以更好地理解這一點。

示例

考慮以下具有六個城市及其之間距離的圖 -

graph_six_cities

從給定的圖中，由於起點已提及，因此解決方案必須始終從該節點開始。在從A引出的邊中，A→B距離最短。

graph a to b

然後，B→C具有最短且唯一的邊，因此將其包含在輸出圖中。

graph_b_to_c

C→D之間只有一條邊，因此將其新增到輸出圖中。

graph_c_to_d

D有兩條外向邊。即使D→B的距離小於D→E，B也已經訪問過一次，如果新增到輸出圖中，它將形成一個迴圈。因此，D→E被新增到輸出圖中。

graph d to e

從e只有一條邊，即E→F。因此，它被新增到輸出圖中。

graph e to f

同樣，即使F→C的距離小於F→A，為了避免形成迴圈並且C已經訪問過一次，F→A被新增到輸出圖中。

graph f to a

從A開始並以A結束的最短路徑是A→B→C→D→E→F→A

路徑的成本是：16 + 21 + 12 + 15 + 16 + 34 = 114。

即使從其他節點開始可以降低路徑成本，但問題並沒有就此提出。

示例

下面給出了使用貪心方法的旅行商問題的完整實現 -

C C++ Java Python
#include <stdio.h>
int tsp_g[10][10] = {
   {12, 30, 33, 10, 45},
   {56, 22, 9, 15, 18},
   {29, 13, 8, 5, 12},
   {33, 28, 16, 10, 3},
   {1, 4, 30, 24, 20}
};
int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */
void travellingsalesman(int c){
   int k, adj_vertex = 999;
   int min = 999;
   
   /* marking the vertices visited in an assigned array */
   visited[c] = 1;
   
   /* displaying the shortest path */
   printf("%d ", c + 1);
   
   /* checking the minimum cost edge in the graph */
   for(k = 0; k < n; k++) {
      if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
         if(tsp_g[c][k] < min) {
            min = tsp_g[c][k];
            adj_vertex = k;
         }
      }
   }
   if(min != 999) {
      cost = cost + min;
   }
   if(adj_vertex == 999) {
      adj_vertex = 0;
      printf("%d", adj_vertex + 1);
      cost = cost + tsp_g[c][adj_vertex];
      return;
   }
   travellingsalesman(adj_vertex);
}

/* main function */
int main(){
   int i, j;
   n = 5;
   for(i = 0; i < n; i++) {
      visited[i] = 0;
   }
   printf("Shortest Path: ");
   travellingsalesman(0);
   printf("\nMinimum Cost: ");
   printf("%d\n", cost);
   return 0;
}

輸出

Shortest Path: 1 4 5 2 3 1
Minimum Cost: 55

#include <iostream>
using namespace std;
int tsp_g[10][10] = {{12, 30, 33, 10, 45},
{56, 22, 9, 15, 18},
{29, 13, 8, 5, 12},
{33, 28, 16, 10, 3},
{1, 4, 30, 24, 20}
};
int visited[10], n, cost = 0;

/* creating a function to generate the shortest path */
void travellingsalesman(int c){
   int k, adj_vertex = 999;
   int min = 999;
   
   /* marking the vertices visited in an assigned array */
   visited[c] = 1;
   
   /* displaying the shortest path */
   cout<<c + 1<<" ";
   
   /* checking the minimum cost edge in the graph */
   for(k = 0; k < n; k++) {
      if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
         if(tsp_g[c][k] < min) {
            min = tsp_g[c][k];
               adj_vertex = k;
         }
      }
   }
   if(min != 999) {
      cost = cost + min;
   }
   if(adj_vertex == 999) {
      adj_vertex = 0;
      cout<<adj_vertex + 1;
      cost = cost + tsp_g[c][adj_vertex];
      return;
   }
   travellingsalesman(adj_vertex);
}

/* main function */
int main(){
   int i, j;
   n = 5;
   for(i = 0; i < n; i++) {
      visited[i] = 0;
   }
   cout<<"Shortest Path: ";
   travellingsalesman(0);
   cout<<"\nMinimum Cost: ";
   cout<<cost;
   return 0;
}

輸出

Shortest Path: 1 4 5 2 3 1
Minimum Cost: 55

import java.util.*;
public class Main {
    static int[][] tsp_g = {
	   {12, 30, 33, 10, 45},
       {56, 22, 9, 15, 18},
       {29, 13, 8, 5, 12},
       {33, 28, 16, 10, 3},
       {1, 4, 30, 24, 20}};
    static int[] visited;
    static int n, cost;
    public static void travellingsalesman(int c) {
        int k, adj_vertex = 999;
        int min = 999;
        visited[c] = 1;
        System.out.print((c + 1) + " ");
        for (k = 0; k < n; k++) {
            if ((tsp_g[c][k] != 0) && (visited[k] == 0)) {
                if (tsp_g[c][k] < min) {
                    min = tsp_g[c][k];
					adj_vertex = k;
                }
            }
        }
        if (min != 999) {
            cost = cost + min;
        }
        if (adj_vertex == 999) {
            adj_vertex = 0;
            System.out.print((adj_vertex + 1));
            cost = cost + tsp_g[c][adj_vertex];
            return;
        }
        travellingsalesman(adj_vertex);
    }
    public static void main(String[] args) {
        int i, j;
        n = 5;
        visited = new int[n];
        Arrays.fill(visited, 0);
        System.out.print("Shortest Path: ");
        travellingsalesman(0);
        System.out.print("\nMinimum Cost: ");
        System.out.print(cost);
    }
}

輸出

Shortest Path: 1 4 5 2 3 1
Minimum Cost: 55

import numpy as np
def travellingsalesman(c):
    global cost
    adj_vertex = 999
    min_val = 999
    visited[c] = 1
    print((c + 1), end=" ")
    for k in range(n):
        if (tsp_g[c][k] != 0) and (visited[k] == 0):
            if tsp_g[c][k] < min_val:
                min_val = tsp_g[c][k]
                adj_vertex = k
    if min_val != 999:
        cost = cost + min_val
    if adj_vertex == 999:
        adj_vertex = 0
        print((adj_vertex + 1), end=" ")
        cost = cost + tsp_g[c][adj_vertex]
        return
    travellingsalesman(adj_vertex)
n = 5
cost = 0
visited = np.zeros(n, dtype=int)
tsp_g = np.array([[12, 30, 33, 10, 45],
                  [56, 22, 9, 15, 18],
                  [29, 13, 8, 5, 12],
                  [33, 28, 16, 10, 3],
                  [1, 4, 30, 24, 20]])
print("Shortest Path:", end=" ")
travellingsalesman(0)
print()
print("Minimum Cost:", end=" ")
print(cost)

輸出

Shortest Path: 1 4 5 2 3 1 
Minimum Cost: 55
列印頁面
上一頁
下一頁
廣告
© . All rights reserved.