Các anh cho em hỏi giờ em có bài toán đi du lịch thế này: 1 người du lịch xuất phát từ thành phố A đến tất cả các thành phố B,C,D rồi quay về A. Chi phí đi lại giữa các thành phố khác nhau là khác nhau. Dùng các mảng 2 chiều ví dụ X[12,10] để thể hiện chi phí du lịch từ thành phố A đến B mất 10 triệu, mảng X[24,5] thể hiện chi phí du lịch từ thành phố B đến D mất 5 triệu... (với quy ước 1 là A, 2 là B, 3 là C và 4 là D) Viết chương trình bằng ngôn ngữ C để tìm cách đi sao cho người đó có thể đi du lịch từ A qua tất cả các thành phố khác và quay lại A với chi phí thấp nhất. Bài này em có 2 chỗ chưa biết làm là: - Làm thế nào có thể cộng dồn chi phí đi từ A đến thành phố D khi đi theo những cách khác nhau (A->B->C->D->A hoặc A->C->B->D->A, ...) - Làm thế nào để so sánh chi phí cộng dồn đó cái nào là thấp nhất Các anh giúp em với, nếu có code của cả bài này thì tốt quá ---------- Post added at 21:18 ---------- Previous post was at 21:11 ---------- Em quên mất đề bài còn có thêm mỗi thành phố chỉ đến 1 lần. Em cám ơn các anh trước!
Bạn tham khảo đoạn code này nhé /* bai toan nguoi du lich ban hang TSP-sd pp nhanh can Input : d1 : so cac thanh pho Cac dong tiep theo ghi matran chi phi giua cac thanh pho (Do thi la do thi day du ) Output : tong hanh trinh nho nhat, va ghi lan luot cac thanh pho trong hanh trinh */ #include<stdio.h> #include<conio.h> #include<stdlib.h> int n,a[20],b[20],T[20]; int c[20][20],dem=0; int sum ,cmin,best; void read_File() { int i,j; FILE *fn; fn=fopen("DuLich.INP","r"); if(!fn) { printf("Loi mo tep\n"); getch(); exit(0); } fscanf(fn,"%d",&n); printf("\n So thanh pho:: %d",n); printf("\n Ma tran chi phi::\n"); for(i=1;i<=n;i++) { printf("\n"); for(j=1;j<=n;j++) { fscanf(fn,"%d",&c[j]); printf("%4d",c[j]); } } } int CPMIN()// tim do dai duong di truc tiep MIN giua 2 dinh cuar Do thi . { int min=1000; int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i!=j && c[j]<min) min=c[j]; } } return min; } int init() { int i; cmin=CPMIN(); best=20000; sum =0; a[1]=1; for(i=1;i<=n;i++) b=1; } void update() { int s = sum +c[a[n]][a[1]]; if(s < best) { //Hanhtrinh(); for(int i=1;i<=n;i++) T=a; // luu lai hanh trinh toi uu nhat hien thoi best=s; // luu lai Tong chi hanh trinh toi uu nhat hien thoi } } void Try(int i)// tim thanh pho thu i trong hanh trinh { int j; for(j=2; j<=n;j++)// duyet tat ca cac pan co the if(b[j] > 0 ) // thanh pho thu j chua dc chon { a=j; b[j]=0; sum = sum+c[a[i-1]][a]; if (i==n) update(); else if( sum + (n-i+1)*cmin< best)// chi di tiep neu nhu thoa man can. { dem++; Try(i+1); } b[j]=1; sum = sum-c[a[i-1]][a]; } } void output() { int i; printf("\n\n\n\n Tong chi phi cua hanh trinh tot nhat la :: %3d",best); printf("\nHanh Trinh:\n"); for(i=1;i<=n;i++) printf(" %3d ->",T); printf(" 1 "); } int main() { read_File(); init() ; Try(2); output(); getch(); }
