Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 11 kết quả

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

  1. #1
    Ngày gia nhập
    05 2007
    Bài viết
    49

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

    mình có bài toán người du lịch đc chép ở trong sách ra nhưng có phần hàm Try() mình chưa thực sự hiểu rõ lắm và phần hàm init() là hai hàm mình chưa hiểu rõ lắm. Mong các huynh giảng cho mình với
    C Code:
    1. #include <stdlib.h>
    2. #include <stdio.h>
    3. #include <conio.h>
    4. #include <dos.h>
    5. #define index 100;
    6. #define TRUE 1
    7. #define FALSE 0
    8. #define STOP 27
    9. typedef int hanhtrinh[100];
    10. typedef int cuocphi[100][100];
    11. int xp,n,t,min,max;
    12. char ch;
    13. struct time time1;
    14. double t1,t2;
    15. hanhtrinh p,pm;
    16. cuocphi c;
    17. char b[100];
    18. float r;
    19. init()
    20. {
    21.     int i,j;
    22.     for(i=0;i<n;i++)
    23.     {
    24.         b[i]=TRUE;
    25.         p[i]=xp;
    26.     }
    27.     min=c[1][1];
    28.     max=min;
    29.     for(i=0;i<n;i++)
    30.      for(j=0;j<n;j++)
    31.      {
    32.         if(c[i][j]<min)
    33.         min=c[i][j];
    34.         if(c[i][j]>max)
    35.         max=c[i][j];
    36.      }
    37.      printf("min=%d\n",min);
    38.      printf("max=%d\n",max);
    39.      t=n*max;
    40.      printf("t=%d",t);
    41.      b[xp]=FALSE;
    42.      return 0;
    43. }
    44. inkq()
    45. {
    46.     int i;
    47.     printf("\nHanh trinh toi uu:\n");
    48.     for(i=0;i<n;i++)
    49.      printf("%d=>",pm[i]);
    50.     printf("%d\nChi phi:%d",xp,t);
    51.     return 0;
    52. }
    53. nhapdl()
    54. {
    55.     int i,j;
    56.     printf("\nSo thanh pho:");     scanf("%d",&n);
    57.     printf("\nThanh pho xuat phat(0...%d):",n-1);scanf("%d",&xp);
    58.     if((xp<0)||(xp>=n))
    59.     exit(1);
    60.     randomize();
    61.     for(i=0;i<n;i++)
    62.      for(j=0;j<n;j++)
    63.      c[i][j]=random(100);
    64.     for(i=0;i<n;i++)
    65.     c[i][i]=0;
    66.     /*for(i=0;i<n;i++)
    67.      for(j=0;j<n;j++)
    68.      {
    69.       printf("c[%d][%d]=",i,j);scanf("%d",&c[i][j]);
    70.      }*/
    71.     for(i=0;i<n;i++)
    72.      {
    73.         for(j=0;j<n;j++)
    74.         printf("%3d",c[i][j]);printf("\n");
    75.      }
    76.      return 0;
    77. }
    78. Try(int k,int s)
    79. {
    80.     int i,j,tg;
    81.     for(i=0;i<n;i++)
    82.     {
    83.         tg=s+c[p[k-1]][i];
    84.         if((b[i])&&(tg+min*(n-k)<t))
    85.         {
    86.             p[k]=i;
    87.             b[i]=FALSE;
    88.             if((k==n-1)&&(tg+c[i][xp]<t))
    89.             {
    90.                 for(j=0;j<n;j++)
    91.                 pm[j]=p[j];
    92.                 t=tg+c[i][xp];
    93.             }
    94.             else
    95.                 if(k<n-1)
    96.                     Try(k+1,tg);
    97.             b[i]=TRUE;
    98.         }
    99.     }
    100.     return 0;
    101. }
    102. main()
    103. {
    104.     clrscr();
    105.     printf("    BAI TOAN NGUOI DU LICH\n");
    106.     nhapdl();
    107.     init();
    108.     gettime(&time1);
    109.     t1=3600*time1.ti_hour+600*time1.ti_min+100*time1.ti_sec+time1.ti_hund;
    110.     Try(1,0);
    111.     inkq();
    112.     gettime(&time1);
    113.     t2=3600*time1.ti_hour+600*time1.ti_min+100*time1.ti_sec+time1.ti_hund;
    114.     printf("\nTime:%0.4f(s)",(t2-t1)/100);
    115.     getch();
    116. }

  2. #2
    Ngày gia nhập
    11 2007
    Bài viết
    47

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

    Đề bài:
    Cho một mạng lưới gồm n thành phố. Một người muốn đi du lịch khắp các thành phố, mỗi thành phố đi qua đúng một lần và sau đó quay về thành phố xuất phát. Giả sử biết chi phí đi lại giữa các thành phố (0<c[i,j]). Hãy lập trình tìm phương án với tổng chi phí ít nhất.

    Thuật toán:Phương án của bài toán là x[1], x[2].. x[n], x[1]. Trong đó x[1] là đỉnh xuất phát, x là đỉnh thứ i trong hành trình của người du lịch. Lúc đó tổng chi phí S được tính như sau:

    S = a[x[1],x[2]]+ a[x[2],x[3]]+...+ a[x[n-1],x[n]]+ a[x[n],x[1]].

    Trong quá trình xây dựng các thành phần của phương án ta tiến hành đặt nhánh cận như sau:

    Xây dựng thành phần thứ i của phương án (x) ta có tổng chi phí S của i-1 thành phần đã được xây dựng. Thành phần thứ i của phương án phải thoả mãn biểu thức sau:

    S + a[x[i-1], x]+(n-i)*Amin +X1min < Min.

    Trong đó: + Amin là chí phí nhỏ nhất trong bảng chi phí a[i,j].

    + X1min là chi phí nhỏ nhất từ x[1] đến các thành phố còn lại.

    + Min là chi phí của phương án mẫu.

    Chương trình.

    Các biến trong chương trình:

    a:array[1..100,1..100] of integer; chứa bảng chi phí.

    x,y:array[1..100]of 1..100 ; chứa phương án trong quá trình duyệt

    chuaxet:array[1..100]of boolean;chứa trạng thái các thành phố. Nếu thành phố i đã nằm trong phương án đang duyệt->chuaxet=false. ngược lại chuaxet=true. Ban đầu các giá trị của chuaxet được khởi tạo =true.


    Hy vọng qua phần thuật toán, bạn sẽ hiểu init và try của bạn.
    Nguồn:http://www.diendantinhoc.net/

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

    Mấy anh ơi vì sao code bài toán trên chạy không được và nó báo lỗi ở chỗ hàm struct time time1 ; vậy mấy anh coi chỉnh lại dùm em tí

  4. #4
    Ngày gia nhập
    02 2012
    Nơi ở
    everywhere
    Bài viết
    13

    Trích dẫn Nguyên bản được gửi bởi BornIsBAD Xem bài viết
    Mấy anh ơi vì sao code bài toán trên chạy không được và nó báo lỗi ở chỗ hàm struct time time1 ; vậy mấy anh coi chỉnh lại dùm em tí
    đã copy code người ta về còn đòi hỏi

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

    hix , mình làm bài kiểm tra đúng bài này , h copy về mà nó ko chạy , bạn nào giúp mình vs có đòi hỏi gì đâu

  6. #6
    Ngày gia nhập
    01 2012
    Nơi ở
    PTIT
    Bài viết
    0

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

    Mình thấy bài trên code lằng nhằng quá, chẳng muốn đọc
    Còn đây là code của mình, share cho bạn nào thích ( có bạn nào dân PTIT không nhỉ? ):
    Code:
    #include<iostream>
    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    using namespace std;
    int n,c[100][100],x[100],chuaxet[100],kq[100];
    int MIN=0;
    int a=1;
    void Init(){
         cout<<"\n Nhap n="; cin>>n;
         cout<<"\n Nhap chi phi \n";
         for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++){
                 if(i!=j){
                 cout<<"c["<<i<<"]["<<j<<"]="; cin>>c[i][j];
                 }
                 else c[i][j]=0;
                 }
         x[1]=1;
         for(int i=2;i<=n;i++)  chuaxet[i]=1;
    }
    void Result(){
         cout<<"\n T1->";
         for(int i=2;i<=n;i++) cout<<"T"<<kq[i]<<"->";
         cout<<"T1";
         cout<<"\n Tong chi phi la: "<<MIN;
    }
    void Work(){
         int S=0;
         for(int i=1;i<=n-1;i++){
                 S=S+c[x[i]][x[i+1]];
                 }
         S=S+c[x[n]][1];
         if(S<MIN||a==1){ a=0;
                   MIN=S;
                   for(int i=1;i<=n;i++) kq[i]=x[i];
                   }
    }
    void Try(int i){
         for(int j=2;j<=n;j++){
                 if(chuaxet[j]){
                                x[i]=j; chuaxet[j]=0;
                                if(i==n)             Work();
                                else Try(i+1);
                                chuaxet[j]=1;
                                }
                                }
    }
    main(){
           Init();
           Try(2);
           Result();
           getch();
    }

  7. #7
    Ngày gia nhập
    11 2012
    Bài viết
    136

    ( có bạn nào dân PTIT không nhỉ? ):
    có này . Bạn lớp nào vậy.
    Đã được chỉnh sửa lần cuối bởi kimcy1992 : 17-11-2012 lúc 10:55 AM.
    Giao lưu và học hỏi
    https://www.facebook.com/kimcy1992

  8. #8
    Ngày gia nhập
    01 2012
    Nơi ở
    PTIT
    Bài viết
    0

    D11cn1 :d..............
    Hic, giờ mới để ý topic từ năm 2007 :dead:
    Đã được chỉnh sửa lần cuối bởi nam156 : 18-11-2012 lúc 05:18 PM.

  9. #9
    Ngày gia nhập
    11 2012
    Bài viết
    136

    Trích dẫn Nguyên bản được gửi bởi nam156 Xem bài viết
    D11cn1 :d..............
    Hic, giờ mới để ý topic từ năm 2007 :dead:
    Mình C11cn1. topic năm nào cũng được miễn là làm việc tốt hì
    Giao lưu và học hỏi
    https://www.facebook.com/kimcy1992

  10. #10
    Ngày gia nhập
    11 2013
    Bài viết
    1

    Trích dẫn Nguyên bản được gửi bởi nam156 Xem bài viết
    Mình thấy bài trên code lằng nhằng quá, chẳng muốn đọc
    Còn đây là code của mình, share cho bạn nào thích ( có bạn nào dân PTIT không nhỉ? ):
    Code:
    #include<iostream>
    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    using namespace std;
    int n,c[100][100],x[100],chuaxet[100],kq[100];
    int MIN=0;
    int a=1;
    void Init(){
         cout<<"\n Nhap n="; cin>>n;
         cout<<"\n Nhap chi phi \n";
         for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++){
                 if(i!=j){
                 cout<<"c["<<i<<"]["<<j<<"]="; cin>>c[i][j];
                 }
                 else c[i][j]=0;
                 }
         x[1]=1;
         for(int i=2;i<=n;i++)  chuaxet[i]=1;
    }
    void Result(){
         cout<<"\n T1->";
         for(int i=2;i<=n;i++) cout<<"T"<<kq[i]<<"->";
         cout<<"T1";
         cout<<"\n Tong chi phi la: "<<MIN;
    }
    void Work(){
         int S=0;
         for(int i=1;i<=n-1;i++){
                 S=S+c[x[i]][x[i+1]];
                 }
         S=S+c[x[n]][1];
         if(S<MIN||a==1){ a=0;
                   MIN=S;
                   for(int i=1;i<=n;i++) kq[i]=x[i];
                   }
    }
    void Try(int i){
         for(int j=2;j<=n;j++){
                 if(chuaxet[j]){
                                x[i]=j; chuaxet[j]=0;
                                if(i==n)             Work();
                                else Try(i+1);
                                chuaxet[j]=1;
                                }
                                }
    }
    main(){
           Init();
           Try(2);
           Result();
           getch();
    }
    anh còn thiếu trường hợp giữa hai thành phố không có đường đi hay chỉ có một đường đi (cái này nhập vào là 0)

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