การค้นหาตามค่าทุนอย่างมีเอกรูป

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีค้นหาแบบค่าทุนน้อยสุด () เป็นการค้นหาโดยใช้ขั้นตอนวิธีแบบแผนภูมิต้นไม้ ใช้สำหรับการแวะผ่านหรือการค้นหาในต้นไม้ค้นหาแบบเทียบน้ำหนัก จากโครงสร้างหรือกราฟ เราจะเริ่มค้นหาจากปมราก ส่วนปมถัดไปที่เราจะเลือกนั้น ต้องทำให้ค่าที่เราสนใจรวมสุทธิจากปมรากไปยังปมนั้นมีค่าทุนน้อยสุด โดยค่าทุนที่เราสนใจนั้นอาจเป็นน้ำหนัก หรือระยะทางก็ได้ เราจะใช้หลักการเลือกแบบนี้จนกว่าจะถึงปมเป้าหมาย

 นิยาม 
โดยปกติขั้นตอนวิธีการค้นหานั้น จะเกี่ยวข้องกับการสร้างปมลูกโดยการเพิ่มปมข้างเคียงที่ยังไม่มีปมลูกและมีเส้นทางเชื่อมไปยังแถวคอยบุริมภาพ แต่ละปมในแถวคอยจะเก็บค่าทุนสุทธิจากปมราก โดยปมที่มีค่าทุนผ่านทางรวมที่น้อยที่สุดจะเป็นปมในแถวคอยที่มีลำดับความสำคัญมากสุด ปมแรกในแถวคอยจะถูกสร้างลูกเป็นลำดับ โดยจะเพิ่มเซตของปมเชื่อมต่อด้วยค่าทุนรวมจากปมราก UCS นั้นจะเสร็จสมบูรณ์และดีที่สุดเมื่อค่าทุนรวมของแต่ละขั้นตอนเกินค่า ε (ค่าบวก) กรณีที่ใช้เวลาเยอะที่สุดซึ่งมีความซับซ้อนคือ O (b1 + C*/ε)  เมื่อ C* คือค่าทุนของผลลัพธ์ที่ดีที่สุด และเมื่อค่าทุนของทุกกรณีเท่ากัน มันจะกลายเป็น O (bd + 1) 

 รหัสเทียม 
 node := root, cost = 0
 frontier := empty priority queue containing node
 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)
 if n is in frontier with higher cost
 replace existing node with n

 ขั้นตอนวิธีการที่เกี่ยวข้อง 
ขั้นตอนวิธีค้นหาระยะทางแบบเอกรูป เปรียบได้กับการมอง Best First Search แบบง่าย ๆ ซึ่งในทางทฤษฎีแล้วก็มีความใกล้เคียงกับ Dijkstra's Algorithm มากที่สุด และยังเกี่ยวเนื่องกับ A* Algorithm

 ตัวอย่าง 
ไฟล์:UCS graph.jpg

Expansion showing the explored set and the frontier (priority queue) :
Start Node: A
Goal Node: G

Step 1
Frontier:
 Node  A Cost  0
Explored: -

Step 2
Expand A
Frontier:
 Node  D  B Cost  3  5
Explored: A

Step 3
Expand D
Frontier:
 Node  B  E  F Cost  5  5  5
Explored: A D

Step 4
Expand B
Frontier:
 Node  E  F  C Cost  5  5  6
Explored: A D B

Step 5
Expand E
Frontier:
 Node  F  C Cost  5  6
Explored: A D B E
 Note: B was not added to the priority queue because it was already explored

Step 6
Expand F
Frontier:
 Node  C  G Cost  6  8
Explored: A D B E F

Step 7
Expand C
Frontier:
 Node  G Cost  8
Explored: A D B E F C

Step 8
Expand G
Found the path: A to D to F to G

 แหล่งข้อมูลที่อ้างอิง 
 Uniform cost search - Math Wiki
 Artificial Ingelligence - Uniform Cost Search 
 บทความ* 
 บทความ** 

หมวดหมู่:ขั้นตอนวิธีการค้นหา