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: [ Solved ]Hỏi về thuật toán "Mã đi tuần"

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

    Angry [ Solved ]Hỏi về thuật toán "Mã đi tuần"

    Ai biết thuật toán bài "Mã đi tuần" chỉ cho tớ với. Cám ơn nhiều!
    "Trên bàn cờ quốc tế, quân Mã xuất phát từ vị trí bất kì trên bàn cờ. Hãy chỉ ra cách đi để quân Mã đi qua tất cả các ô trên bàn cờ mà mỗi ô chỉ được đi 1 lần."

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

    Bạn xem link này nhé .

    http://forums.congdongcviet.com/show...u%E1%BA%A7n%22

    Lần sau chịu khó search trước khi post câu hỏi lên diễn đàn bạn nhé.

  3. #3
    Ngày gia nhập
    04 2008
    Bài viết
    336

    Bài này mình tìm thử chu trình đóng của quân mã = hamilton thấy lâu kinh khủng -.-'
    chắc phải biết trước đáp án rồi mới cho chạy và chạy đc. 1 cái thì thoát -.-'
    code ra gió bão

  4. #4
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Mấy cái này dùng trí tuệ nhân tạo quất một phát là xong. 100x100 chạy chừng 2 phút là ra.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

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

    Mấy cái này dùng trí tuệ nhân tạo quất một phát là xong. 100x100 chạy chừng 2 phút là ra.
    - Trí tuệ nhân tạo là môn học mà ? Phải có thuật toán mới đúng chứ nhỉ ?
    - Dùng heuristic cho bài này là rất nhanh đó ! Còn giải thuật nào hay hơn thì nhờ mèo chia sẻ

  6. #6
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Mặc định [ Solved ]Hỏi về thuật toán "Mã đi tuần"

    Đối với một bài toán tìm kiếm có một không gian tìm kiếm rộng như bài này thì dùng heuristic là phương án tối ưu nhất rồi. ăn thua là mình "chế" ra được một Heuristic như thế nào cho nó tối ưu nhất thui. .

    @mèo: có thể chia sẽ cho mọi người cái heuristic của mèo được không? (cái mà 100x100 nó chạy khoảng chừng 2 phút đóa)

  7. #7
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Code này chạy đúng với 81x81 trở xuống, cái code chạy đúng với 100x100 thì mình để đâu mất rồi, đang kiếm lại. Code này chạy trong 1 giây.

    C++ Code:
    1. #include <iostream.h>
    2. #include <stdio.h>
    3. #include <conio.h>
    4.  
    5. #define MAX 81
    6. #define MAXSTEP MAX * MAX      
    7.  
    8.  
    9. typedef struct Cell
    10. {
    11.     int x,y;
    12. } _Cell;
    13.  
    14.  
    15. const int DX[8] = { 2,-2, 2,-2, 1, 1,-1,-1 };
    16. const int DY[8] = { 1, 1,-1,-1, 2,-2, 2,-2 };
    17.  
    18.  
    19. void Print(int board[MAX][MAX]);
    20. int FindAvailable(int board[MAX][MAX],int x,int y,Cell *result);
    21. int MinCase(int board[MAX][MAX],Cell *steparray,int count);
    22.  
    23.  
    24. int main(int argc, char* argv[])
    25. {
    26.     int board[MAX][MAX];
    27.     int x0,y0;
    28.     int stepcount = 0;
    29.     Cell steparray[8];
    30.     int n = 0, index;
    31.     int x, y;
    32.  
    33.     cout<<"Nhap x0 : ";
    34. //  cin>>x0;
    35.     cout<<"Nhap y0 : ";
    36. //  cin>>y0;
    37.  
    38.     cout<<endl<<endl;
    39.  
    40.     x0 = MAX / 2;
    41.     y0 = MAX / 2;
    42.  
    43.     for (y=0;y<MAX;y++)
    44.         for (x=0;x<MAX;x++)
    45.             board[y][x] = 0;
    46.  
    47.     x = x0;
    48.     y = y0;
    49.  
    50.     board[y][x] = ++stepcount;
    51.  
    52.     do
    53.     {
    54.         n = FindAvailable(board,x,y,&steparray[0]);
    55.         if (n > 0)
    56.         {
    57.             index = MinCase(board,&steparray[0],n);
    58.             x = steparray[index].x;
    59.             y = steparray[index].y;
    60.             board[y][x] = ++stepcount;
    61.         }
    62.     }
    63.     while (n > 0 && stepcount < MAXSTEP);
    64.  
    65.     Print(board);
    66.    
    67.     cout<<endl;
    68.     if (stepcount == MAXSTEP)
    69.         cout<<"Thanh cong !"<<endl;
    70.     else
    71.         cout<<"Khong tim duoc loi giai."<<endl;
    72.  
    73.     getch();
    74.     return 0;
    75. }
    76.  
    77. void Print(int board[MAX][MAX])
    78. {
    79.     for (int y=0;y<MAX;y++)
    80.     {
    81.         for (int x=0;x<MAX;x++)
    82.             printf("%03d ",board[y][x]);
    83.         printf("\n");
    84.     }
    85. }
    86.  
    87. int FindAvailable(int board[MAX][MAX],int x,int y,Cell *result)
    88. {
    89.     int count = 0;
    90.     int row, col;
    91.  
    92.     for (int i=0;i<8;i++)
    93.     {
    94.         row = y + DY[i];
    95.         col = x + DX[i];
    96.        
    97.         if (row >= 0 && row < MAX
    98.             && col >= 0 && col < MAX)
    99.             if (!board[row][col])
    100.             {
    101.                 result[count].x = col;
    102.                 result[count].y = row;
    103.                 count++;
    104.             }
    105.  
    106.     }
    107.  
    108.     return count;
    109. }
    110.  
    111. int MinCase(int board[MAX][MAX],Cell *steparray,int count)
    112. {
    113.     Cell result[8];
    114.     int n;
    115.     int min = MAX + 1;
    116.     int ans;
    117.    
    118.     for (int i=0;i<count;i++)
    119.     {
    120.         n = FindAvailable(board,steparray[i].x,steparray[i].y,result);
    121.         if (n < min)
    122.         {
    123.             min = n;
    124.             ans = i;
    125.         }
    126.     }
    127.  
    128.     return ans;
    129. }
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

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

    Đọc code của mèo mù tịt luôn
    mèo có thể giải thích cho zkday 2 câu lệnh này được không?

    C Code:
    1. for (int i=0;i<8;i++)

    ở đây nữa:
    C Code:
    1. Cell result[8];

    Ở đây tại sao lại là 8 mà không phải là MAX nhỉ

    thank mèo trước nhé
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 13-10-2008 lúc 05:19 PM.

  9. #9
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Trích dẫn Nguyên bản được gửi bởi zkday2686 Xem bài viết
    Đọc code của mèo mù tịt luôn
    mèo có thể giải thích cho zkday 2 câu lệnh này được không?

    C Code:
    1. for (int i=0;i<8;i++)

    ở đây nữa:
    C Code:
    1. Cell result[8];

    Ở đây tại sao lại là 8 mà không phải là MAX nhỉ

    thank mèo trước nhé
    Số 8 đó là số cách đi tối đa của con mã : trái, trái trên, trên, phải trên, phải, phải dưới, dưới, trái dưới.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

  10. #10
    Ngày gia nhập
    04 2008
    Bài viết
    336

    meocon ơi thuật toán này chứng minh như thế nào ? tại sao nếu cứ đi vào những nước có số nước đi tiếp theo bé nhất thì có thể đi hết toàn bộ bàn cờ ?
    à thế có cách nào khác ngoài Hamilton để tìm ra 1 chu trình đóng của quân mã ko ?
    code ra gió bão

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

  1. 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
  2. Thắc mắc về "giao diện khả tuần tự trong C#"
    Gửi bởi _adam_ trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 3
    Bài viết cuối: 27-07-2011, 08:10 AM
  3. Problems : " recover tree " with input as " preorder" and "inorder"
    Gửi bởi HoangManhHa1991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 16
    Bài viết cuối: 13-04-2011, 10:19 PM
  4. Bài toán tìm "bao lồi" bằng thuật toán "bọc gói" trên 1 mặt phẳng
    Gửi bởi tvtau trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 17-01-2009, 03:27 PM
  5. [ Solved ]Lỗi "Function "gets" should have a prototype" !
    Gửi bởi hongqb 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: 26-11-2008, 05:45 AM

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