資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究旅行商問題
一名銷售人員在一家城市中，他必須訪問其他所有列出的城市，同時也提供了從一個城市到另一個城市旅行的成本。找到一條成本最低的路線，以訪問所有城市一次並返回他的出發城市。
對於這種情況，圖表必須是完整的，因此銷售人員可以直接從任何城市到任何城市。
在這裡，我們必須找到加權最小的哈密頓環。
輸入和輸出
Input: Cost matrix of the matrix. 0 20 42 25 30 20 0 30 34 15 42 30 0 10 10 25 34 10 0 25 30 15 10 25 0 Output: Distance of Travelling Salesman: 80
演算法
travellingSalesman (mask, pos)
有一張表格 dp，VISIT_ALL 值用於標記所有訪問過的節點
輸入 − 掩碼值，用於掩蓋一些城市，位置。
輸出減號；找出訪問所有城市的最快路線。
Begin if mask = VISIT_ALL, then //when all cities are visited return cost[pos, 0] if dp[mask, pos] ≠ -1, then return dp[mask, pos] finalCost := ∞ for all cities i, do tempMask := (shift 1 left side i times) if mask AND tempMask = 0, then tempCpst := cost[pos, i] + travellingSalesman(mask OR tempMask, i) finalCost := minimum of finalCost and tempCost done dp[mask, pos] = finalCost return finalCost End
示例
#include<iostream>
#define CITY 5
#define INF 9999
using namespace std;
int cost[CITY][CITY] = {
{0, 20, 42, 25, 30},
{20, 0, 30, 34, 15},
{42, 30, 0, 10, 10},
{25, 34, 10, 0, 25},
{30, 15, 10, 25, 0}
};
int VISIT_ALL = (1 << CITY) - 1;
int dp[16][4]; //make array of size (2^n, n)
int travellingSalesman(int mask, int pos) {
if(mask == VISIT_ALL) //when all cities are marked as visited
return cost[pos][0]; //from current city to origin
if(dp[mask][pos] != -1) //when it is considered
return dp[mask][pos];
int finalCost = INF;
for(int i = 0; i<CITY; i++) {
if((mask & (1 << i)) == 0) { //if the ith bit of the result is 0, then it is unvisited
int tempCost = cost[pos][i] + travellingSalesman(mask | (1 << i), i); //as ith city is visited
finalCost = min(finalCost, tempCost);
}
}
return dp[mask][pos] = finalCost;
}
int main() {
int row = (1 << CITY), col = CITY;
for(int i = 0; i<row; i++)
for(int j = 0; j<col; j++)
dp[i][j] = -1; //initialize dp array to -1
cout << "Distance of Travelling Salesman: ";
cout <<travellingSalesman(1, 0); //initially mask is 0001, as 0th city already visited
}輸出
Distance of Travelling Salesman: 80
更新時間：2020-06-17
1000+ 次瀏覽
廣告