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

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển 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]