thuật toán cho game xếp số

[ngocquynh85]

bác nào biết cái game xếp số không ?
cho 1 mảng 2 chiều(n*n) các số tu` 1 tới n*n-1 (có nghĩa là có 1 ô trống), và được xăp sếp linh tinh !!
nhiệm vụ của bạn là dùng cái ô trống đó để chuyển các ô chứa số khác về theo thứ tự
1 2 3 4 5
6 7 8 9 10
v.v.v
mong các bác chỉ giúp !!

[CrazyBabe]

Có cần xếp min bước kô zị ? Nếu không cần min thì có thể sử dụng Gen để giải quyết với mảng dữ liệu đủ bé để tổ chức được. Note: bạn viết sai chính tả kìa. :)

[ngocquynh85]

hichic !!
cái này có thuật toán mà !! có cách để xếp giống như chơi rubic đó ! nhung mà tui không nhớ !

[Boy4is]

Cái này hình như đâu có thuật toán tốt ... chỉ có vét cạn mới giải wuyết được trường hợp tìm số bước chuyển ít nhất, còn không phải sử dụng heuristic để tìm kiếm, ví dụ 1 heuristic là trong mỗi bước di chuyển là làm sao nó gần với cấu hình kết thúc nhất ...

[jany2222]

Tùy theo thuật toán mà ta có thể dùng để giải quyết bài toán số. Dạng thuật toán phổ biến nhất là Greedy search (không biết tiếng việt dịch là gì thông cảm nha)
Ví dụ minh họa là cách tốt nhất để hiểu
Giả sử ban đầu các số được sắp xếp như sau
1 2 3
5 6
4 8 7
Và mục đích để sắp xếp các số trên theo thứ tự
1 2 3
4 5 6
7 8

Bước 1: Tử hình cho thấy
1 2 3
5 6
4 8 7
khỏang trống nẳm ở giữa và ta có thể di chuyển được khỏang trống lên, xuống, trái và phải cho nên ta có thể biết trứơc 4 trửơng hợp có thể xảy ra.
Di chuyển khỏang trống lên trên
1 3
5 2 6
4 8 7

Di chuyển khỏang trống xuống dưới
1 2 3
5 8 6
4 7

Di chuyển khỏang trống sang phải
1 2 3
5 6
4 8 7

Di chuyển khỏang trống sang trái
1 2 3
5 6
4 8 7

Bước 2: Xem xét coi những vị trí của những bước trên so với ví trí của đích đến có gần nhau hay không.Ví dụ
1 3
5 2 6
4 8 7
với
1 2 3
4 5 6
7 8


Vị trí của các số 2,5,4,8,7 không khớp nhau do đó khỏang cách tử
1 3
5 2 6
4 8 7
đến
1 2 3
4 5 6
7 8
là f = h = 5

Lần lược thử với các bước
1 2 3
5 8 6
4 7

1 2 3
5 6
4 8 7

1 2 3
5 6
4 8 7

so với
1 2 3
4 5 6
7 8

Với các kết quả tuần tự là 4, 4, 3
Ta nhận thấy
1 2 3
5 6
4 8 7

so với
1 2 3
4 5 6
7 8
là gần nhất 3 là số nhỏ nhất (đại điện cho quảng đường ngắn nhất để đến đìch) cho nên ta chọn bước
1 2 3
5 6
4 8 7

để phân tích tiếp.
Ở bước này ta nhận thấy khỏang trống chỉ có thể di chuyển lên xuống và sang phải. Nhưng vì sang phải sẻ lập lại bước ban đầu cho nên ta bỏ qua. Chỉ còn 2 vị trí di chuyển là lên và xuống
2 3
1 5 6
4 8 7

và
1 2 3
4 5 6
8 7

Áp dụng kỷ thuật trên ta nhận thấy
1 2 3
4 5 6
8 7
f = h = 2
so với đích đến gẩn hơn
2 3
1 5 6
4 8 7
f = h = 4

Ta chon
1 2 3
4 5 6
8 7

phan tich tiep cho den khi tim ra dich den.
Grreed Search algorithm có thể tham khảo tại đây
http://www.cs.toronto.edu/~mitchell/ai-course/s2.html

[duyvu931984]

Bac Jany2222 trinh bay 1 so cho chua dung(hoi kho hieu:tu vi tri ban dau chi co the den 3 vi tri sao lai la 4?!!!)
va :Nhung neu bai toan khong co loi giai, se duyet the nao?

[jany2222]

Sorry mình nhằm lẩn trong cái này có lẻ tại làm lẹ quá. Thông cảm nha.

[haison3000]

CÁi này hiện nay chưa có thuật toán tốt. Chỉ có dùng search với heuristic thui. Còn greedy algorithm thì chưa chắc là tối ưu.