Kênh dành cho phái đẹp!

Cài đặt code bài toán người du lịch cài đặt bằng C++, Java

articlewriting1

Bài toán người du lịch: Một nguời du lịch muốn đi tham quan n thành phố T1,T2…, Tn. Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua duy nhất 1 lần rối quay trở trở lại thành phố xuất phát.

Gọi Cij là ngân sách đi từ thành phố Ti đến Tj. Hãy tìm một hành trình dài thỏa nhu yếu bài toán sao cho ngân sách là nhỏ nhất .
Hãy cùng Lập trình không khó đi xử lý bài toán này nhé những bạn

Code bài toán người du lịch

Chúng ta sẽ lưu ma trận chi phí đi từ Ti đến Tj là a[i][j]. Như vậy, tại đường chéo của ma trận thì chi phí sẽ bằng 0. Giả sử với ma trận sau:

0123456

intgraph[4][4]={{0,10,15,20},

{10,0,35,25},

{15,35,0,30},

{20,25,30,0}

};

Chúng ta giả sử có 4 thành phố : T0, T1, T2, T3. Như vậy thì hàng tiên phong là ngân sách đi từ T0 đến T0, T1, T2, T3 lần lượt là 0, 10, 15, 20. Tương tự với những hàng phía sau .

Lưu ý: cost = 999999 ngầm hiểu ở đây là khai báo giá trị cost khởi tạo là vô cùng lớn.

Source code C/C++:

012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758

/ *

* C + + Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm

* /

#include

#include

#include

usingnamespacestd;

intc=0,cost=999999;

intgraph[4][4]={{0,10,15,20},

{10,0,35,25},

{15,35,0,30},

{20,25,30,0}

};

voidswap(int*x,int*y)

{

inttemp;

temp=*x;

*x=*y;

*y=temp;

}

voidcopy_array(int*a,intn)

{

inti,sum=0;

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

{

sum+=graph[a[i%4]][a[(i+1)%4]];

}

if(cost>sum)

{

cost=sum;

}

}

voidpermute(int*a,inti,intn)

{

intj,k;

if(i==n)

{

copy_array(a,n);

}

else

{

for(j=i;j<=n;j++)

{

swap((a+i),(a+j));

permute(a,i+1,n);

swap((a+i),(a+j));

}

}

}

intmain()

{

inti,j;

inta[]={0,1,2,3};

permute(a,0,3);

cout<<" minimum cost : "<

getch();

}

> Lời giải tìm hiểu thêm tại : sanfoundry.com
Kết quả chạy :

012
minimum cost : 80

Source code Java:

0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384

85

868788899091929394

importjava.util.InputMismatchException;

importjava.util.Scanner;

importjava.util.Stack;

publicclassTSPNearestNeighbour

{

privateintnumberOfNodes;

privateStackstack;

publicTSPNearestNeighbour()

{

stack=newStack();

}

publicvoidtsp(intadjacencyMatrix[][])

{

numberOfNodes=adjacencyMatrix[1].length-1;

int[]visited=newint[numberOfNodes+1];

visited[1]=1;

stack.push(1);

intelement,dst=0,i;

intmin=Integer.MAX_VALUE;

booleanminFlag=false;

System.out.print(1+” \ t “);

while(!stack.isEmpty())

{

element=stack.peek();

i=1;

min=Integer.MAX_VALUE;

while(i<=numberOfNodes)

{

if(adjacencyMatrix[element][i]>1và và visited [ i ] = = 0 )

{

if ( min > adjacencyMatrix [ element ] [ i ] )

{

min = adjacencyMatrix [ element ] [ i ] ;

dst=i;

minFlag=true;

}

}

i++;

}

if(minFlag)

{

visited[dst]=1;

stack.push(dst);

System.out.print(dst+” \ t “);

minFlag=false;

continue;

}

stack.pop();

}

}

publicstaticvoidmain(String…arg)

{

intnumber_of_nodes;

Scannerscanner=null;

try

{

System.out.println(” Enter the number of nodes in the graph “);

scanner=newScanner(System.in);

number_of_nodes=scanner.nextInt();

intadjacency_matrix[][]=newint[number_of_nodes+1][number_of_nodes+1];

System.out.println(” Enter the adjacency matrix “);

for(inti=1;i<=number_of_nodes;i++)

{

for(intj=1;j<=number_of_nodes;j++)

{

adjacency_matrix[i][j]=scanner.nextInt();

}

}

for(inti=1;i<=number_of_nodes;i++)

{

for(intj=1;j<=number_of_nodes;j++)

{

if(adjacency_matrix[i][j]==1và và adjacency_matrix [ j ] [ i ] = = 0 )

{

adjacency_matrix [ j ] [ i ] = 1 ;

}

}

}

System.out.println(” the citys are visited as follows “);

TSPNearestNeighbourtspNearestNeighbour=newTSPNearestNeighbour();

tspNearestNeighbour.tsp(adjacency_matrix);

}catch(InputMismatchExceptioninputMismatch)

{

System.out.println(” Wrong Input format “);

}

scanner.close();

}

}

> Lời giải tìm hiểu thêm tại : sanfoundry.com

Source: https://ladyfirst.vn
Category: DU LỊCH

Related posts

Lam Visa, Lam Visa gia re, Dich vu Lam Visa, Lam Visa xuat nhap canh

ladybaby

Chia sẻ Kinh nghiệm du lịch Hà Giang tự túc 2020

ladybaby

Khám phá Vườn quốc gia Tràm Chim

ladybaby