Báo cáo trí tuệ nhân tạo tìm ĐƯỜNG mã đi TUẦN TRONG bàn cờ
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (120.04 KB, 6 trang )
TÊN BÀI TẬP: TÌM ĐƯỜNG MÃ ĐI TUẦN TRONG BÀN CỜ.
ĐIỀU KIỆN BÀI TOÁN:
-
Đi mỗi ô 1 lần duy nhất và đi hết tất cả các ô trong bàn cờ.
Kích thước tối thiểu: >50x50.
Thời gian tìm đường tối đa: <5s.
Ý TƯỞNG THUẬT TOÁN:
Ta thấy: Ban đầu số ô chưa đi trên bàn cờ còn nhiều:
-
Tại mỗi ô vị trí giữa trên bàn cờ: con mã có thể đi được tối đa ra 8 vị trí xung quanh. Cụ
thể:
o VD bàn cờ 8x8:
(0,0
)
(x,y
)
(7,7
)
8 điểm:
(x-1,y-2).
(x-2,y-1).
(x+1,y-2).
(x+2,y-1).
(x-2,y+1).
(x-1,y+2).
(x+1,y+2).
(x+2,y+1).
-
Tại mỗi ô ở vị trí biên bàn cờ: con mã chỉ có thể đi tối đa ra 4 vị trí xung quanh. Tại vị trí
mỗi ô ở góc bàn cờ: con mã chỉ đi được tối đa ra 2 vị trí xung quanh. Cụ thể:
o VD bàn cờ 8x8:
(x2,y2
)
(0,0)
(x1,y1
)
(x3,y3
)
-
Tại mỗi ô ở vị trí giáp biên bàn cờ: con mã chỉ đi được tối đa ra 6 vị trí xung quanh. Cụ
thể:
(0,0
)
(x,y
)
(7,7
)
-
-
Ta định nghĩa:
o Ô sống trên bàn cờ: là ô mà tại vị trí đó con mã có thể đi tới ít nhất 1 ô tại vị trí
khác con mã chưa đi trên bàn cờ (giúp ta có thể hạn chế việc đi vào các ô chết).
o Ô chết trên bàn cờ: là ô mà tại vị trí đó con mã không thể đi tới ô nào chưa đi trên
bàn cờ.
Kết luận ý tưởng:
o Như vậy khi con mã tại vị trí ô ở biên hoặc giáp biên trên bàn cờ, ta sẽ có ít lựa
chọn đi cho con mã hơn. Vì vậy khi số ô con mã chưa đi trên bàn cờ ít dần thì ô
tại vị trí biên sẽ dễ là ô chết nhất nếu con mã đi vào. Từ kết luận trên ta đưa ra ý
tưởng: “Cố gắng đi con mã ra vị trí biên hoặc giáp biên trước”.
THUẬT TOÁN CỤ THỂ:
-
Xét trường hợp dẫn tới ô chết: (ô màu trắng : chưa đi). Cụ thể:
(0,0
)
(2,2
)
(1,4
)
(0,6
)
(7,7
)
o Giả sử con mã đang ở vị trí có tọa độ (1,4). Tại đó ta chỉ còn 2 lựa chọn cho con
mã đi tới ô có tọa độ (0,6) và ô có tọa độ (2,2).
Nếu đi tới ô có tọa độ (2,2) trước: khi đó trừ khi ô có tọa độ (0,6) là ô kết
thúc, nếu không khi con mã đi tới ô có tọa độ (0,6) sẽ là ô chết.
Như vậy thuật toán đưa ra là:
-
Tại mỗi bước đi, ta sẽ kiểm tra các vị trí xung quanh con mã có thể đi tới (kiểm tra tương
lại của vị trí kế tiếp). Nếu:
o Gặp 1 vị trí chỉ có duy nhất 1 lựa chọn đi tới 1 vị trí khác. Ta sẽ dừng xét và chọn
ô đó là ô kế tiếp để con mã đi.(Điều này để hạn chế ô chết).
o Ngược lại: nếu không tồn tại ô nào như vậy ta xét tiếp: ô nào tại biên hoặc giáp
biên nhất để đi, dừng xét và đi tới ô đó.
CÀI ĐẶT CỤ THỂ:
-
Để thuận tiện cho việc xét các điểm đi tiếp theo của con mã, ta sẽ cài đặt như sau:
o Với kích thước bàn cờ: NxN, ta sẽ tạo 1 mảng 2 chiều: BanCo[N+4,N+4]. Ô có vị
trí ngoài bàn cờ: set giá trị = -1, ô chưa đi set giá trị =0. Khi đi qua 1 ô, ta sẽ lưu
giá trị ô đó là số thứ tự con mã đi qua. Cụ thể:
Với kích thước 8x8: mảng BanCo[12,12]. Ô bắt đầu (2,3)
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
0
0
0
0
0
0
0
-1
-1
-1
-1
0
0
0
0
0
0
0
0
-1
-1
-1
-1
0
1
0
0
0
0
0
0
-1
-1
-1
-1
0
0
0
0
0
0
0
0
-1
-1
-1
-1
0
0
0
0
0
0
0
0
-1
-1
-1
-1
0
0
0
0
0
0
0
0
-1
-1
-1
-1
0
0
0
0
0
0
0
0
-1
-1
-1
-1
0
0
0
0
0
0
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
o Tiếp theo: tạo 2 mảng ToaDoX [NxN], ToaDoY [NxN] để lưu tọa độ (x,y) tại mỗi
bước đi của con mã.
VD: Thứ tự con mã đi là: Num, tọa độ (x,y): BanCo [x+1,y+1]=Num,
ToaDoX [Num-1]=x-1, ToaDoY [Num-1]=y-1;
o Tạo hàm KiemTra() tại 1 vị trí (ô). Nếu tại vị trí đó, con mã có thể đi tới:
<=1 vị trí khác: KiemTra() = true.
Ngược lại: KiemTra() = fale.
o Tạo hàm StepNext() : tìm vị trí đi tiếp theo của con mã. Nếu:
KiemTra() = = true tại (x1,y1) → NewRow = x1, NewCol = y1, break ;
KiemTra() = = fale. Xét điểm nào gần biên nhất. Giả sử tại (x2,y2) →
NewRow = x2, NewCol = y2.
Num++ ; BanCo [NewRow, NewCol] = Num ;
ToaDoX[Num-1]=NewRow-1;
ToaDoY[Num-1]=NewCol-1;
o Điều kiện dừng:
Có đường đi: Num = = NxN+1;
Hoặc khi không tìm được đường đi: Num! = NxN && NewRow = =0 (do
khi không tìm được điểm nào để đi tiếp thì NewRow = =0)
Giả mã:
int N, Xstart, Ystart, Num=1;
bool Check=fale;
int NewRow= Xstart+1, NewCol= Ystart+1;
While (Num!=NxN+1)
{
BanCo [NewRow, NewCowl]=Num;
ToaDoX [Num-1]=NewRow-2;
ToaDoY [Num-1]=NewCol-2;
StepNext ()
if(Num!=NxN && NewRow = = 0)
{
Check= true;
break;
}
else
Num++;
}
if (Check)
// Không tìm được đường đi.
else
//Tìm được đường đi.
-
Ở đây. Để hạn chế số ô bắt đầu đi mà con mã không tìm được đường đi. Ta thêm các lựa
chọn khác nhau khi chọn con mã đi.
Giả sử cụ thể như sau: Với bàn cờ 8x8:
(2,2
)
o Tại vị trí có tọa độ (2,2) như trên: Ta có thể chọn 1 trong 4 ô đã đánh dấu vì cả 4 ô
đều ở biên. Như vậy cách chọn ô nào ở đây sẽ có thể ảnh hưởng tới kết quả tìm
kiếm. Vì vậy ta cài đặt thêm 1 hàm thay đổi cách chọn ô tiếp theo nếu có các ô có
các tiêu chuẩn chọn trước giống nhau. Có 8 cách chọn khác nhau. Đặt tên hàm là:
RowColChangeNew().
o Thêm vào giả mã như sau:
int dem=0;
if(Num!=NxN && NewRow = = 0 && dem<8)
RowColChangeNew();
else
break.
o Như vậy với bổ sung trên: ta đã hạn chế được số điểm bắt đầu mà không tìm được
đường đi của con mã. Cụ thể theo thực nghiệm số điểm không tìm được đường đi
cho con mã với bàn cờ kích thước:
50x50: 16 điểm.
60x60: 43 điểm.
70x70: 187 điểm.
