Python giải mê cung dfs

Thuật toán tìm kiếm A-Star [A*] là một thuật toán thông minh để giải bài toán đồ thị. Trái ngược với Tìm kiếm theo chiều sâu [DFS] và Tìm kiếm theo chiều rộng [BFS], A* là một thuật toán tìm kiếm được thông báo, có nghĩa là nó tính đến vị trí/vị trí của mục tiêu trong khi tìm kiếm nó và do đó nó tìm kiếm khá nhiều nút để

Chúng tôi sẽ phát triển thuật toán A* trong Python để giải bài toán Mê cung. Đây là một đầu ra mẫu của mã chúng tôi sẽ phát triển

Chúng ta sẽ thảo luận về logic của thuật toán tìm kiếm A* trên mê cung sau

Cách thức hoạt động của A* là nó chỉ định một chi phí cho từng ô của mê cung và thuật toán sẽ chọn đường đi có chi phí nhỏ nhất. Chi phí của một ô [n] có hai phần và được định nghĩa là

f[n] = g[n]+h[n]

Trong đó f[n] là tổng chi phí để đến được ô n và g[n] và h[n] được định nghĩa là

g[n] → Đó là chi phí thực tế để đến được ô n từ ô bắt đầu

h[n] → Đó là chi phí heuristic để tiếp cận ô mục tiêu từ ô n. Đó là chi phí ước tính để đạt được ô mục tiêu từ ô n

Hãy xem trường hợp sau của ô [3,3] để hiểu rõ hơn về g[n] và h[n]

Chi phí g[n] cho ô [3,3] là 2 vì từ ô bắt đầu, chúng ta có thể đến ô [3,3] trong 2 bước. Khi đó h[n] là chi phí ước tính để đến được ô mục tiêu [1,1] từ ô [3,3]. Chúng tôi không biết chi phí để đạt được ô mục tiêu vì vậy chúng tôi sẽ chỉ ước tính rằng. Có thể có hai chức năng để ước tính chi phí đó

1- Khoảng cách Euclide

Nó sẽ là khoảng cách tuyến tính giữa một ô và ô mục tiêu như được hiển thị ở đây

2- Khoảng cách Manhattan

Tùy chọn thứ hai có thể là Khoảng cách Manhattan giữa một ô và ô đích là khoảng cách ngang cộng dọc giữa hai ô

Chi phí Heuristic chỉ là ước tính chi phí và việc lựa chọn đúng Hàm Heuristic là một tham số chính của Thuật toán A*. Chúng tôi sẽ sử dụng Khoảng cách Manhattan làm Hàm Heuristic

Khoảng cách Manhattan giữa ô [3,3] và ô mục tiêu là 4 và do đó tổng chi phí của ô [3,3] là

f[n]=g[n]+h[n]=2+4=6

Việc bao gồm Chi phí Heuristic trong thuật toán A* làm cho nó hiệu quả hơn so với BFS hoặc DFS vì thuật toán chọn các ô có chi phí tối thiểu [chi phí thực tế + chi phí ước tính] và do đó nó sẽ tiếp cận mục tiêu nhanh chóng

Bây giờ hãy xem Thuật toán A* sẽ mở rộng như thế nào từ ô bắt đầu cho đến khi đến ô mục tiêu

Đây là vị trí bắt đầu của Mê cung và hình vuông màu đỏ hiển thị ô hiện tại chúng ta đang ở tại thời điểm đó là ô bắt đầu

Bắt đầu từ ô bắt đầu, g[n] của ô bắt đầu bằng 0 vì chi phí để tiếp cận ô bắt đầu từ ô bắt đầu rõ ràng là bằng không. Và h[n] của ô bắt đầu là 6, đó là Khoảng cách Manhattan giữa ô bắt đầu và ô mục tiêu

Đối với các tế bào khác, chúng tôi không biết chi phí; . Đây là giá trị chi phí của toàn bộ Mê cung trong đó chi phí của mỗi ô được hiển thị dưới dạng hai giá trị g[n]+h[n]

Bây giờ chúng ta sẽ khám phá các ô lân cận của ô hiện tại. Chỉ có một ô lân cận [3,4] của ô hiện tại và chúng tôi sẽ tính chi phí của ô này. g[n] của ô [3,4] sẽ là 1, vì chúng ta cần một bước để đến ô [3,4] từ ô bắt đầu và h[n] là 5

Chúng tôi vẫn đang ở ô bắt đầu. Bây giờ, Thuật toán A* sẽ chọn ô có chi phí nhỏ nhất, cho bước di chuyển tiếp theo trong trường hợp này là ô [3,4] và do đó nó sẽ di chuyển đến đó

Có 3 hàng xóm của ô [3,4] và chi phí của chúng sẽ được tính như hình dưới đây

Chi phí mới của các ô [4,4] là 8, cao hơn chi phí cũ là 6 và do đó chúng tôi sẽ không cập nhật giá trị đó

Điều đó đơn giản có nghĩa là chúng ta không muốn chuyển động từ ô [4,4] sang ô [3,4] rồi từ ô [3,4] trở lại ô [4,4]. Chi phí của hai ô khác, [2,4] và [3,3] tốt hơn vô cùng và do đó chúng tôi sẽ cập nhật chi phí của chúng và sẽ không cập nhật chi phí của ô [4,4]

Chúng tôi đang ở ô [3,4] và ô tiếp theo sẽ được chọn là ô có chi phí nhỏ nhất. Chúng tôi sẽ không xem xét ô [4,4] vì nó đã được truy cập và chi phí của nó không được cập nhật sau đó. Điều đó đang được biểu thị dưới dạng một thanh màu vàng bên trong ô

Trong số các ô khác, hai ô [3,3] và [2,4] có chi phí thấp nhất là 6. Bây giờ cái nào để chọn? . Trong trường hợp hiện tại, cả hai ô đều có cùng chi phí khám phá là 4 và do đó chúng ta có thể chọn bất kỳ ô nào trong hai ô và giả sử chúng ta chọn ô [2,4]. Chúng tôi sẽ di chuyển đến đó và đây sẽ là trạng thái cập nhật của Mê cung

Quá trình tính cost của các ô lân cận và sau đó chọn ô có cost nhỏ nhất sẽ tiếp tục cho đến khi chúng ta đến ô mục tiêu. Các bước tiếp theo được hiển thị trong các hình sau

Khi chúng tôi đến ô mục tiêu, có một cách chúng tôi có thể chọn chỉ đường được tô sáng, đó là đường ngắn nhất từ ​​ô bắt đầu đến ô mục tiêu

Bây giờ, hãy xem mã giả của Tìm kiếm A* có thể là gì

Vì phải chọn ô có chi phí nhỏ nhất nên chúng ta sẽ sử dụng Hàng đợi ưu tiên cấu trúc dữ liệu để triển khai thuật toán A*. Khác với Hàng đợi hoạt động theo nguyên tắc FIFO [Vào trước ra trước], các phần tử trong Hàng đợi ưu tiên được lấy ra trên cơ sở thứ tự ưu tiên. Mức độ ưu tiên có thể là giá trị của phần tử [cao nhất hoặc thấp nhất]. Trong Python, chúng tôi có Hàng đợi ưu tiên có sẵn trong Hàng đợi mô-đun và mức độ ưu tiên là giá trị thấp nhất và do đó phù hợp nhất để triển khai A*

Vì vậy, đây là mã giả của A* Search

Điểm quan trọng cần lưu ý trong mã giả ở trên là cách chúng ta lưu trữ thông tin về chi phí và ô bên trong Hàng đợi ưu tiên. Nó đang được lưu trữ dưới dạng Tuple [f_score[start], h[start], start]. Các bộ dữ liệu được so sánh trên cơ sở phần tử đầu tiên bên trong chúng và nếu điều đó giống nhau, thì việc so sánh được thực hiện trên cơ sở phần tử tiếp theo, v.v. Do đó, giá trị đầu tiên được lưu trữ là chi phí của ô và thứ hai là chi phí Heuristic của ô để nếu chi phí của hai hoặc nhiều ô giống nhau, việc so sánh sẽ được thực hiện trên Chi phí Heuristic. Thứ ba là giá trị của chính ô

Để triển khai thuật toán này trong Python, chúng tôi sẽ sử dụng mô-đun pyamaze. Có một bài đăng chi tiết và một video về việc sử dụng mô-đun này nhưng bạn có thể tiếp tục mà không cần chi tiết đó

Ở đây mã hoàn chỉnh được cung cấp và sau đó là thảo luận từng bước về nó

Để tạo một mê cung với kích thước bất kỳ, e. g. , một mê cung 5x5, chúng ta có thể sử dụng module như hình bên dưới

Đoạn mã trên sẽ tạo ra một Mê cung 5x5 ngẫu nhiên. Một ví dụ hiển thị dưới đây

Các đối số Mê cung bạn cần biết là

1- hàng → m. rows sẽ trả về số hàng của mê cung. Nó sẽ là 5 cho trường hợp trên

2- col → m. cols sẽ trả về số cột của mê cung. Nó sẽ là 5 cho trường hợp trên

3- lưới → m. lưới sẽ trả về danh sách tất cả các ô của mê cung. Trong trường hợp trên, nó sẽ là một danh sách gồm 25 ô, từ [1,1] đến [5,5]

4- mê cung_map → m. maze_map sẽ trả về thông tin các bức tường mở và đóng của mê cung dưới dạng từ điển. Các phím sẽ là ô và giá trị sẽ là một từ điển khác với thông tin của bốn bức tường theo hướng Đông, Tây, Bắc và Nam. Đối với trường hợp trên, đây sẽ là đầu ra

{[1, 1]: {'E': 0, 'W': 0, 'N': 0, 'S': 1}, [2, 1]: {'E': 0, 'W': 0, 'N': 1, 'S': 1}, [3, 1]: {'E': 1, 'W': 0, 'N': 1, 'S': 0}, [4, 1]: {'E': 1, 'W': 0, 'N': 0, 'S': 1}, [5, 1]: {'E': 1, 'W': 0, 'N': 1, 'S': 0}, [1, 2]: {'E': 1, 'W': 0, 'N': 0, 'S': 1}, [2, 2]: {'E': 1, 'W': 0, 'N': 1, 'S': 0}, [3, 2]: {'E': 0, 'W': 1, 'N': 0, 'S': 1}, [4, 2]: {'E': 0, 'W': 1, 'N': 1, 'S': 0}, [5, 2]: {'E': 1, 'W': 1, 'N': 0, 'S': 0}, [1, 3]: {'E': 1, 'W': 1, 'N': 0, 'S': 0}, [2, 3]: {'E': 1, 'W': 1, 'N': 0, 'S': 1}, [3, 3]: {'E': 0, 'W': 0, 'N': 1, 'S': 1}, [4, 3]: {'E': 1, 'W': 0, 'N': 1, 'S': 0}, [5, 3]: {'E': 1, 'W': 1, 'N': 0, 'S': 0}, [1, 4]: {'E': 1, 'W': 1, 'N': 0, 'S': 0}, [2, 4]: {'E': 1, 'W': 1, 'N': 0, 'S': 0}, [3, 4]: {'E': 0, 'W': 0, 'N': 0, 'S': 1}, [4, 4]: {'E': 0, 'W': 1, 'N': 1, 'S': 0}, [5, 4]: {'E': 1, 'W': 1, 'N': 0, 'S': 0}, [1, 5]: {'E': 0, 'W': 1, 'N': 0, 'S': 0}, [2, 5]: {'E': 0, 'W': 1, 'N': 0, 'S': 1}, [3, 5]: {'E': 0, 'W': 0, 'N': 1, 'S': 1}, [4, 5]: {'E': 0, 'W': 0, 'N': 1, 'S': 1}, [5, 5]: {'E': 0, 'W': 1, 'N': 1, 'S': 0}}

Sử dụng mã giả được trình bày ở trên, thuật toán có thể được thực hiện như

Trong đoạn mã trên, chúng tôi vừa in các giá trị của g[n] và h[n] nhưng chúng tôi cần thông tin đường dẫn từ ô bắt đầu đến ô mục tiêu. Chúng tôi có thể lưu trữ thông tin đó dưới dạng Từ điển. Một cách rõ ràng có thể lưu trữ thông tin mỗi khi một ô mới được chọn. Trên Mê cung mà chúng ta đã xem xét trước đó, ba cặp khóa-giá trị đầu tiên của từ điển sẽ như thế này

Nhưng trong Từ điển, chúng tôi không thể có các giá trị trùng lặp với một khóa, vì vậy trong trường hợp trên, chúng tôi không thể lưu trữ hai cặp, [3,4]. [2,4] và [3,4]. [3,3]. Giải pháp là lưu đường dẫn theo thứ tự ngược lại vì chúng ta có thể có các giá trị trùng lặp trong Từ điển. Vì vậy, đường dẫn sẽ là đường dẫn ngược lại và sau này chúng ta có thể đảo ngược đường dẫn đó để có được đường dẫn phía trước

Hơn nữa, lớp agent được sử dụng để tạo một tác nhân và sau đó sử dụng phương thức tracePath của lớp Mê cung, tác nhân sẽ lần theo đường đi được tính toán bởi Thuật toán A*

Các bạn có thể xem video chi tiết để rõ hơn. Ngoài ra, có một đoạn mã khác trực quan hơn một chút về thuật toán theo cách mà việc tìm kiếm các ô mê cung khác nhau cũng được mô phỏng

Mô-đun pyamaze được tạo để tạo điều kiện thuận lợi cho việc tạo Mê cung bằng mã dễ dàng và sau đó có thể được sử dụng để mã hóa bất kỳ thuật toán tìm kiếm nào như Tìm kiếm theo chiều rộng, Tìm kiếm theo chiều sâu, A*, Dijkstra hoặc một số thuật toán tìm kiếm Học tăng cường hoặc di truyền. Bạn có thể xem danh sách phát này để thực hiện các thuật toán tìm kiếm khác nhau với mô-đun pyamaze