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

[bills_khoa]

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

[rox_rook]

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 !

[bills_khoa]

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 đỡ.

[bills_khoa]

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.

[rox_rook]

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 ?

[bills_khoa]

-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

[rox_rook]

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ì...

http://forums.congdongcviet.com/showthread.php?t=5869

[rox_rook]

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!

[bills_khoa]

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

[NT_OnlyLove]

-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):

#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.