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ố 12 kết quả

Đề tài: Các giải thuật cho mã đi tuần?

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mặc định Các giải thuật cho mã đi tuần?

    Đang làm bài mã đi tuần , sử dụng quay lui + cầm canh . Nhưng vẫn còn dài dòng lắm , và tốn rất nhiều thời gian . Không biết anh em có giải thuật nào hay hơn không nhỉ ?

    Kid thử dùng heuristic xem ! Knight move vào ô có xác xuất ít nhất !

    C++ Code:
    1. #include <iostream>
    2. #include <iomanip>
    3. #include <conio.h>
    4.  
    5. using namespace std;
    6.  
    7. const int size = 8;
    8. void Possible();
    9. void Heuristic(int);
    10.  
    11. const int ver[]={-1,-2,-2,-1,1,2,2,1},
    12.           hor[]={2,1,-1,-2,-2,-1,1,2};
    13.  
    14. int row, col;
    15.        
    16. int board[size][size];
    17. int choice[8][8][8];
    18. int accessible[8][8];
    19. int main()
    20. {
    21.  
    22.     int count = 1,k,j;
    23.  
    24.     cout <<"position [from (0,0) to (7,7)]:";
    25.     cin  >> row >> col;
    26.     cout << endl;
    27.  
    28.     board[row][col]=count;
    29.  
    30.  
    31.     while(count!=size*size)
    32.     {
    33.         count++;
    34.         Possible();
    35.         Heuristic(count);
    36.         for(j=0;j<=7;j++)
    37.         {
    38.             for(k=0;k<=7;k++)
    39.                 cout <<  setw(3) << accessible[j][k];
    40.             cout <<"\t";
    41.             for(k=0;k<=7;k++)
    42.                 cout <<  setw(3) << board[j][k];
    43.             cout <<"\n\n";
    44.         }
    45.  
    46.         cout <<"\n\n";        
    47.     }
    48.     for(j=0;j<=size-1;j++)
    49.     {
    50.         for(k=0;k<=size-1;k++)
    51.                     cout <<  setw(3) << board[j][k];
    52.         cout <<"\n\n";
    53.     }
    54.    
    55.         system("pause");
    56.         return 0;
    57.  
    58. }
    59. void Possible()
    60. {
    61.     int next_pos;
    62.     for(int r=0;r<=size-1;r++)
    63.     {
    64.  
    65.         for(int c=0;c<=size-1;c++)
    66.         {
    67.             next_pos = 0;
    68.            
    69.             for(int i=0;i<=7;i++)
    70.             {
    71.                 if(((r+ver[i] >=0) && (r+ver[i] <=size-1))&&((c+hor[i] >=0) && (c+hor[i] <=size-1))&&(board[r+ver[i]][c+hor[i]] == 0))
    72.                 {
    73.                    
    74.                     choice[r][c][next_pos] = i;
    75.                     next_pos++;
    76.                 }
    77.             }
    78.             accessible[r][c] = next_pos;    
    79.         }
    80.     }
    81.  
    82.      
    83. }
    84. void Heuristic ( int move )
    85. {
    86.         int min =  accessible[row+ver[choice[row][col][0]]][col+hor[choice[row][col][0]]];
    87.     int r   =  row+ver[choice[row][col][0]],
    88.             c   =  col+hor[choice[row][col][0]];
    89.  
    90.     for(int i=1; i < accessible[row][col]; i++)
    91.         {  
    92.         if( min >= accessible[row+ver[choice[row][col][i]]][col+hor[choice[row][col][i]]] )
    93.         {
    94.             min = accessible[row+ver[choice[row][col][i]]][col+hor[choice[row][col][i]]];
    95.             r = row + ver[choice[row][col][i]];
    96.             c = col + hor[choice[row][col][i]];
    97.         }
    98.     }    
    99.         cout <<"\n min ="<<min <<"  ("<<r<<','<<c<<") \n";
    100.        
    101.                 board[r][c] = move;
    102.         row = r;
    103.         col = c;
    104.  
    105. }
    tự tìm hiểu đi nhé !

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Code mã đi tuần viết bằng C++ thuật giải giống nhánh cận

    À, mình còn 1 bài này nữa ! Do lúc trước nghiên cứu bài này cũng nhiều ^_^! Cái này mình thấy giống nhánh cận ! Ý tưởng cũng là chọn bước move có ít khả năng nhất nhưng kết hợp với quay lùi và đánh giá bước move !
    C++ Code:
    1. #include<iostream>
    2. #include<iomanip>
    3. #include<conio.h>
    4. #include<stdio.h>
    5.  
    6. using std::cout;
    7. using std::cin;
    8. using std::endl;
    9. using std::setw;
    10.  
    11.  
    12. /* Knight Tour */
    13. const int maxx = 100;
    14.  
    15. int size;
    16. int K[maxx][maxx], access[maxx][maxx];
    17.  
    18.  
    19. int SUB_ROW[8], SUB_COL[8];
    20. int ver[] = {+2, -1, -1, -2, -2, +1, +1, +2};
    21. int hor[] = {-1, +2, -2, -1, +1, -2, +2, +1};
    22. int row, col,times;
    23.  
    24. bool CHECK ( int row, int col )
    25. {
    26.         if ( row > size-1 || row < 0 || col > size-1 || col < 0 || K[row][col] != 0 )
    27.                 return false;
    28.         else
    29.                 return true;
    30. }
    31. void PRINT()
    32. {
    33.         for ( int i = 0; i < size; i++ )
    34.         {        
    35.                 for ( int j = 0; j < size; j++ )
    36.                     cout << setw(3) << K[i][j] ;
    37.                 cout << "\n";
    38.         }
    39.         cout << "----------------------------" << endl;
    40.         getch();
    41. }  
    42.  
    43. void swap(int &a, int &b)
    44. {
    45.     int temp = a;
    46.     a = b;
    47.     b = temp;  
    48. }
    49.  
    50. void HEURISTIC( int row, int col, int &step, int ORDER[8] )
    51. {
    52.         int poss_row, poss_col; /* Gia su nhung kha nang cua ROW va COL */
    53.      
    54.         /* BAT DAU SINH BANG ACCESSIBILITY */
    55.         for ( int i = 0; i < size; i++)
    56.         {
    57.                 for ( int j = 0; j < size; j++)
    58.                 {
    59.                         access[i][j] = 0;
    60.                         for (int k = 0; k < size; k++)
    61.                         {
    62.                                 poss_row = i + ver[k];
    63.                                 poss_col = j + hor[k];
    64.                                 if ( CHECK(poss_row, poss_col) )
    65.                                         access[i][j]++;
    66.  
    67.                         }  
    68.                 }
    69.         }
    70.         /* KET THUC SINH BANG */
    71.        
    72.         int ROW_I, ROW_II;
    73.         int COL_I, COL_II;
    74.        
    75.          
    76.         /* BAT DAU KHOI TAO GIA TRI CHO SUB_ROW[] va SUB_COL[] */  
    77.        
    78.         step = 0; /* THE MOST IMPORTANT */
    79.        
    80.         for ( int i = 0; i < 8; i++)
    81.         {
    82.                 poss_row = row + ver[i];
    83.                 poss_col = col + hor[i];
    84.                      
    85.                     if ( CHECK(poss_row, poss_col) )
    86.                     {
    87.                             SUB_ROW[step] = poss_row;
    88.                             SUB_COL[step] = poss_col;
    89.                             ORDER[step] = step; /* Luu lai trang thai cua Row va Col */
    90.                             step++;
    91.                     }
    92.         }
    93.         /* KET THUC */
    94.        
    95.         /* SO SANH CHON RA BUOC NHAY TOI UU NHAT */
    96.         for ( int i = 0; i < step ; i++)
    97.         {
    98.                 for ( int j = i + 1; j < step; j++)
    99.                 {
    100.                         ROW_I  = SUB_ROW[ORDER[i]];
    101.                         COL_I  = SUB_COL[ORDER[i]];
    102.                         ROW_II = SUB_ROW[ORDER[j]];
    103.                         COL_II = SUB_COL[ORDER[j]];
    104.                        
    105.                             if (access[ROW_I][COL_I] > access[ROW_II][COL_II])
    106.                                       swap(ORDER[i], ORDER[j]);
    107.                 }
    108.         }
    109.         /*---------------------------------------------------*/
    110. }      
    111. void Knight (int times, int row, int col)
    112. {
    113.     int ORDER[8];
    114.     int moves = 0;
    115.     int next_row, next_col;
    116.    
    117.         K[row][col] = times + 1;
    118.      
    119.         while ( times != size*size )
    120.         {
    121.                 PRINT();
    122.                 HEURISTIC(row, col, moves, ORDER);
    123.                
    124.                 for ( int i = 0; i < moves; i++)  
    125.                 {
    126.                         next_col = SUB_COL[ORDER[i]];
    127.                         next_row = SUB_ROW[ORDER[i]];
    128.                         if (CHECK(next_row, next_col ))
    129.                                   Knight ( times + 1, next_row, next_col);
    130.                 }
    131.         }
    132. }
    133. int main()
    134. {
    135.         cout << " Enter the size of board: "; cin >> size;
    136.         cout << " Enter [row,col] ";          cin  >> row >> col;
    137.        
    138.         Knight (0, row, col);
    139.         system("pause");
    140.         return 0;
    141. }

  3. #3
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Không biết bài này dựa vào cái gì để làm hàm Heuristic là tốt nhất ?

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Không biết bài này dựa vào cái gì để làm hàm Heuristic là tốt nhất ?
    . Ý của Hailoc là gì nhỉ ? theo mình nghĩ thì heuristic là mình chỉ áp dụng thôi! Còn tại sao dùng heuristic lại được thì mình nghĩ cái này thuộc về toán học ! Hình như trên từ điển bk toàn thư có nói về vấn đề này cũng hay lắm ! Mà hồi đó mình nhớ Hailoc có post cho mình 1 bài của tác giả nào đó CM về giải thuật Knight khá hay ! Hailoc check thử xem !

  5. #5
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Theo em được đọc thì khi duyệt qua các trạng thái, tương đương với chọn nước đi tiếp theo của con mã trong bài này, ta dùng hàm heuristic (hàm đánh giá ) để chọn ra được nước đi tốt nhất. Để biết nước nào là "tốt hơn " so với nước nào ta phải có một tiêu chuẩn để đánh giá giữa các nước. Việc chọn tiêu chuẩn là rất quan trọng, nó sẽ quyết định tính hiệu quả của heuristic. Ý em muốn hỏi là đối với bài toán này, chọn tiêu chuẩn nào sẽ mang lại hiệu quả cao nhất ( phải duyệt ít nhất )

  6. #6
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Các giải thuật cho mã đi tuần?

    À hiểu ý em rồi !Theo anh thì Heuristic mang hiệu quả cao nhất rồi ! Vì nó chỉ đi qua mỗi 1 ô 1 lần ! Còn lại việc so sánh bước move ! Anh nghĩ cái này chính là tiêu chuẩn mà em nói ! Hồi trước lúc làm đệ qui khi nhập lộn thứ tự các bước move ( ví dụ const int ver[]={-1,-2,-2,-1,1,2,2,1},
    hor[]={2,1,-1,-2,-2,-1,1,2};
    mà em đổi thành { 1,2,2,1,-1,-2,-2-1 } ...tức là thứ tự có thay đổi thì thời gian chạy ra kết quả cũng thay đổi theo ! Nhưng làm cách này thì ít thấy được sư khác biệt lắm ! nếu em dùng đệ qui thì sẽ thấy ngay thôi ! Cho nên vấn đề giải thuật chỉ là so sánh và chọn bước move thôi! Cái này thì anh không dám chắc là cách so sánh trên có phải là tốt nhất hay không! Còn việc move vào ô các xác xuất ít nhát thì theo anh cái này là tối ưu ( chỉ theo suy nghĩ anh thôi )! Nếu có thời gian thì anh em mình cùng bàn về cái này!
    Đã được chỉnh sửa lần cuối bởi rox_rook : 09-07-2007 lúc 09:44 AM.

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    C++ Code:
    1. #include "stdafx.h"
    2. #include "iostream.h"
    3. #include "conio.h"
    4. #include "col_conio.cpp"
    5. #include "col_conio.h"
    6.  
    7. #include "process.h"
    8.  
    9. //using namespace std;
    10.  
    11. /*
    12.     Chuong Trình : Mã Ði Tu?n
    13.     Gi?i Thu?t   : Ð? Qui + Quay Lui
    14.     Mô T?       :
    15.     -------------------- -----------------------
    16.     T?i m?t v? trí trên bàn c?:
    17.  
    18.                  C?t   
    19.         -------------------------
    20.         |   | x1|   | x2|   |   |
    21.         -------------------------
    22.         | x8|   |   |   | x3|   |
    23.         -------------------------
    24. Hàng   |   |   | M |   |   |   |
    25.         -------------------------
    26.         | x7|   |   |   | x4|   |
    27.         -------------------------
    28.         |   | x6|   | x5|   |   |
    29.         -------------------------
    30.  
    31.         Mã ( M( Hàng, C?t )  ) có th? di du?c 8 hu?ng khác nhau .
    32.         Các v? trí có th? d?n du?c dánh d?u là x(1->8).
    33.         Trong dó t?a d? các v? trí ph? thu?c Hàng C?t c?a M .
    34.  
    35.         Bây gi? ta s? s? d?ng Quay Lui d? duy?t l?n lu?t các hu?ng
    36.         có th? di c?a con mã ( M ) . Ð? d?t mã M t?i ví trí nào dó
    37.         thì t?i v? trí dó ph?i thu?c trong bàn c? ,và T?i dó con mã
    38.         chua t?ng di qua .
    39.         Ta s? s? d?ng các bi?n nhu sau :
    40.         + ChessBoard[n][n] : Ð? luu các giá tr? mã dã di qua trên bàn c?
    41.         + Number : Ð? xem th? M dã di qua du?c bao nhiêu ô trên bàn c? (< n*n)
    42.         + Row[n] : Ð? luu d?a ch? các hàng có th? di d?n t? M.
    43.         + Col[n] : Tuong t? nhung là giá tr? c?t .
    44.  
    45.         Ð? gi?m thi?u dk , ta s? s? d?ng ki thu?t c?m canh nhu v?y :
    46.         +chessBoard[n+4][n+4]
    47.        
    48. */
    49. int n;
    50. int chessBoard[12][12];
    51. int number;
    52. int row[8]={-2,-1,1,2,2,1,-1,-2};
    53. int col[8]={1,2,2,1,-1,-2,-2,-1};
    54. /********************************
    55.     Kh?i d?ng cho bàn c? .
    56.     Các ô chua di qua , s? ô di qua = 0,
    57.     và giá tr? chi?u dài,r?ng c?a b.c?
    58. **********************************/
    59. void initialize()
    60. {
    61.    
    62.     n=12;
    63.     // Kh?i t?o các giá tr? ban d?u theo kt c?m canh
    64.     for(int i=0;i<n;i++)
    65.         for(int j=0;j<n;j++)
    66.         {  
    67.             if( i>=2 && i< 10 && j>=2 && j<10 )
    68.                 chessBoard[i][j]=0;
    69.             else
    70.                 chessBoard[i][j]=-1;
    71.  
    72.         }
    73. }
    74. /***********************************
    75.     Hàm Show dùng d? in các bu?c trong
    76.     quá trình d? qui.
    77. ***********************************/
    78.  
    79. void Show()
    80. {
    81.     system("cls");
    82.     for(int i=2;i<n-2;i++)
    83.     {
    84.         cout<<"|";
    85.         for(int j=2;j<n-2;j++)
    86.         {
    87.             if(chessBoard[i][j] == 0)
    88.                 cout<<"   "<<"|";
    89.             else
    90.                 cout<<chessBoard[i][j]<<"|";
    91.         }
    92.         cout<<endl;
    93.         cout<<"|";
    94.         for(j=2;j<n-2;j++)
    95.         {
    96.            
    97.                 cout<<"---"<<"|";
    98.  
    99.         }
    100.         cout<<endl;
    101.        
    102.     }
    103. //  getch();
    104.     Sleep(5000);
    105.  
    106. }
    107. /***********************************
    108.     Thông báo k?t qu? ra ngoài .
    109. ***********************************/
    110.  
    111.  
    112. void Try(int step,int i,int j)
    113. {
    114.     int hang,cot;
    115.    
    116.     for(int v=0;v<8;v++)
    117.         {
    118.             // Cac Buoc Nhay :
    119.             hang=i+row[v];
    120.             cot=j+col[v];
    121.             if(chessBoard[hang][cot] == 0 )
    122.             {
    123.                 if(step +1 == 64)
    124.                 {
    125.                     chessBoard[hang][cot]= step+1;
    126.                     Show();
    127.                     chessBoard[hang][cot]= 0;
    128.  
    129.                 }
    130.                
    131.                 else
    132.                 {
    133.                     chessBoard[hang][cot]= step+1;
    134.                     Try(step+1,hang,cot);
    135.                     chessBoard[hang][cot]= 0;
    136.    
    137.                 }
    138.            
    139.             }
    140.            
    141.            
    142.            
    143.         }
    144. }
    145. void main()
    146. {
    147.     initialize();
    148.     chessBoard[2][2]=1;
    149.     Try(1,2,2);
    150.     cout<<" Ket Thuc"<<endl;
    151.  
    152. }

    Chậc đệ qui như rox_ rock nói thì là đoạn code trên , anh em nhìn sơ qua thôi chứ chạy thì có nhiều cái còn vướng mắt lắm . Kid thấy cũng vướng nữa nhưng bận quá chưa sửa được .

    Nghe phong phanh đâu là dùng chu trình Haminton gì đó là giải cái này gọn nhất . Nhưng chưa biết về nó . Anh em cứ tiếp tục nhé .

  8. #8
    Ngày gia nhập
    04 2007
    Bài viết
    16

    Tìm chu trình Hamilton là bài toán người du lịch nổi tiếng, code ngắn nhưng thời gian chạy rất lâu vì tư tưởng chủ đạo là vét cạn và đặt cận, ngoài ra còn cách dùng ngẫu nhiên để giải nhưng không ổn định về mặt thời gian, tuy nhiên trong đa số trường hợp thì độ phức tạp là chấp nhận được. Nội dung bài toán có thể được phát biểu vắt tắt: một người du lịch muốn đi vòng quanh tất cả các thành phố đúng 1 lần và trở lại thành phố đầu tiên, mỗi thành phố nếu có đường nối với nhau thì là đường nối 2 chiều và một lượng $ nào đó để đi qua. Hãy tìm hành trình cho người du lịch đó sao cho chi phí phải trả là ít nhất.
    Bài toán mã đi tuần là tiêu biểu của đệ quy quay lui. Đây là một trong những phương pháp hữu hiệu nhất rồi mà.

  9. #9
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Đệ qui quay lui + kĩ thuật cầm canh thì kid làm được rồi . Nhưng nghe nói là dùng haminton thì hay hơn nên mới hỏi thử , tưởng đâu còn kĩ thuật nào hay hơn chứ . Tiếc nhỉ .

  10. #10
    Ngày gia nhập
    02 2011
    Bài viết
    7

    mình đang học về đệ quy,cũng có bài tập này nhưng không hiểu thuật giải của nó thế nào?
    mọi người có thể tường minh thuật giải bài này được không ?
    nhân đây cho mình hỏi chút,
    đoạn code trên
    dòng này nghĩa là sao?
    row[8]={-2,-1,1,2,2,1,-1,-2};
    col[8]={1,2,2,1,-1,-2,-2,-1};
    cám ơn mọi người !

Các đề tài tương tự

  1. Thuật toán Thuật toán tìm chu kỳ của số hữu tỷ vô hạn tuần hoàn.
    Gửi bởi hoailam911 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 11
    Bài viết cuối: 21-08-2013, 06:37 AM
  2. Diễn giải thuật toán để giải "Mã đi tuần"
    Gửi bởi kenshin trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 15
    Bài viết cuối: 12-12-2012, 04:15 PM
  3. Giải thuật đếm tuần suất các kí tự có trong 1 file .txt
    Gửi bởi silkworm trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 26
    Bài viết cuối: 06-05-2011, 08:18 PM
  4. Mã đi tuần | Quy tắc và thuật toán trong lập trình C#?
    Gửi bởi sasadudu trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 23-12-2010, 09:50 PM
  5. lưu đồ giải thuật bài mã đi tuần thuật toán quay lui vét cạn. Giúp mình với?
    Gửi bởi katemat000 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 05-01-2010, 10:53 PM

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