Translate these C++ code into Matlab (Traveling Saleman Problem)
Show older comments
This is about TSP. I use all permutation (n! case) to find the minum sum path and the order. Please help me to translate this C++ code to Matlab in detailed code.
#include <bits/stdc++.h>
using namespace std;
#define V 7 //in below example: 7 location
vector<int> result;
// implementation of traveling Salesman Problem
int travllingSalesmanProblem(int graph[][V], int s)
{
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
// store minimum weight Hamiltonian Cycle.
int min_path = INT_MAX;
do {
// store current Path weight(cost)
int current_pathweight = 0;
// compute current path weight
int k = s;
for (int i = 0; i < vertex.size(); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
}
current_pathweight += graph[k][s];
// update minimum
if (current_pathweight < min_path){
min_path = current_pathweight;
result = vertex;
}
} while (next_permutation(vertex.begin(), vertex.end()));
return min_path;
}
// driver program to test above function
int main()
{
// matrix representation of graph
int graph[][V] = { { 0, 6, 13, 8, 13, 21, 14 },
{ 6, 0, 7, 10, 11, 15, 14 },
{ 13, 7, 0, 11, 12, 8, 15 },
{ 8, 10, 11, 0, 7, 13, 6 },
{ 13, 11, 12, 7, 0, 8, 3 },
{ 21, 15, 8, 13, 8, 0, 10 },
{ 14, 14, 15, 6, 3, 10, 0 } };
//record the order
int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl;
cout << s + 1 << " ";
for (int x:result)
cout << x + 1 << " ";
cout<< s + 1 << endl;
return 0;
}
Thank you so much.
Answers (0)
Categories
Find more on Traveling Salesman (TSP) in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!