TXT

# Travel c++

By Deborah Miller,2014-05-05 10:58
18 views 0
Travel c++

#include <iostream.h>

#define M 10

#define N 5

int a[2][M] = {{5,4,1,1,1,1,3,2,4,2},{3,2,5,4,2,3,4,3,5,5}},L[M] =

{3,4,4,9,10,10,11,13,16,20}; int s[N],d0 = 9999,d = 0,deep = N,temp = 0;

int judge() //判断是否构成H回路。

{

int temps[N],i;

for (i = 0 ; i < N ; i++)

{

temps[i] = 0;

}

for (i = 0 ; i < N ; i++)

{

temps[a[0][s[i]] - 1]++;

temps[a[1][s[i]] - 1]++;

}

for (i = 0 ; i < N ; i++)

{

if (temps[i] > 2)

{

return 0;

}

}

if (d < d0)

{

d0 = d;

for (i = 0 ; i < N ; i++)

{

cout<<a[0][s[i]]<<a[1][s[i]]<<" ";

}

cout<<"d0 = "<<d0<<endl;

return 1;

}

return 0;

}

void DeepSearch()

{

d = d - L[s[deep - 1]];

s[deep - 1] = s[deep - 1] + 1;

d = d + L[s[deep - 1]];

judge();

}

/*int BackStack()

{

}*/

void main()

{

int i,t;

for (i = 0 ; i < N ; i++)

{

s[i] = i;

d = d + L[s[i]];

}

judge();

while (1)

{

temp = s[N-1];

while(M - temp > 1) //step 3

{

DeepSearch();

temp++;

}

deep--;

while (deep)

{

t = deep;

if (s[deep - 1] < deep + 4) //确保有足够多的边加入s？否则退栈。

{

d = d - L[s[deep - 1]];

s[deep - 1] = s[deep - 1] + 1;

d = d + L[s[deep - 1]];

while (deep < N)

{

d = d - L[s[deep]];

s[deep] = s[deep - 1] + 1;

d = d + L[s[deep]];

deep++;

}

if (d > d0) //d > d0 退栈？剪枝。否则go to step 3;

{

deep = t - 1;

}

else

{

break;

}

}

else

{

deep--;

}

}

if (deep == 0) // 栈控退出；

{

break;

}

}

}

Report this document

For any questions or suggestions please email
cust-service@docsford.com