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

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

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

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