Trong bài trước mình có nhắc tới 2 thuật toán tìm kiếm cơ bản cho đồ thị là Breadth-first search (BFS) và Depth-first search (DFS). Hôm nay mình sẽ hướng dẫn cách làm một game tự giải đố sử dụng 2 thuật toán trên. Trò chơi được viết chính là Tháp Hà Nội (Tower of Hanoi). Đây là một trò chơi vô cùng quen thuộc với các bạn học ngành khoa học máy tính, đặc biệt là khi chúng ta học tới thuật toán đệ quy. Trong bài mình sẽ tập trung về khía cạnh thiết kế thuật toán thay vì đi vào những phần như đồ hoạ, GUI, hay quan hệ giữa các lớp, giao diện.


http://matebe.com/talent/article/365/2-thuật-toán-tìm-đường-đơn-giản-áp-dụng-trong-đồ-thị/ 


Trước hết, chúng ta sẽ nói về bài toán Tháp Hà Nội. Trong bài toán bao gồm 3 cột, gọi là 3 chồng p, q và r. Mục tiêu của bài toán là đưa toàn bộ các chồng đĩa từ cột p sang cột r. Mỗi đĩa có một kích thước khác nhau và đĩa có kích thước lớn hơn không được đặt trên đĩa có kích thước bé hơn nó.



  •  Class relationship

Để thiết kế được bài toán này, chúng ta cần có một lớp đầu tiên gọi là State. Lớp state dùng để chứa thông tin trạng thái của bài toán, mỗi khi di chuyển 1 đĩa, bài toán sẽ tạo ra 1 state khác nhau. Ví dụ trên hình trên, mình có thể di chuyển p sang q và r và tạo ra 2 state khác nhau. Ngoài lớp State, chúng ta sẽ cần tới 1 lớp Move với mục đích tạo ra các state mới từ một state cũ. Cuối cùng sẽ là lớp Problem dùng để chứa lớp State và lựa chọn bước đi (Move).



Để chương trình có thể tự tìm ra bài giải, mỗi State của bài toán phải trở thành 1 nút trong cây tìm kiếm (Vertex). Do đó, mỗi State có thể có cùng trạng thái giống nhau, nhưng vì chúng là các nút khác biệt nên sẽ có thể có khoảng cách tới nút gốc khác nhau. Lúc này, lớp Problem sẽ trở thành một graph để chứa các nút trong đồ thị và thực hiện các hàm tìm kiếm.


                                     


Lớp problem cũng sẽ chứa lớp Canvas nhằm mục đích hiển thị bài toán thông qua đồ hoạ thay vì dùng tới console nhưng mình sẽ không nói tới phần này.


  • Thiết kế thuật toán

      Theo như bài viết trước, thuật toán Depth-first search sẽ tìm 1 nút nối với nút khởi đầu, từ đó sẽ tìm tới những nút khác cho tới khi tìm ra nút kết thúc (đáp án của bài toán). Lợi thế của DFS là không tốn bộ nhớ do sử dụng cấu trúc dữ liệu ngăn xếp (stack). Tuy nhiên nó không đảm bảo sẽ tìm được đường ngắn nhất tới đáp án



 


Đối với bài toán 5 chồng đĩa trên, số bước đi ngắn nhất là 31. Tuy nhiên, DFS lại tìm ra lời giải với 121 bước đi! DFS gọi tới 307 lần các hàm thêm và xoá nút khỏi deque, kích thước lớn nhất của deque là 64.


Trong cùng với trường hợp trên khi sử dụng BFS, do kích thước của bài toán quá lớn và bất lợi của BFS là tốn bộ nhớ do sử dụng hàng đợi, thuật toán đã không thể tìm ra được đường ngắn nhất dẫn tới đáp án vì bị Heap Overflow. Vì thế trong lần tới chúng ta sẽ phải tìm tới một thuật toán tốt hơn nữa để giải bài toán tháp Hà Nội với nhiều hơn 5 chồng đĩa (A* search). Dưới đây là code dành cho thuật toán DFS và BFS. Do sử dụng cấu trúc dữ liệu deque, chúng ta có thể giảm thiểu số code dư thừa vì sự khác biệt của 2 thuật toán trên chỉ nằm ở cách chúng thêm một nút vào (đầu hàng hay cuối hàng).


 


   private Stack search(Vertex start, DequeAdder adder) {


        resetStats();


        //Ngăn xếp chứa tất cả các nút từ nút khởi đầu cho tới nút chứa đáp án bài toán


        Stack solution = new Stack();


        //Tạo ra một deque chứa các nút được tìm thấy bởi thuật toán


        Deque vertices = new LinkedList();


        //Đưa nút ban đầu (State đầu của bài toán) vào trong deque trên.


        //Chú ý: chúng ta sử dụng một lớp có tên gọi là DequeAdder để giúp lựa chọn xem nút


        //được đưa vào sẽ có vị trí ở đầu hay cuối hang


        adder.add(start, vertices);


        //Đây là các thống kê về mức độ hiệu quả của thuật toán


        //Số lượng các công việc (hàm) được deque sử dụng


        ++queueOps;


        //Kích thước của deque


        ++queueSize;


        //Kích thước lớn nhất của deque


        maxQueueSize = Math.max(queueSize, maxQueueSize);


        //Trong khi deque vẫn còn nút


        while (!vertices.isEmpty()) {


            //Lấy ra nút đầu tiên trong hang đợi / ngăn xếp


            //Vị trí của nút bị lấy ra không quan trọng vì đó luôn là nút đầu hang


            Vertex toBeExpanded = vertices.pop();


            ++queueOps;


            --queueSize;


            //Nếu như nút trên là đáp án của bài toán


            if (isFinalState(((State) toBeExpanded))) {


                //Đưa nút đó vào stack đáp án


                solution.push(toBeExpanded);


                //Đi ngược trở lên cây tìm kiếm, đưa tất cả các nút cha của nút trên vào stack đáp án


                for (Vertex pred = toBeExpanded.getPredecessor() ; !pred.equals(start) ; ) {


                    solution.push(pred);


                    pred = pred.getPredecessor();


                }


                return solution;


            } else { //Nếu như chưa tìm thấy đáp án bài toán


                //Tìm tất cả các nút con nối với nút trên


                List children = expand(toBeExpanded);


                Iterator iter = children.iterator();


              //Đưa tất cả các nút mới được tìm thấy vào deque vertices


                while (iter.hasNext()) {


                    adder.add(iter.next(), vertices);


                    ++queueOps;


                    ++queueSize;


                    maxQueueSize = Math.max(queueSize, maxQueueSize);


                }


            }


        }


        //Trả về null nếu như không thể tìm ra đáp án cho bài toán


        return null;


    }


Đoạn code trên có lẽ sẽ khá khó hiểu với nhiều bạn, dưới đây mình có một bức hình minh hoạ cho hàm tìm kiếm trên sử dụng thuật toán BFS.



Giả sử nút A là nút khởi đầu và E là đáp án cần tìm.


B1: Đưa nút A trên vào hàng đợi (Do BFS sử dụng queue)


B2: Mở rộng nút A, tìm tất cả các nút con của A


B3: Đưa các nút con vừa tìm thấy vào hang đợi


B4: Rút nút B ra và mở rộng nó (tìm thấy nút D, không nhận A vì A là nút cha của B)


B5: Đưa D vào cuối hàng đợi


B6: Rút C ra, tìm thấy nút F


B7: Đưa nút F vào hang đợi


B8: Rút D ra và mở rộng nó, tìm thấy nút E


B9: Đưa E vào hàng đợi


B10: Rút F ra, tìm thấy nút E (Tuy 2 State giống nhau, nhưng 2 nút này lại khác nhau hoàn toàn do chúng được tìm thấy bởi 2 nút khác nhau).


Đáp án do BFS tìm ra là A-B-D-E 


Project java được đính kèm trong bài sử dụng IDE Netbeans. Trong project có tổng cộng 9 bài toán tháp hà nội với số đĩa khác nhau, tuy nhiên thì theo như mình đã nêu ở trên thì BFS dường như không thể giải được bài toán lớn hơn 5 đĩa (Do mất khá lâu nên mình quyết định dừng chạy BFS ở mức 5 đĩa) và DFS không giải được bài toán lớn hơn 8 đĩa (tuy nhiên số bước đi khá khủng khiếp!). Để tìm ra đáp án ngắn nhất cho các bài toán lớn hơn và đảm bảo thời gian tìm kiếm ngắn (khoảng 1s). Chúng ta sẽ cần tìm tới một thuật toán tốt hơn, đó là A* search và sau cùng là phiên bản nâng cấp của nó (Enhanced A* search). Hai thuật toán trên sẽ cần tới một định nghĩa mới dành cho mỗi State đó là heuristic và một cấu trúc dữ liệu khác mình đã nhắc tới ở một bài viết khác (Hàng đợi ưu tiên).
http://matebe.com/talent/article/389/cấu-trúc-dữ-liệu-hàng-ưu-tiên-priority-queue/

Login để lấy link download