Làm cách nào để triển khai thuật toán sao trong python?

Thuật toán A* là một trong những thuật toán tìm đường hiệu quả nhất được sử dụng để tìm đường đi ngắn nhất giữa hai điểm. Nó được xuất bản lần đầu vào năm 1968 bởi Peter Hart, Nils Nilsson và Bertram Raphael [1]. Mặc dù ban đầu nó có thể được coi là một phần mở rộng của thuật toán Dijkstra, nhưng nó đã trở thành một trong những thuật toán tìm đường được sử dụng thường xuyên nhất hiện nay

Thuật toán A* về cơ bản đạt được kết quả tối ưu bằng cách tính toán vị trí của tất cả các nút khác giữa nút bắt đầu và nút kết thúc. Ngoài ra, nó nhanh hơn thuật toán Dijkstra do hàm heuristic[2]

f(n) = g(n) + h(n)

f(n). Tổng chi phí đường đi được tính toán

g(n). Chi phí của đường dẫn giữa nút đầu tiên và nút hiện tại

h(n). hàm heuristic

Nếu chúng ta muốn tìm đường đi ngắn nhất trên Hình 2 bằng chức năng trên;

Giả sử chúng ta đang cố gắng đi từ điểm X đến điểm Y. Vì điểm X không được di chuyển đến một nút khác, chi phí g(n) không xảy ra và giá trị của nó là 0. Giá trị heuristic của điểm này là giá trị 5 được ghi trên nút màu đỏ. Trong các vấn đề như vậy, giá trị heuristic nói chung là khoảng cách không khí giữa nút hiện tại và nút mong muốn. Có hai điểm để đi từ điểm X.
Trường hợp đi đến điểm A thì g(n) = 5 (chi phí đường đi) vì nó di chuyển đến một nút mới. Heuristic được đặt thành h(n) = 1. Giá trị f(n) của điểm A được tìm thấy là 5+1 = 6. Nếu chúng ta muốn tìm giá trị f(n) của tất cả các điểm bằng phương pháp này,

X— A => g(A) + f(A) = 5 + 1 = 6,

A — Y=> g(Y) + f(Y) = 6+ 0= 6,

X— B => g(B) + f(B) = 1+ 4= 5,

B — C => g(C) + f(C) = 3+ 2= 5,

C — Y=> g(Y) + f(Y) = 5 + 0= 5,

Như đã thấy trong ví dụ đơn giản ở trên, con đường ngắn nhất là tuyến đường X-B-C-Y. Chi phí của con đường này là 5 đơn vị, trong khi chi phí của tuyến đường thay thế X-A-Y là 6 đơn vị. Ví dụ trong Hình 3 có thể được xem xét chi tiết hơn khi chúng ta đã hiểu đầy đủ cách sử dụng phương trình trên

Giả sử chúng ta muốn đến nút A từ nút J. Có 2 điểm (B và F), có thể đạt được từ điểm A. Tính toán chi phí chung, chúng tôi nhận được f(B) = 8 + 6 = 14 và f(F) = 3+6 =9. Vì chi phí thấp nhất là tại điểm F, thuật toán A* tiếp tục từ đây. Có 2 đường đi tại điểm F. f(G) = 4 +5 = 9 và f(H) = 10 + 3 = 13. Vì chi phí nhỏ nhất là tại điểm G nên ta có thể thực hiện từ điểm đó. Sau đó, theo các nút I và J, chúng tôi nhận được f(I) = 7 + 1 = 8 , f(J) = 10. Vì tất cả các giá trị nhận được sau khi đi đến nút F đều nhỏ hơn nút f(B) nên nó không được trả về nút B. Nhưng trong một kịch bản khác, giả sử rằng f(I) lớn hơn f(B) sau nút F và G (f(I) > 14). Trong trường hợp này, theo thuật toán A*, quá trình này bị gián đoạn tại đây và đường đi được tiếp tục với nút B. Ở đây, ngay khi f(C) > f(I), quá trình xác định đường đi lại tiếp tục từ nút I

Triển khai với Python

Tất cả các mã bên dưới đều có sẵn tại https. //github. com/ademakdogan/Implementation-of-A-Algorithm-Visualization-via-Pyp5js-

Đầu tiên, cấu trúc lưới được tạo ra. Một số nút ở đây được đánh dấu là chướng ngại vật. Sau đó xác định nút đầu và nút cuối và tìm đường đi ngắn nhất giữa hai điểm này bằng thuật toán A* [3]. Logic hoạt động của thuật toán về cơ bản dựa trên hai danh sách có tên là open_set và closed_set. Mặc dù có những nút có thể được xử lý trong open_set, nhưng có những đường dẫn nút được xử lý trong closed_set và do đó không nên lặp lại (Trong một số cách tiếp cận, các chướng ngại vật cũng được ném trực tiếp vào danh sách closed_set, trong khi ở một số cách tiếp cận, nó có thể được thêm vào . ). Do các quy trình khác nhau, các danh sách này được lấp đầy và làm trống, và đạt được kết quả cuối cùng

Mã giả của tất cả các giai đoạn có thể được xem trên wikipedia

Github

Hình 4 cho thấy triển khai python của thuật toán A*. Thư viện Pyp5js đã được sử dụng để trực quan hóa trong công việc này. Ngoài ra, thuật toán A* có thể hoạt động theo danh sách chướng ngại vật được cung cấp cụ thể, tọa độ của nút đầu và cuối và kích thước của cấu trúc lưới. Do đó, dự án này cũng có thể được sử dụng để giải quyết các vấn đề cụ thể

python AStar.py -c 25 -r 25 -s 1 -q 3 -e 23 -t 21 -l True

Kết quả là,

The way found!!!
23 20
23 19
23 18
23 17
23 16
23 15
23 14
23 13
23 12
23 11
23 10
23 9
23 8
23 7
23 6
23 5
23 4
23 3
22 3
21 3
20 3
19 3
18 3
17 3
16 3
15 3
14 3
13 3
12 3
11 3
10 3
9 3
8 3
7 3
6 3
5 3
4 3
3 3
2 3
1 3

Pyp5js

Pyp5js là một khung để trực quan hóa mã python trên trình duyệt. Nó cho phép sử dụng p5. thư viện javascript js qua Chuyển mã bằng Python. Sau khi thực hiện các cài đặt cần thiết, nó chỉ cần chạy bằng lệnh sau

$ SKETCHBOOK_DIR='~/my-custom-sketchbook' pyp5js serve

Sau đó, các cài đặt cấu hình cần thiết được thực hiện bằng cách truy cập phần giao diện qua http. //máy chủ cục bộ. 5000/. Trong thư mục được chỉ định (SKETCHBOOK_DIR), các thao tác được thực hiện theo các mã trong tệp python có cùng tên với tên dự án. Nếu bạn muốn kiểm tra chi tiết dự án này, https. //berinhard. github. io/pyp5js/ có thể được truy cập

Kết quả là, thuật toán A* là một trong những thuật toán tìm đường được sử dụng thường xuyên nhất. Trong bài viết này, các nguyên tắc làm việc của thuật toán này và mã hóa của nó với python sẽ được thảo luận. Tất cả các mã có thể được tìm thấy tại github. Thư viện pyp5js đã được sử dụng để trực quan hóa thuật toán. Trong các bài viết tiếp theo, chúng ta sẽ thảo luận về so sánh các thuật toán xác định đường đi khác với thuật toán A*

Github. https. //github. com/ademakdogan

liên kết. https. //www. linkin. com/in/adem-akdo%C4%9Fan-948334177/

[1] Hart, P. e. ; . J. ; . (1968). “Cơ sở chính thức để xác định theo kinh nghiệm các đường dẫn chi phí tối thiểu”. Giao dịch của IEEE về Khoa học Hệ thống và Điều khiển học. 4 (2). 100–107

[2] Tăng, W. ; . L. (2009). “Tìm đường đi ngắn nhất trên mạng lưới đường thực tế. trường hợp của A*”. Tạp chí Khoa học Thông tin Địa lý Quốc tế. 23 (4). 531–543

[3] Hetland, Magnus Lie (2010), Thuật toán Python. Nắm vững các thuật toán cơ bản trong ngôn ngữ Python, Apress, p. 214, ISBN 9781430232377

Thuật toán sao và các bước của nó là gì?

một thuật toán sao với ví dụ là gì?

Thuật toán A* hoạt động như thế nào?

Làm cách nào để tạo một thuật toán trong Python?