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