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

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 Anh là UCS) 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. 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
 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ụ 

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

 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

Liên kết ngoài
 Unit 2, Topic 14, Uniform Cost Search, YouTube.

Giải thuật lý thuyết đồ thị
Giải thuật tìm kiếm