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: Cho em hỏi về thuật toán đường đi ngắn nhất của quan mã.

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

    Mặc định Cho em hỏi về thuật toán đường đi ngắn nhất của quan mã.

    Xét bàn cờ có kí ch thước 8x8 ô vuông trên đó có 2 ô đặt tên là s và t. tại ô s người ta đặt một quân mã. người ta muốn tìm cách di chuyển quan mã đến ô t với số nước đi ít nhất. (quân mã di chuyển theo quy luật 1x2).
    Một sinh viên được yêu cầu xây dựng thuật toán để giải bài toán trên anh ta đã thực hiện một thuật toán gán nhãn như sau:
    1. biểu diển bàn cớ bằng một ma trận vuông mà các ô ban đầu đều có giá tri 0.
    2. ô s được gắn nhãn là 1. Gán k=1
    3. lặp lại cho đến khi gắn nhãn được ô t.
    a. với các ô trong bàn cờ chưa được gắn nhãn (=0) kề với ô có nhãn k, gán nhãn k+1
    b. Tăng k=k+1
    Nếu nhãn của t là n thì n-1 chính là số nước di chuyển cần thực hiện
    Câu hỏi:
    -Hãy cài đặt thuật toán trên
    -Nếú trên bàn cờ mà người ta đặt một số ô cấm( nghĩa là đi từ s đến t quân mã ko được đi ô này). Hãy viết lại thuật toán mới.
    Sửa/Xóa bài viết

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

    Bạn bills_khoa chú ý cách đặt câu hỏi nhá, không có post 1 bài rồi không nói 1 tiếng nào như vậy nữa đâu. Muốn được giúp thì phải biết nói cho đúng cách :
    - Bạn suy nghĩ tới đâu
    - Ý tưởng là gì
    - Kẹt chỗ nào
    Quăng cái đề lên như vậy thì không ai giúp bạn đâu !

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

    chào bác! Bài tập của em là quá rõ ràng so với đề bài rồi. E làm ko được và post lên nhờ anh em giúp đỡ.

  4. #4
    Ngày gia nhập
    02 2008
    Bài viết
    21

    Chào bác Rox_rook. Em cần là cần giúp đỡ cách cài đặt cái thuật toán của bài đó. Em cũng đã hỏi rõ ràng trong bài tập rồi.

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

    Câu hỏi:
    -Hãy cài đặt thuật toán trên
    -Nếú trên bàn cờ mà người ta đặt một số ô cấm( nghĩa là đi từ s đến t quân mã ko được đi ô này). Hãy viết lại thuật toán mới.
    Bạn viết 1 câu có chủ ngữ khó đến vậy à ?
    - Bạn suy nghĩ tới đâu
    - Ý tưởng là gì
    - Kẹt chỗ nào
    Bạn đã suy nghĩ thế nào rồi nói tui nghe xem ?

  6. #6
    Ngày gia nhập
    02 2008
    Bài viết
    21

    Mặc định Cho em hỏi về thuật toán đường đi ngắn nhất của quan mã.

    -Theo đề bài thì em có được sự hình dung như vậy và có chút gợi ý của thầy giáo khi dạy là:
    Bài toán có chút manh mối là thế này các bác ah!Giả sử ta biểu diễn bàn cờ bằng một ma trận 8x8 và tất cả ban đầu đều có giá trị là 0.
    -ô S được gán nhãn là k=1
    -Ta lặt đi lặt lại cho đền khi gán nhãn được ô T:
    +với các ô trong bàn cờ chưa được gán nhãn (=0) kề với ô có nhãn k, ta gán k+1
    +Tăng k=k+1
    -Nếu nhãn của T là n thì n-1 là số bước đi.
    Ví dụ ta có hình sau:(mà làm sao em uphinh len đây nhỉ:???Chỉ em với

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

    Lần sau không ghi rõ ra thì tui nhất định không giúp đâu đó. Vào đây coi, thắc mắc gì thì hỏi tiếp, nhớ là suy nghĩ cho kĩ rùi mới hỏi, vì học là học cho cậu chứ không phải cho tui, muốn học chắc thì phải tự suy nghĩ, còn nếu chỉ muốn nộp bài cho thầy thì...

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

    Sorry đọc đề ẩu tả, bài này thì dùng đồ thị tìm đường đi ngắn nhất cũng được tuy nhiên dùng heuristic vẫn ok, với cách đánh giá 1 ô có vị trí đi là xem nó có thể đi được tới bao nhiêu nước khác mà vị trí đó cho các khả năng move tới cái ô khác nữa là thấp nhất. Và cái bài move con mã đi hết bàn cờ của tui làm là dùng heuristic, đọc sơ qua xem có idea gì không!

  9. #9
    Ngày gia nhập
    02 2008
    Bài viết
    21

    tớ không cần mộp bài cho ai hết vì tớ không đi học nữa. Tớ chỉ tranh thủ kiếm thêm chút kiến thức và chia sẻ những gì mình suy nghĩ cùng bạn bè. Mình làm không đc cũng là chuyện thường mà. Nhưng tất cả chúng ta thì sẽ làm được

  10. #10
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Trích dẫn Nguyên bản được gửi bởi bills_khoa Xem bài viết
    -Theo đề bài thì em có được sự hình dung như vậy và có chút gợi ý của thầy giáo khi dạy là:
    Bài toán có chút manh mối là thế này các bác ah!Giả sử ta biểu diễn bàn cờ bằng một ma trận 8x8 và tất cả ban đầu đều có giá trị là 0.
    -ô S được gán nhãn là k=1
    -Ta lặt đi lặt lại cho đền khi gán nhãn được ô T:
    +với các ô trong bàn cờ chưa được gán nhãn (=0) kề với ô có nhãn k, ta gán k+1
    +Tăng k=k+1
    -Nếu nhãn của T là n thì n-1 là số bước đi.
    Ví dụ ta có hình sau:(mà làm sao em uphinh len đây nhỉ:???Chỉ em với
    Tôi không hiểu cái ô kề:
    kề với ô có nhãn k
    Theo tôi cái ô kề theo bạn hiểu chính là ô mà tại k để có thể đi được tới nhãn k+1.
    Cái ý tưởng theo bạn nghĩ chính là mấu chốt cho bài toán Mã đi tuần.
    Bài này tôi làm khi tự đọc linklist( mục đính tôi lưu cấu hình sinh của nó).
    Nhưng cũng khá lâu rồi, chưa có thời gian nghiên cứu lại.
    Hình như trong diễn đàn cũng bàn khá nhiều ( bạn tìm hoặc bài gần đây là knigh's tow ấy)
    Bạn tham khảo bài Mã Đi Tuần này( hiểu bài này bạn có thể làm bài 8 hậu):
    Code:
    #include "conio.h"
    #include "stdio.h"
    #include "stdlib.h"
    #include "graphics.h"
    
    #define MAXX getmaxx()
    #define MAXY getmaxy()
    #define SIZE 50
    #define CL_khung RED
    
    void Fill(int i,int j)//to o ban co
     {
    	if((i+j)%2==0) {
    					 setfillstyle(SOLID_FILL,3);
    					 floodfill(j*SIZE+13,MAXY-i*SIZE-13,WHITE);
    				  }
    			else {
    					 setfillstyle(SOLID_FILL,5);
    					 floodfill(j*SIZE+13,MAXY-i*SIZE-13,WHITE);
    				  }
     }
    
    void ban_co(int a=1)    //ve ban co
     {
    	 int i,j;
    		setcolor(WHITE);
    	for(i=0;i<8;i++)
    		for( j=0;j<8;j++)
    		 {      
                            if(a)
    			rectangle(j*SIZE+10,MAXY-i*SIZE-10,(j+1)*SIZE+10,MAXY-(i+1)*SIZE-10);
    			Fill(i,j);//to o ban co
    		 }
     }
    
    void khung()//ve khung
     {
      //khung va nen
      setcolor(CL_khung);
      rectangle(0,0,MAXX,MAXY);
      setfillstyle(SOLID_FILL,BLACK+BLUE);
      floodfill(1,1,CL_khung);
      //bong do 3D cho ban co
      setfillstyle(1,BLACK+DARKGRAY);
      bar(8*SIZE+10,MAXY-5,8*SIZE+15,MAXY-8*SIZE-5);
      bar(15,MAXY-5,8*SIZE+10,MAXY-10);
     }
    
    //not graphics
    const N=8;
    const soO=64;
    const O_FREE=0;
    const H[8]={-2,-1,1,2, 2, 1,-1,-2};
    const C[8]={ 1, 2,2,1,-1,-2,-2,-1};
    
    int a[12][12];
    unsigned socach=0;
    int dau=2,x0,y0;
    
    void WriteResult()//viet ket qua
    {
      ban_co(0);//ve lai khi nhay sang buoc khac
      int i,j;
      char c[2];
      socach+=1;
      setcolor(BLACK);
      for(i=2;i<10;i++)
    	{
    	  for(j=2;j<10;j++)
    	  outtextxy((j-2)*SIZE+5+SIZE/2,MAXY+(i-2)*SIZE-405+SIZE/2,itoa(a[i][j],c,10));
    	}
       getch();
    }
    
    void Try(int sb,int u,int v)//thu cac buoc chay cua Ma
    {
      int i,x1,y1;
      for(i=0;i<8;i++)
    	{//start for
    		 x1=u+H[i];
    		 y1=v+C[i];
    	  if(a[x1][y1]==O_FREE)
    		  {//start if
    			 a[x1][y1]=sb;
    			  if(sb==soO) WriteResult();
    			  else Try(sb+1,x1,y1);
    			  a[x1][y1]=O_FREE;
    		  }//end if
    	}//end for
    }
    
    void ma_di_tuan(int x,int y)
    {
    	int i,j;
    	for(i=0;i<12;i++)
    	 for(j=0;j<12;j++)
    		a[i][j]=-1;
    	for(i=dau;i<10;i++)
    	 for(j=dau;j<10;j++)
    		a[i][j]=O_FREE;
    	a[x+dau-1][y+dau-1]=1;
    	Try(2,x+dau-1,y+dau-1);
    }
     //function main
    main()
    {
     int d,c;
      printf("\nNhap dong");
       scanf("%d",&d);
      printf("\nNhap cot");
       scanf("%d",&c);
      int mh=DETECT,kieu;
      initgraph(&mh,&kieu,"c:\\tc\\bgi");
      khung();//khung
      ban_co();//ban co
      ma_di_tuan(d,c);
      getch();
      closegraph();
      return 0;
    }
    Còn bài này, theo tôi thêm một vài điều kiện sau:
    1.Tại 'S' bạn làm sao để rút ngắn khoảng cách tới 'T', bằng cách:
    a.So sánh abs(S(x),T(x)) với abs(S(y),T(y))
    Mục đính là tiếp cận với ô 'T' trong khu vực matrix 3x3 ( chứa 'T')
    b.Nếu việc tiếp cận với abs(S(x),T(x)) và abs(S(y),T(y)) == 0 coi như xong.
    Ngược lại ta có vị trí mới ( trong khu vực tiếp cận này) gọi hàm để tìm đường đi ngắn nhất trong khu vực lân cận ( mở rộng ma trận nếu cần thiết) để tìm đường đi ngắn nhất giữa hai cái.
    Hoặc( cách 2):
    2.Bạn lưu hết các cấu hình có thể từ 's' -> 't'
    3.tiến hành tìm cây khung nhỏ nhất( hoặc tìm đường đi ngắn nhất bằng ma trận kề)
    ĐÓ là chút suy nghĩ, tôi sẽ suy nghĩ thêm về nó và bàn luận thêm sau.
    Có gì chưa đúng, xin chỉ giúp.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

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

  1. thuật toán tìm đường đi ngắn nhất(dijkstra)
    Gửi bởi shogun_vn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 04-11-2015, 06:14 PM
  2. Bài toán tìm đường đi ngắn nhất với thuật toán Dijsktra
    Gửi bởi biencuongtq1 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 17-03-2011, 02:51 AM
  3. thuật toán TÌM ĐƯỜNG ĐI NGẮN NHẤT
    Gửi bởi tanchelsea trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 11
    Bài viết cuối: 02-11-2010, 09:31 PM
  4. Bài toán liên quan đến đường đi ngắn nhất.
    Gửi bởi tsandtm trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 11-09-2010, 12:15 AM
  5. Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận
    Gửi bởi hunterphu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 10-08-2010, 12:05 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