Trong khoa học máy tính, A* (đọc là A sao) là thuật toán tìm kiếm trong đồ thị. Thuật toán này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới một nút thỏa mãn một điều kiện đích). Thuật toán này sử dụng một “đánh giá heuristic” để xếp loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua nút đó. Thuật toán này duyệt các nút theo thứ tự của đánh giá heuristic này. Do đó, thuật toán A* là một ví dụ của tìm kiếm theo lựa chọn tốt nhất (best-first search).

Thuật toán A * được miêu tả lần đầu vào năm 1968 bởi Peter Hart, Nils Nilsson, và Bertram Raphael. Trong bài báo của họ, thuật toán được gọi là thuật toán A ; khi sử dụng thuật toán này với một nhìn nhận heuristic thích hợp sẽ thu được hoạt động giải trí tối ưu, do đó mà có tên A * .Năm 1964, Nils Nilsson ý tưởng ra một chiêu thức tiếp cận dựa trên mày mò để tăng vận tốc của thuật toán Dijkstra. Thuật toán này được gọi là A1. Năm 1967 Bertram Raphael đã cải tổ đáng kể thuật toán này, nhưng không hề hiển thị tối ưu. Ông gọi thuật toán này là A2. Sau đó, trong năm 1968 Peter E. Hart đã trình làng một đối số chứng tỏ A2 là tối ưu khi sử dụng thuật toán này với một nhìn nhận heuristic thích hợp sẽ thu được hoạt động giải trí tối ưu. Chứng minh của ông về thuật toán cũng gồm có một phần cho thấy rằng những thuật toán A2 mới là thuật toán tốt nhất hoàn toàn có thể được đưa ra những điều kiện kèm theo. Do đó ông đặt tên cho thuật toán mới là A * ( A sao, A-star ) .

Mục lục nội dung

Ý tưởng trực quan[sửa|sửa mã nguồn]

Xét bài toán tìm đường – bài toán mà A* thường được dùng để giải. A* xây dựng tăng dần tất cả các tuyến đường từ điểm xuất phát cho tới khi nó tìm thấy một đường đi chạm tới đích. Tuy nhiên, cũng như tất cả các thuật toán tìm kiếm có thông tin (informed tìm kiếm thuật toán), nó chỉ xây dựng các tuyến đường “có vẻ” dẫn về phía đích.

Bạn đang đọc: Giải thuật tìm kiếm A* – Wikipedia tiếng Việt

Để biết những tuyến đường nào có năng lực sẽ dẫn tới đích, A * sử dụng một ” nhìn nhận heuristic ” về khoảng cách từ điểm bất kể cho trước tới đích. Trong trường hợp tìm đường đi, nhìn nhận này hoàn toàn có thể là khoảng cách đường chim bay – một nhìn nhận xê dịch thường dùng cho khoảng cách của đường giao thông vận tải .Điểm độc lạ của A * so với tìm kiếm theo lựa chọn tốt nhất là nó còn tính đến khoảng cách đã đi qua. Điều đó làm cho A * ” rất đầy đủ ” và ” tối ưu “, nghĩa là, A * sẽ luôn luôn tìm thấy đường đi ngắn nhất nếu sống sót một đường đi như vậy. A * không bảo vệ sẽ chạy nhanh hơn những thuật toán tìm kiếm đơn thuần hơn. Trong một môi trường tự nhiên dạng mê cung, cách duy nhất để đến đích hoàn toàn có thể là trước hết phải đi về phía xa đích và ở đầu cuối mới quay lại. Trong trường hợp đó, việc thử những nút theo thứ tự ” gần đích hơn thì được thử trước ” hoàn toàn có thể gây tốn thời hạn .

Xem thêm: Review ứng dụng đọc sách hay trên Android

Mô tả thuật toán[sửa|sửa mã nguồn]

Mô phỏng thuật toán tìm kiếm A * ứng dụng trong tìm đường đi từ một nút khởi đầu đến một nút tiềm năng trong hoạt động robot. Các vòng rỗng đại diện thay mặt cho những nút trong tập mở, nghĩa là những nút đợi, và những vòng tròn tô màu là thuộc tập đóng. Màu trên mỗi nút tô màu tượng trưng cho khoảng cách từ nút đó đến điểm xuất phát : càng xanh thì càng xa. Đầu tiên ta hoàn toàn có thể thấy A * vận động và di chuyển theo hướng thẳng đến tiềm năng, sau khi gặp vật cản, nó sẽ tìm những đường sửa chữa thay thế từ những nút chờ trong tập mở .

A* lưu giữ một tập các lời giải chưa hoàn chỉnh, nghĩa là các đường đi qua đồ thị, bắt đầu từ nút xuất phát. Tập lời giải này được lưu trong một hàng đợi ưu tiên (priority queue). Thứ tự ưu tiên gán cho một đường đi

{\displaystyle x}

$x$ được quyết định bởi hàm

f
(
x
)
=
g
(
x
)
+
h
(
x
)

{\displaystyle f(x)=g(x)+h(x)}

$f(x)=g(x)+h(x)$ .

Trong đó,

g
(
x
)

{\displaystyle g(x)}

$g(x)$ là chi phí của đường đi cho đến thời điểm hiện tại, nghĩa là tổng trọng số của các cạnh đã đi qua.

h
(
x
)

{\displaystyle h(x)}

$h(x)$ là hàm đánh giá heuristic về chi phí nhỏ nhất để đến đích từ

{\displaystyle x}

. Ví dụ, nếu “chi phí” được tính là khoảng cách đã đi qua, khoảng cách đường chim bay giữa hai điểm trên một bản đồ là một đánh giá heuristic cho khoảng cách còn phải đi tiếp.

Hàm

f
(
x
)

{\displaystyle f(x)}

$f(x)$ có giá trị càng thấp thì độ ưu tiên của

{\displaystyle x}

càng cao (do đó có thể sử dụng một cấu trúc heap tối thiểu để cài đặt hàng đợi ưu tiên này)

function A*(điểm_xuất_phát,đích)
    var đóng:= tập rỗng
    var q:= tạo_hàng_đợi(tạo_đường_đi(điểm_xuất_phát))
    while q không phải tập rỗng
        var p:= lấy_phần_tử_đầu_tiên(q)
        var x:= nút cuối cùng của p
        if x in đóng
            continue
        if x = đích
            return p
        bổ sung x vào tập đóng
        foreach y in các_đường_đi_tiếp_theo(p)
            đưa_vào_hàng_đợi(q, y)
    return failure

Trong đó, các_đường_đi_tiếp_theo(p) trả về tập hợp các đường đi tạo bởi việc kéo dài p thêm một nút kề cạnh. Giả thiết rằng hàng đợi được sắp xếp tự động bởi giá trị của hàm

Xem thêm: Phần mềm 1001 truyện người lon

{\displaystyle f}

$f$ .

“Tập hợp đóng” (đóng) lưu giữ tất cả các nút cuối cùng của p (các nút mà các đường đi mới đã được mở rộng tại đó) để tránh việc lặp lại các chu trình (việc này cho ra thuật toán tìm kiếm theo đồ thị). Đôi khi hàng đợi được gọi một cách tương ứng là “tập mở”. Tập đóng có thể được bỏ qua (ta thu được thuật toán tìm kiếm theo cây) nếu ta đảm bảo được rằng tồn tại một lời giải hoặc nếu hàm các_đường_đi_tiếp_theo được chỉnh để loại bỏ các chu trình.

Các đặc thù[sửa|sửa mã nguồn]

Cũng như tìm kiếm theo chiều rộng (breadth-first search), A* là thuật toán đầy đủ (complete) theo nghĩa rằng nó sẽ luôn luôn tìm thấy một lời giải nếu bài toán có lời giải.

Nếu hàm heuristic

{\displaystyle h}

$h$ có tính chất thu nạp được (admissible), nghĩa là nó không bao giờ đánh giá cao hơn chi phí nhỏ nhất thực sự của việc đi tới đích, thì bản thân A* có tính chất thu nạp được (hay tối ưu) nếu sử dụng một tập đóng. Nếu không sử dụng tập đóng thì hàm

{\displaystyle h}

phải có tính chất đơn điệu (hay nhất quán) thì A* mới có tính chất tối ưu. Nghĩa là nó không bao giờ đánh giá chi phí đi từ một nút tới một nút kề nó cao hơn chi phí thực. Phát biểu một cách hình thức, với mọi nút

x
,
y

{\displaystyle x,y}

$x,y$ trong đó

{\displaystyle y}

$y$ là nút tiếp theo của

{\displaystyle x}

h(x)\leq g(y)-g(x)+h(y)

A* còn có tính chất hiệu quả một cách tối ưu (optimally efficient) với mọi hàm heuristic

{\displaystyle h}

, có nghĩa là không có thuật toán nào cũng sử dụng hàm heuristic đó mà chỉ phải mở rộng ít nút hơn A*, trừ khi có một số lời giải chưa đầy đủ mà tại đó

{\displaystyle h}

dự đoán chính xác chi phí của đường đi tối ưu.

Bài toán minh họa[sửa|sửa mã nguồn]

Cho một bàn cờ size n x n. Hãy tìm đường đi ngắn nhất từ điểm 〇 đến điểm △ biết rằng

Các ô trắng là đường đi
Các ô đen là vật cản, không đi được
Tại một ô bất kỳ, chỉ có thể đi lên, xuông, trái, phải nếu không bị cản. Không được đi chéo

Bàn cờ với kích cỡ 9 * 8

Trong bài toán trên ta thấy rằng đường đi ngắn nhất là đường chéo nối từ 〇 đến △

chiều dài đường chéo được tính bằng công thức

h
(
x
)
=

=
8.6

{\displaystyle h(x)={\sqrt {a^{2}+b^{2}}}={\sqrt {7^{2}+5^{2}}}=8.6}

$h(x)={\sqrt {a^{2}+b^{2}}}={\sqrt {7^{2}+5^{2}}}=8.6$

Khi chuyển dời qua mỗi ô thì giá trị của ô sẽ tăng lên 1 đơn vị chức năng

g ( x )
h
(
x
)
=
a
2
+
b
2
{\displaystyle h(x)={\sqrt {a^{2}+b^{2}}}}
$h(x)={\sqrt {a^{2}+b^{2}}}$
Xem thêm: Top 6 Phần Mềm Chơi Game Điện Thoại Trên Pc Bằng Giả Lập, 10 Phần Mềm Giả Lập Android Tốt Nhất Cho Windows

vì là f ( x ) = g ( x ) + h ( x ) { \ displaystyle f ( x ) = g ( x ) + h ( x ) } nên ta có bảng như sau :

f ( x ) = g ( x ) + h ( x ) { \ displaystyle f ( x ) = g ( x ) + h ( x ) }

Xem thêm: Cách chuyển ứng dụng Android sang thẻ nhớ

Tiếp theo từ vị trí 0 sẽ duyệt những ô lân cận nó để tìm ra đường ngắn nhấtVí dụ

Xét lại điểm P(0,0) thì có 2 điểm liên kề nó là bên phải P(1,0) và bên dưới P(0,1) và giá trị

f
(
x
)
=
g
(
x
)
+
h
(
x
)
=
3.2

{\displaystyle f(x)=g(x)+h(x)=3.2}

$f(x)=g(x)+h(x)=3.2$

vì 2 giá trị bằng nhau nên chọn điểm nào cũng được. Ở Step 2 thì đang chọn điểm P. ( 1,0 )

Điểm P(1,0) có 2 điểm liền kề có giá trị lần lượt là:

P
(
2
,
0
)
=
5.2
,
P
(
1
,
1
)
=
4.8

{\displaystyle P(2,0)=5.2,P(1,1)=4.8}

$P(2,0)=5.2,P(1,1)=4.8$ công với P(0,1) đang có sẵn thì ta có 3 điểm

P
(
0
,
1
)
=
3.2
,
P
(
2
,
0
)
=
5.2
,
P
(
1
,
1
)
=
4.8

{\displaystyle P(0,1)=3.2,P(2,0)=5.2,P(1,1)=4.8}

$P(0,1)=3.2,P(2,0)=5.2,P(1,1)=4.8$

Giá trị

P
(
2
,
0
)
=
5.2

{\displaystyle P(2,0)=5.2}

$P(2,0)=5.2$ là giá trị gần với giá trị 8.6 nhất. nên P(2,0) được chọn làm giá trị xét tiếp theo. tương tự các bước trên ta được bảng như dưới.

Sau khi chạm được đến điểm △ thì ta được sơ đồ đường đi ngắn nhất như sau :

Quan hệ với tìm kiếm chi phí đều (uniform-cost search)
[sửa|sửa mã nguồn]

Thuật toán Dijkstra là một trường hợp đặc biệt của A* trong đó đánh giá heuristic là một hàm hằng

h
(
x
)
=
0

{\displaystyle h(x)=0}

$h(x)=0$ với mọi

{\displaystyle x}

Độ phức tạp thuật toán[sửa|sửa mã nguồn]

Độ phức tạp thời gian của A* phụ thuộc vào đánh giá heuristic. Trong trường hợp xấu nhất, số nút được mở rộng theo hàm mũ của độ dài lời giải, nhưng nó sẽ là hàm đa thức khi hàm heuristic h thỏa mãn điều kiện sau:

|h(x)-h^{*}(x)|\leq O(\log h^{*}(x))

trong đó

∗

{\displaystyle h^{*}}

$h^{*}$ là heuristic tối ưu, nghĩa là hàm cho kết quả là chi phí chính xác để đi từ

{\displaystyle x}

tới đích. Nói cách khác, sai số của h không nên tăng nhanh hơn lôgarit của “heuristic hoàn hảo”

∗

{\displaystyle h^{*}}

– hàm trả về khoảng cách thực từ x tới đích (Russell và Norvig 2003, tr. 101).

Vấn đề sử dụng bộ nhớ của A* còn rắc rối hơn độ phức tạp thời gian. Trong trường hợp xấu nhất, A* phải ghi nhớ số lượng nút tăng theo hàm mũ. Một số biến thể của A* đã được phát triển để đối phó với hiện tượng này, một trong số đó là A* lặp sâu dần (iterative deepening A*), A* bộ nhớ giới hạn (memory-bounded A* – MA*) và A* bộ nhớ giới hạn đơn giản (simplified memory bounded A*).

Một thuật toán tìm kiếm có thông tin khác cũng có tính chất tối ưu và đầy đủ nếu đánh giá heuristic của nó là thu nạp được (admissible). Đó là tìm kiếm đệ quy theo lựa chọn tốt nhất (recursive best-first search – RBFS).

Hart, P. E. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics SSC4 (2): 100–107.
Hart, P. E. (1972). “Correction to “A Formal Basis for the Heuristic Determination of Minimum Cost Paths””. SIGART Newsletter. 37: 28–29.
Xem thêm: Nâng cao khả năng ứng dụng công nghệ thông tin vào dạy, học ở Học viện Lục quân hiện nay
Nilsson, N. J. (1980). Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company.
Russell, S. J. (2003). Artificial Intelligence: A Modern Approach. tr. 97-104.