Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: bài toán du lịch

  1. #1
    Ngày gia nhập
    03 2009
    Bài viết
    2

    Mặc định bài toán du lịch

    có ai có thể giúp mình xem bài này nên làm như thế nào ko?
    "một người du lịch muốn đi tham quang TP T1, T2,....Tn xuất phát từ 1 thành phố nào đó người du lịch muốn đi wa tất cả các TP còn lại, mỗi TP đi wa đúng 1 lần rùi quay về TP xuất phát, cho biết Cij là chi phí đi từ TP Ci đến Cj. Hãy tìm hành trình với tổng chi phí là nhỏ nhất .

  2. #2
    Ngày gia nhập
    04 2008
    Nơi ở
    HCMC
    Bài viết
    251

    Bạn nên tìm hiểu và đọc về đồ thị.Coi thành phố như 1 điểm. Đường đi giữa các thành phố là cạnh.Chiều dài là trọng số.
    C++ Code:
    1. for(;;){cout<<"Busy"<<endl;}
    2. system("cls");
    Hãy ủng hộ cho quỹ phát triển cộng đồng C Việt
    http://congdongcviet.com/quyphattrien-congdongcviet.cpp

  3. #3
    Ngày gia nhập
    03 2009
    Bài viết
    2

    nhưng làm như thế nào để xác định được cạnh nào là ngắn nhất hoặc là xa nhất. làm như thế nào để tính chi phí. ta có cần dùng thuật toán quay luôi ko?

  4. #4
    Ngày gia nhập
    04 2008
    Nơi ở
    HCMC
    Bài viết
    251

    Sử dụng thuật toán Dijkstra bạn ah.Bạn thử search xem nhé.
    C++ Code:
    1. for(;;){cout<<"Busy"<<endl;}
    2. system("cls");
    Hãy ủng hộ cho quỹ phát triển cộng đồng C Việt
    http://congdongcviet.com/quyphattrien-congdongcviet.cpp

  5. #5
    Ngày gia nhập
    03 2009
    Bài viết
    2

    mình chưa học đến đó. có thể sử dụng thuật toán way luôi làm được ko?

  6. #6
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Mặc định bài toán du lịch

    Bài toán người đi du lịch đây bạn, code lâu quá rồi (không nhớ là phải mình code không nữa, vì khi đó thi olympic lâu quá rôi), không nhớ rõ lắm thế nào nữa, bạn xem thử thế nào?
    C++ Code:
    1. #include<iostream.h>
    2. #include<fstream.h>
    3. const max=20;
    4. const maxC=20*100+1;
    5. int C[max][max],x[max],BestWay[max+1],T[max+1],Free[max], MinSpending,m,n;
    6. void enter(){
    7.     int i,j,k;
    8.     ifstream f1("C:\\TOURISM.INP",ios::in);
    9.     f1>>n>>m;
    10.     for (i=1;i<=n;i++)
    11.         for (j=1;j<=n;j++)
    12.             if (i==j) C[i][j]=0;
    13.             else C[i][j]=maxC;
    14.     for (k=1;k<=m;k++){
    15.         f1>>i>>j>>C[i][j];
    16.         C[j][i]=C[i][j];
    17.     };
    18.     f1.close();
    19. };
    20. void init(){
    21.     for (int i=0;i<=n;i++) Free[i]=1;
    22.     Free[1]=0;
    23.     x[1]=1;
    24.     T[1]=0;
    25.     MinSpending=maxC;
    26. };
    27. void Try(int i){
    28.     int j;
    29.     for (j=2;j<=n;j++)
    30.         if (Free[j]==1){
    31.             x[i]=j;
    32.             T[i]=T[i-1]+C[x[i-1]][j];
    33.             if (T[i]<MinSpending)
    34.                 if (i<n){
    35.                     Free[j]=0;
    36.                     Try(i+1);
    37.                     Free[j]=1;
    38.                 }
    39.                 else{
    40.                     if (T[n]+C[x[n]][1]<MinSpending){
    41.                         for(int l=1;l<=n;l++) BestWay[l]=x[l];
    42.                         MinSpending=T[n]+C[x[n]][1];
    43.                     };
    44.                                 };
    45.         };
    46. };
    47. void ghiFile(){
    48.     int i;
    49.     ofstream f2("C:\\TOURISM.OUT",ios::out);
    50.     if (MinSpending==maxC) f2<<"No solution"<<endl;
    51.     else
    52.         for (i=1;i<=n;i++) f2<<BestWay[i]<<"->";
    53.     f2<<"1"<<endl;
    54.     f2<<"Cost: "<<MinSpending<<endl;
    55.     f2.close();
    56. };
    57. void main(){
    58. enter();
    59. init();
    60. Try(2);
    61. ghiFile();
    62. };
    Đã được chỉnh sửa lần cuối bởi Forlorn_hope : 09-03-2009 lúc 11:30 PM.
    Không biết ghi gì luôn ...

  7. #7
    Ngày gia nhập
    03 2009
    Bài viết
    2

    oh thanks bạn nhiều! mà bạn ơi, đoạn code sử dụng = những lệnh gì vậy?
    mình chưa học tới này, nhưng dù sao cũng cảm ôn bạn nhiều!

  8. #8
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Trích dẫn Nguyên bản được gửi bởi chauminhhuy2000 Xem bài viết
    oh thanks bạn nhiều! mà bạn ơi, đoạn code sử dụng = những lệnh gì vậy?
    mình chưa học tới này, nhưng dù sao cũng cảm ôn bạn nhiều!
    Trong code mình gửi chỉ sử dụng những lệnh cơ bản thôi, có lẽ bạn mới đi vào học C++ thì phải?
    Hãy tìm hiểu kỹ từng cú pháp lệnh, rồi đọc hiểu code, debug chạy thử xem thế nào, sẽ giúp bạn hiểu rõ hơn về giải thuật trong chương trình.
    Không biết ghi gì luôn ...

  9. #9
    Ngày gia nhập
    03 2009
    Bài viết
    2

    mình chỉ mơí học có vài tháng thui.

  10. #10
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Trích dẫn Nguyên bản được gửi bởi chauminhhuy2000 Xem bài viết
    mình chỉ mơí học có vài tháng thui.
    Vậy bạn hãy tự xem lại cú pháp lệnh, và post bài thắc mắc tại đây, nhưng không chấp nhận: trường hợp câu lệnh nào bạn cũng hỏi mà không chịu tìm hiểu. Thân!!!
    Không biết ghi gì luôn ...

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn