作业 3 穷举法
题目 1：旅行者问题
(1)算法实现的伪代码
(2)程序执行过程分析
测试用例 1： 输入:n=4,m=2
list[4]={1,2,3,4}
d[4][4]={0 10 30 15
10 0 20 40
30 20 0 35
15 40 35 0 }
输出:80
2 1 4 3 2
input :two int n、m, an array list[n] about number of citys and a array d[n][n] with
distance:city i->j
output:the shortest distance sum and the line :m ->m of the shortest distance(contain
all citys)
begin
do Perm(list, 0, n - 1);
function Perm(int *list,k,n)
if k=n and list[0]=m then
for i=0;i<n;i++ do tsum += d[list[i]-1][list[i + 1]-1];
tsum += d[list[n]-1][list[0]-1];
if tsum < sum then
sum=tsum;
for i=0;i<=n;i++ do line[i] = list[i];
line[n+1]=list[0];
else
for i=k;i<=n;i++ do
Swap(list[k], list[i]);
Perm(list, k + 1, n);
Swap(list[k], list[i]);
return;
function Swap(int &i,int &j)
do
temp = i;
i = j;
j = temp;
return;
