Ở phần trước, mình đã nhắc về thuật toán DFS và BFS áp dụng trong việc giải bài toán tháp Hà Nội. BFS đã thất bại đau đớn trong việc giải bài toán với hơn 5 đĩa và DFS chỉ có thể giải các bài toán ít hơn 9 đĩa (đối với bài toán có 8 đĩa, DFS tìm ra kết quả dài 3280 bước trong khi đáp án tối ưu chỉ cần 255 bước!) Vì vậy chúng ta cần tìm tới một thuật toán tối ưu hơn nữa, đó chính là A* search và mong rằng A* search có thể giải được toàn bộ các bài toán trên với bộ nhớ, thời gian và đáp án tối ưu nhất.


http://matebe.com/talent/article/442/phần-1-thiết-kế-game-giải-đố-áp-dụng-thuật-toán-tìm-kiếm-trong-đồ-thị-bfs-v/


                                                                                     


Trước khi nói về A* Search, chúng ta cần phải nhắc tới một cấu trúc dữ liệu gắn liền với nó là Hàng ưu tiên (Priority queue). Ở bài trước mình đã nhắc tới cấu trúc trên và các cách xây dựng một hàng ưu tiên dựa trên mảng, binary heap, v…v… Tuy nhiên chúng ta sẽ dùng tới hàng ưu tiên đã được xây dựng sẵn trong lớp java.util.


http://matebe.com/talent/article/389/cấu-trúc-dữ-liệu-hàng-ưu-tiên-priority-queue/


Lí do mình nhắc tới hàng đợi ưu tiên vì trong A* Search chúng ta sẽ cần thêm một định nghĩa mới cho lớp State là heuristic và evaluation function. Evaluation function là hàm nhận vào một State và trả về một giá trị đánh giá mức độ “tốt” của State đó để quyết định xem State đó có nên được dùng tới hay không. Giá trị mà chúng ta vừa nói tới chính là heuristic. Cấu trúc hàng đợi ưu tiên dựa vào giá trị heuristic trên để đánh giá xem nút nào được sử dụng trước vì nó có thể tìm ra đáp án tối ưu cho bài toán.


                              


Ở hình trên, giá trị heuristic càng bé thì chúng ta sẽ càng tiến gần tới đáp án bài toán (State với heuristic = 0 chính là đáp án bài toán cần tìm). Tuy nhiên khi phân tích một State để tìm ra giá trị heuristic, chúng ta cần phải nắm rõ bài toán đó và đưa ra những phương pháp đánh giá heuristic tốt nhất nếu không sẽ khiến cho độ chính xác của thuật toán bị ảnh hưởng và có khả năng không thể tìm ra đáp án tối ưu và tệ hơn nữa là không thể tìm ra đáp án! Ở hình dưới mình sẽ đưa ra một ví dụ vì sao tính toán sai giá trị heuristic có thể dẫn tới một đáp án không tối ưu.


                                 


                                   


Một ví dụ khác về hậu quả của việc đánh giá sai một State gây ra (Đáp án tối ưu của bài toán này là 30)



Khi đánh giá một State chính xác, thuật toán không chỉ tìm ra đáp án tối ưu mà còn tăng tính hiệu quả (Số lần gọi các hàm dùng tới priority queue giảm, kích thước priority queue giảm)


Để tăng tính hiệu quả khi đánh giá độ “tốt” của một State, ngoài giá trị heuristic, chúng ta sẽ tìm tới một giá trị khác giúp cho thuật toán có thể đưa ra lựa chọn chính xác hơn đó là chiều sâu của nút. Hãy xem xét trường hợp sau:


                                    


Khi sử dụng thêm độ sâu của nút, ban đầu nút 3 bên trái vẫn được mở rộng trước, tuy nhiên đây là hàng đợi ưu tiên (sắp xếp các phần tử dựa trên giá trị), khi nút này được mở rộng tiếp, các giá trị sau nó có giá trị lớn hơn (4 và 6) (tuy nút 3 ở hàng 1 và 2 ở hàng 2 có cùng giá trị trên hàng đợi là 4, nhưng vì nút 2 được tìm ra sau nên sẽ đứng đằng sau). Như vậy, chúng ta có thể tóm tắt đơn giản rằng thuật toán A* dựa mức độ “tốt” của một State (heuristic) để đánh giá xem nút nào đáng được tìm kiếm trước nhất, qua đó sẽ giảm thiểu được thời gian tìm kiếm, dung lượng bộ nhớ và đảm bảo tìm ra được đáp án tối ưu. Sau đây là điểm khác biệt của 3 thuật toán mình đã nêu (không bao gồm mức độ phức tạp)


                                                                 


Dưới đây là code cho thuật toán A*, các bạn có thể nhận thấy không hề có nhiều khác biệt so với code trước của BFS và DFS


    public Stack aStarSearch(Vertex start) {


        //Clear all previous stats if there are any


        resetStats();


        //Comparator used for the priority queue operation


        Comparator comp = new Comparator() {


            @Override


            public int compare(Object o1, Object o2) {


                //So sánh giá trị dựa trên độ sâu của nút và heuristic của nút đó


                if (((Vertex) o1).getDistance() + ((State) o1).getHeuristic(getFinalState()) <


                        ((Vertex) o2).getDistance() + ((State) o2).getHeuristic(getFinalState())) {


                    return -1;


                }


                return 1;


            }


        };


        //Ngăn xếp chứa các bước đáp án bài toán


        Stack solution = new Stack();


        //Hàng đợi ưu tiên chứa các nút 


        PriorityQueue priorityQueue = new PriorityQueue(1, comp);


        //Đưa nút khởi đầu vào hàng đợi ưu tiên


        priorityQueue.add(start);


        //Update statistics


        ++queueOps;


        ++queueSize;


        maxQueueSize = Math.max(queueSize, maxQueueSize);


        while (!priorityQueue.isEmpty()) {


            //Lấy ra nút đầu tiên trong hàng đợi


            Vertex toBeExpanded = priorityQueue.remove();


            //Update statistics


            ++queueOps;


            --queueSize;


            //Nếu đã tìm ra đáp án


            if (this.isFinalState(((State) toBeExpanded))) {


                //Push the final state onto the solution stack


                solution.push(toBeExpanded);


                //Keep pushing all predecessors onto the solution stack until it reach the start state


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


                    solution.push(pred);


                    pred = pred.getPredecessor();


                }


                //Trả về đáp án nếu tìm ra


                return solution;


            } else { //Nếu vẫn chưa tìm ra đáp án, mở rộng nút đầu tiên trong hàng đợi


                //Mở rộng nút đầu tiên trong hàng đợi


                List children = expand(toBeExpanded);


                Iterator iter = children.iterator();


                //Tìm ra các nút con mới và thêm chúng vào hàng ưu tiên 


                while (iter.hasNext()) {


                    //Add discovered node to the priority queue


                    priorityQueue.add(iter.next());


                    //Update statistic


                    ++queueOps;


                    ++queueSize;


                    maxQueueSize = Math.max(queueSize, maxQueueSize);


                }


            }


        }


        //Trả về null nếu như không tìm ra đáp án


        return null;


    }


Đối với bài toán tháp Hà Nội, chúng ta cần tìm ra giá trị heuristic tốt nhất để có thể giúp cho thuật toán tìm ra đáp án tối ưu trong thời gian ngắn mà không tốn bộ nhớ. Một số cách tính giá trị heuristic mà mình áp dụng để giải bài toán tháp Hà Nội bao gồm số lượng các đĩa nằm không đúng vị trí, số lượng các đĩa cần phải di chuyển (những đĩa này tuy nằm đúng cột nhưng vị trí của chúng lại không chính xác). Xét trường hợp trên:


                                                                  


Có 1 đĩa nằm sai cột là đĩa ở cột p, như vậy heuristic lúc này là 1. Tuy nhiên 4 đĩa ở cột r tuy nằm ở đúng cột nhưng sai vị trí của chúng nên 4 đĩa này cần phải được di chuyển. Lúc này heuristic trả về sẽ là 5. Mình đã giải thích xong về thuật toán A* search, bây giờ chúng ta sẽ áp dụng nó vào bài toán Tháp Hà Nội để xem A* có thể giải được tới bao nhiêu chồng đĩa. Và…


                                        


A* Search đã tìm ra đáp án tối ưu cho bài toán 5 chiếc đĩa (31 bước đi). Tuy nhiên, nhìn vào thống kê số lần gọi hàm của hàng ưu tiên (1,041,896) và kích thước lớn nhất của hàng ưu tiên (249,137) quả là không thể chấp nhận được! Hơn nữa A* search cũng tốn khá lâu mới có thể tìm ra đáp án này nghĩa là với bài toán lớn hơn A* search có khả năng sẽ thất bại. Liệu có phải do cách tính heuristic có vấn đề nên đã khiến cho A* search không phát huy được tính hiệu quả? Hay do những yếu tố khác như độ phức tạp của thuật toán, độ lớn của bài toán (khá khó chấp nhận khả năng này vì bài toán này chỉ có 31 bước đi so với bài cuối là 511 bước đi!) Chúng ta sẽ phải tìm cách giúp cho thuật toán tối ưu hơn nữa để có thể có được một đáp số tốt hơn và điều này sẽ cần tới một cấu trúc dữ liệu mới là bảng băm (Hash table).


Đính kèm dưới bài viết là bản mở rộng của bài toán tháp Hà Nội với thuật toán A* search.

Login để lấy link download