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.^[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

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

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

1. Uniform Cost Search Lưu trữ 2013-10-29 tại Wayback Machine, Đại học Stanford.

Liên kết ngoài

• Unit 2, Topic 14, Uniform Cost Search, YouTube.