Bài toán (hay game) n-puzzle có lẽ rất quen thuộc với chúng ta cũng như những người mới bắt đầu tiếp cận với môn trí tuệ nhân tạo. Nó được biết đến với nhiều phiên bản và tên gọi khác nhau như 8-puzzle, 15-puzzle, Gem puzzle, Boss puzzle, Game of Fifteen, Mystic Square,… Ở mức độ đơn giản tôi xin nói về 8-puzzle.
Bài toán gồm một bảng 3×3 với các ô số được đánh từ 1->8 và một ô trống. Ở trạng thái bắt đầu, các ô được sắp đặt ngẫu nhiên, và nhiệm vụ của người giải là tìm cách đưa chúng về đúng thứ tự kiểu lợp ngói (lớn dần từ trái qua phải và từ trên xuống) như minh họa dưới:
Để đơn giản trong cách tiếp cận giải bài toán, người ta giả định chỉ có ô trống trong bảng là di chuyển đến những vị trí khác. Như vậy tại một trạng thái thì chỉ có tối đa 4 cách đi để chuyển sang trạng thái khác (trái, phải, lên, xuống). Người ta cũng nhận ra được rằng để có thể chuyển từ 1 trạng thái bất kì về trạng thái đích như trên thì trạng thái đầu đó phải theo một quy luật mà tôi trình bày sau đây.
Cho trạng thái đầu tiên như hình dưới, duyệt qua từng ô theo thứ tự từ trái qua và từ trên xuống, ở mỗi ô số duyệt đến, bạn hãy đếm xem có bao nhiêu ô số có giá trị bé hơn nó.
- Đầu tiên là ô số 4, ta thấy có 3 ô số {1;3;2} nằm phía sau và bé hơn nó nên n1 = 3
- Tiếp đến là ô số 8 có 6 ô nhỏ hơn là {1;6;3;2;7;5}, vậy n2 = 6
- Ô số 1 là bé nhất nên n3=0
- Tương tự ô số 6, n4=3
- Ô số 3, n5=1
- Ô số 2, n6=0
- Ô số 7, n7=1
- Ô cuối luôn bằng 0 nên có thể bỏ qua, n8=0
Tính tổng các số từ n1->n8 ta có:
N = 3 + 6 + 0 + 3 + 1 + 0 + 1 + 0 = 14
Với số N này ta chỉ cần biết 1 thông tin là nó có chia hết cho 2 hay không (lẻ hay chẵn). Nếu nó là số chẵn thì chắc chắn có thể chuyển về trạng thái đích từ trạng thái hiện tại này. Bởi vì khi di chuyển ô trống với hướng đi bất kì thì giá trị N mod 2 cũng không thay đổi. Tức là từ trạng thái đích bạn có thể xáo trộn bằng cách di chuyển ô trống nhiều lần thì giá trị N vẫn là số chẵn.
15-puzzle
Khá ổn thỏa với bài toán 8-puzzle, ta thử phân tích tiếp bài toán 15-puzzle. Và bất ngờ bạn gặp phải vấn đề khi kiểm tra theo cách tương tự như với bài toán 8-puzzle: Khi di chuyển ô trống trong bảng giữa các dòng và tính toán giá trị N thì bạn nhận ra rằng N sẽ thay đổi giá trị chẵn, lẽ.
15-puzzle
Ví dụ như các bảng phía trên bạn tính được N tương ứng khi di chuyển ô trống giữa các dòng lần lượt là 60, 59, 60, 61. Qua vài lần thử bạn có thể nhận ra quy luật là N là lẻ khi ô trống nằm ở các dòng lẻ tính từ trên xuống (dòng đầu tiên là 1), và N là chẵn khi ô trống nằm ở các dòng chẵn tính từ trên xuống.
Sự khác biệt này so với phiên 8-puzzle là do độ dài cạnh (n) khác nhau. Tức là với n lẻ thì giá trị N mod 2 sẽ ko thay đổi, với n thì thì nó sẽ thay đổi tương ứng với vị trí dòng của ô trống trên bảng.
Ta đã so sánh và nhận thấy là không thể áp dụng cùng quy luật của bài toán 8-puzzle để kiểm tra xem bài toán có thể giải được không. Phân tích lại bài toán 8-puzzle bạn có thể vẫn thắc mắc tại sao việc di chuyển ô trống giữa hai dòng lại không làm thay đổi tính chẵn lẻ của N.
Thử chuyển bảng 3×3 này dạng mảng 1 chiều rồi hình dung việc di chuyển ô trống giữa các hàng.
Như trong bảng 3×3 khi di chuyển ô trống lên phía trên tức là hoán vị ô thứ 3 và ô thứ 6. Tạm thời không quan tâm đến ô trống, ta chỉ xét ô có giá trị 1, dãy trên chuyển thành như sau:
Giá trị N ban đầu được tăng lên 2 là do hiện tại có thêm hai ô lớn hơn nằm trước ô có giá trị 1. Nếu thử vài lần bạn có thể thấy khi di chuyển ô trống giữa các dòng thì giá trị N mới sẽ có 1 trong 3 trường hợp: không thay đổi, tăng 2, giảm 2. Ta có nhận xét: giá trị N mới tăng giảm ±1 với số lần chẵn.
Tương tự với n=4 ta có:
Di chuyển ô trống giữa các dòng trong 15-puzzle
- L1: Việc di chuyển ô số 6 xuống vị trí cuối làm giảm N đi 2 đơn vị (do đứng sau ô 3 và 5) và tăng N lên 1 đơn vị (do đứng sau ô số 9). Ta được N = N – 1 – 1 + 1.- L2: di chuyển ô số 4 xuống vị trí 12 tăng N lên 2 đơn vị (đứng sau ô 14 và 10) và giảm N 1 đơn vị (do đứng sau ô số 1). Ta được N = N +1 +1 – 1.- L3: Tương tự N = N + 1 +1 – 1.
Tức là mỗi lần ô trống giữa các dòng ta chỉ làm thay đổi giá trị N đi 1 đơn vị. Nếu thử với các trường hợp khác, giá trị N có thể thay đổi 3 đơn vị. Nhận xétgiá trị N mới tăng giảm ±1 với số lần lẻ.
Với hai ví dụ trên ta nhận ra một quy luật là: Khi thay đổi vị trí ô trống giữa các dòng thì giá trị N sẽ thay đổi tương ứng với giá trị là số lẻ hay số chẵn tùy thuộc vào n. Tổng quát lên chính là n-1 cũng là giá trị tối đa mà N có thể thay đổi.
Cuối cùng ta suy ra phương pháp tổng quát để áp dụng cho mọi n.
- Với n lẻ:
- Chỉ cần N mod 2 = 0
- Với n chẵn:
- N mod 2 = 0 và ô trống nằm trên dòng chẵn tính từ trên xuống.
- N mod 2 = 1 và ô trống nằm trên dòng lẻ tính từ trên xuống.
Cuối cùng ta giải quyết được vấn đề đầu tiên là: xác định được một n-puzzle có thể chuyển về trạng thái đích với số lần di chuyển bất kì hay không. Việc biết điều này rất quan trọng khi ta đưa ra một trạng thái bắt đầu có thể giải được không.
0 nhận xét:
Đăng nhận xét