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

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

นิยาม

[แก้]

โดยปกติขั้นตอนวิธีการค้นหานั้น จะเกี่ยวข้องกับการสร้างปมลูกโดยการเพิ่มปมข้างเคียงที่ยังไม่มีปมลูกและมีเส้นทางเชื่อมไปยังแถวคอยบุริมภาพ แต่ละปมในแถวคอยจะเก็บค่าทุนสุทธิจากปมราก โดยปมที่มีค่าทุนผ่านทางรวมที่น้อยที่สุดจะเป็นปมในแถวคอยที่มีลำดับความสำคัญมากสุด ปมแรกในแถวคอยจะถูกสร้างลูกเป็นลำดับ โดยจะเพิ่มเซตของปมเชื่อมต่อด้วยค่าทุนรวมจากปมราก 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

ตัวอย่าง

[แก้]

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

แหล่งข้อมูลที่อ้างอิง

[แก้]