动态规划解决TSP问题

制定行动计划，分步骤解决问题 #生活常识# #职场技巧# #解决问题#

题目描述

某推销员要从城市 v1 出发，访问其它城市v2，v3，…，v6 各一次且仅一次，最后返回v1。D为各城市间的距离矩阵。
问：该推销员应如何选择路线，才能使总的行程最短？

                                   

#include<stdio.h>

#include<stdlib.h>

#define NODE_NUMBER 6

int D[NODE_NUMBER][NODE_NUMBER] =

{ 0,10,20,30,40,50,

12,0,18,30,25,21,

23,19,0,5,10,15,

34,32,4,0,8,16,

45,27,11,10,0,18,

56,22,16,20,12,0

};

int Path[6][6];

int cost[6][6] = {

1000,1000,1000,1000,1000,1000,

1000,1000,1000,1000,1000,1000,

1000,1000,1000,1000,1000,1000,

1000,1000,1000,1000,1000,1000,

1000,1000,1000,1000,1000,1000,

1000,1000,1000,1000,1000,1000

};

int TSP(int step,int node ,int S)

{

int min = 10000;

int tmp = 10000;

int next_node=1;

int min_node;

if (step == 6) {

return D[node][0];

}

for (int i = 1; i <=16 ; i *= 2) {

int t = S & i;

if (t == i) {

tmp = D[node][next_node] + TSP(step +1, next_node, S - i);

if (min > tmp)

{

min = tmp;

min_node = next_node;

}

}

next_node++;

}

if (min < cost[step][node]) {

Path[step][node] = min_node;

cost[step][node] = min;

}

return min;

}

int main()

{

int next_node;

int ShortestDistance;

ShortestDistance=TSP(1,0,31);

printf("The Shortest distance is：%d\n",ShortestDistance);

printf("The best Path is: 1 ");

next_node = 0;

for (int i = 1; i <= 5; i++) {

printf("%d ", Path[i][next_node]+1);

next_node = Path[i][next_node];

}

printf("1 \n");

system("pause");

}

'

网址：动态规划解决TSP问题 https://www.yuejiaxmz.com/news/view/488487

相关内容

旅行商问题（动态规划方法，超级详细的）
TSP
动态规划问题dp问题以及经典问题
算法动态规划01背包问题
旅行商问题+背包问题
动态规划之最大子段和问题
动态规划问题最少费用问题 C++版本
动态规划
旅游路线规划：用数学建模优化旅行体验
超详细！动态规划详解分析（典型例题分析和对比，附源码）

随便看看