Tìm kiếm chi phí đều

Bách khoa toàn thư mở Wikipedia
Bước tới điều hướng Bước tới tìm kiếm

Trong khoa học máy tính, tìm kiếm chi phí đều (hay còn gọi là tìm kiếm chi phí cực tiểu hoặc tìm kiếm theo giá thành thống nhất, viết tắt tiếng AnhUCS) là một cách duyệt cây dùng cho việc duyệt hay tìm kiếm một cây, cấu trúc cây, hoặc đồ thị có trọng lượng (chi phí). Việc tìm kiếm bắt đầu tại nút gốc.[1] Việc tìm kiếm tiếp tục bằng cách duyệt các nút tiếp theo với trọng lượng hay chi phí thấp nhất tính từ nút gốc. Các nút được duyệt tiếp tục cho đến khi đến được nút đích cần đến.

Thuật toán[sửa | sửa mã nguồn]

procedure UniformCostSearch(Graph, root, goal)
 node:= root, cost = 0
 frontier:= priority queue containing node only
 explored:= empty set
 do
if frontier is empty
 return failure
node:= frontier.pop()
if node is goal
 return solution
explored.add(node)
for each of node's neighbors n
 if n is not in explored
  if n is not in frontier
 frontier.add(n)
  else if n is in frontier with higher cost
 replace existing node with n

Ví dụ[sửa | sửa mã nguồn]

UCS graph.jpg

Mở rộng các tập đã xét và hàng đợi ưu tiên:
Nút bắt đầu: A
Nút kết thúc: G

Các bước Biên giới: tập các đối tượng (nút và chi phí) Mở rộng[*] Đã xét: tập các nút đã xét
1 {(A,0)} A
2 {(D,3),(B,5)} D {A}
3 {(B,5),(E,5),(F,5)} B {A,D}
4 {(E,5),(F,5),(C,6)} E {A,D,B}
5 {(F,5),(C,6)}[**] F {A,D,B,E}
6 {(C,6),(G,8)} C {A,D,B,E,F}
7 {(G,8)} G {A,D,B,E,F,C}
8

^ * Nút được chọn để duyệt cho bước tiếp theo.
^ ** B không được thêm vào hàng đợi vì nó đã nằm trong tập đã xét.
Đường đi được tìm thấy: A -> D -> F -> G. Ở bước số 3, các nút B, E, F đều có chi phí là 5, trường hợp này có thể chọn 1 nút bất kỳ hoặc ưu tiên theo thứ tự các nút (chẳng hạn như theo thứ tự chữ cái B, E, F thì chọn B).

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Uniform Cost Search, Đại học Stanford.

Liên kết ngoài[sửa | sửa mã nguồn]