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

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

นิยาม

โดยปกติขั้นตอนวิธีการค้นหานั้น จะเกี่ยวข้องกับการสร้างปมลูกโดยการเพิ่มปมข้างเคียงที่ยังไม่มีปมลูกและมีเส้นทางเชื่อมไปยังแถวคอยบุริมภาพ แต่ละปมในแถวคอยจะเก็บค่าทุนสุทธิจากปมราก โดยปมที่มีค่าทุนผ่านทางรวมที่น้อยที่สุดจะเป็นปมในแถวคอยที่มีลำดับความสำคัญมากสุด ปมแรกในแถวคอยจะถูกสร้างลูกเป็นลำดับ โดยจะเพิ่มเซตของปมเชื่อมต่อด้วยค่าทุนรวมจากปมราก UCS นั้นจะเสร็จสมบูรณ์และดีที่สุดเมื่อค่าทุนรวมของแต่ละขั้นตอนเกินค่า ε (ค่าบวก) กรณีที่ใช้เวลาเยอะที่สุดซึ่งมีความซับซ้อนคือ O (b^{1 + C*/ε}) เมื่อ C* คือค่าทุนของผลลัพธ์ที่ดีที่สุด และเมื่อค่าทุนของทุกกรณีเท่ากัน มันจะกลายเป็น O (b^{d + 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

ตัวอย่าง

 

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
• บทความ*
• บทความ**