Code thuật toán nhánh cận người du lịch

//bai toan nguoi du lich su dung ky thuat danh gia nhanh can

#include

int a[5][5]={

                {0,15,30,50,20},

                {15,0,10,35,32},

                {30,10,0,15,40},

                {50,35,15,0,43},

                {20,32,40,43,0}

}// ma tran ke vo huong co trong so

,n;// so luong dinh

bool b[5]={false};// mang danh dau

int kq[10],bestConfig[10]={0};// mang tam, va mang luu cau hinh tot nhat

int min=32000,cost=0;// gia tri thap nhat khi di qua cac dinh va gia tri tam

int start;// dinh bat dau

void Try(int i);

void Output()// ham xuat cac gia tri

{

                for(int i=0;i

                {

                                cout<";

                }cout<

                cout<<"Chi phi: "<

}

void main()

{

                n=5;

                //cout<<"Vi tri ban dau: ";

                start=3;//cin>>start;

                start–;

                kq[0]=start;b[start]=true;

                Try(1);// bat dau goi tu dinh dau tien di,khi bang n thi dung

                Output();

}

void Try(int i)

{

                //neu i == n thi kiem tra de xem phai la cau hinh tot hon thi luu lai

                if(i==n)

                {

                                if(cost+a[kq[i-1]][kq[0]]

                                {

                                                min=cost+a[kq[i-1]][kq[0]];

                                                for(int k=0; k < n;k++)

                                                                bestConfig[k]=kq[k];

                                }

                }

                else

                {

                                for(int j=0;j

                                {

                                                // neu chua di qua va gia tri con cho phep

                                                if(b[j]==false && cost+a[kq[i-1]][j] < min)

                                                {

                                                                //ghi nho lai ket qua

                                                                kq[i]=j;

                                                                b[j]=true;

                                                                cost+=a[kq[i-1]][j];

                                                                //goi de qui den buoc tiep theo

                                                                Try(i+1);

                                                                //xoa bo ghi nho

                                                                b[j]=false;

                                                                cost-=a[kq[i-1]][j];

                                                }

                                }

                }

}