เข้าใจ Uniform Cost Search แบบง่าย ๆ พร้อมตัวอย่างเส้นทางการเดินทางที่มีต้นทุนน้อยที่สุด

ในการแก้ปัญหาเกี่ยวกับการค้นหาเส้นทาง เช่น การหาทางเดินที่ประหยัดที่สุดจากจุดหนึ่งไปอีกจุดหนึ่ง หลายคนอาจจะนึกถึง BFS (Breadth First Search) หรือ DFS (Depth First Search) เป็นหลัก แต่วันนี้เราจะมารู้จักอีกหนึ่งอัลกอริทึมที่มีพลังมากกว่าในการคำนวณเส้นทางที่ “ต้นทุนต่ำที่สุด” และใช้งานได้จริงในหลายสถานการณ์ นั่นคือ Uniform Cost Search (UCS) นั่นเอง!! Uniform Cost Search คืออะไร? Uniform Cost Search หรือที่เรียกสั้น ๆ ว่า UCS เป็นหนึ่งในเทคนิคพื้นฐานของการเขียนโปรแกรมด้าน AI ที่ใช้สำหรับ “ค้นหาเส้นทาง” ที่ดีที่สุดจากจุดหนึ่งไปยังอีกจุดหนึ่ง โดยคำว่า “ดีที่สุด” ในที่นี้ไม่ได้หมายถึง เร็วที่สุด หรือ สั้นที่สุด แต่หมายถึง เส้นทางที่ “มีต้นทุนรวมน้อยที่สุด” หรือก็คือทางที่ คุ้มค่าที่สุด ลองนึกภาพว่าคุณอยากเดินทางจากบ้านไปมหาวิทยาลัย แล้วมีหลายเส้นทางให้เลือก บางเส้นทางอาจจะใกล้แต่รถติดมาก หรือค่ารถแพงกว่า บางเส้นทางอาจจะอ้อมหน่อย แต่ประหยัดทั้งเงินและเวลาในภาพรวม UCS จะช่วยคุณตัดสินใจว่า เส้นทางไหน “เหมาะที่สุด” ในแง่ของต้นทุนโดยรวม แนวคิดของ UCS ก็คือ มันจะเลือกทางที่มี “ต้นทุนสะสม” น้อยที่สุดในทุก ๆ ขั้นตอน เช่น ถ้าเราต้องเดินผ่านเมืองหลายเมือง มันจะเลือกเมืองต่อไปที่รวมค่าผ่านทาง ค่าเดินทาง หรือระยะทาง แล้วมีค่าน้อยที่สุดก่อนเสมอ ต่างจากอัลกอริทึมอื่น ๆ อย่าง DFS หรือ BFS ที่ไม่สนเรื่องต้นทุนเลย หลักการทำงาน UCS แบบเข้าใจง่ายๆเลยนะ โดย “เริ่มจากโหนดเริ่มต้น” จากนั้น “ใช้ Priority Queue” จัดการโหนดที่ต้องไปเยี่ยม โดย “เรียงตามค่าcostสะสม” ต่อด้วย “ขยายโหนดที่มี cost น้อยที่สุดก่อน” และ “หยุดเมื่อถึง goal” UCS ใช้ที่ไหนได้บ้าง? Uniform Cost Search ไม่ได้ใช้แค่ในหนังสือเรียนหรือโจทย์เท่านั้นนะคะ แต่มันถูกนำไปใช้จริงในหลายระบบรอบตัวเราเลย ยกตัวอย่างง่าย ๆ ที่หลายคนอาจจะคาดไม่ถึง นั่นก็คือ ระบบนำทาง (Navigation System) อย่างเช่น Google Maps หรือแอปแผนที่อื่น ๆ ที่เราคุ้นเคย UCS จะช่วยในการหาทางที่ประหยัดเวลาที่สุดหรือต้นทุนน้อยที่สุด เช่น เส้นทางที่หลีกเลี่ยงค่าทางด่วน หรือเส้นทางที่น้ำมันหมดน้อยที่สุด สรุปง่ายๆเลยคือ UCS เหมาะกับทุกสถานการณ์ที่เราต้องเลือก “เส้นทาง” หรือ “ทางเลือก” ที่มี “ต้นทุนรวมต่ำที่สุด” ไม่ว่าจะเป็นต้นทุนเวลา, เงิน, พลังงาน หรือแม้แต่ความเสี่ยง ต่อไปเรามาดูการทำงานของ Uniform Cost Search ในรูปแบบของcodeกันเถอะ เราจะเริ่มจากการสร้างฟังก์ชัน uniform_cost_search ที่รับโครงสร้างของ กราฟ เข้ามา พร้อมจุดเริ่มต้น (start) และจุดหมาย (goal) แล้วให้มันหาทางที่ "ต้นทุนรวมต่ำที่สุด" โดยในโค้ดจะมี 7 ขั้นตอน ขั้นตอนที่ 1 เริ่มจาก Import ตัวช่วยก่อน การนำเข้าโมดูลที่จำเป็น ซึ่งจากในโค้ดการ import heapq ถูกนำเข้าเพื่อใช้ในการจัดการ priority queue ซึ่งช่วยให้สามารถดึง path ที่มี cost ต่ำที่สุดได้อย่างมีประสิทธิภาพ เกล็ดความรู้เล็กๆ Priority Queue คือ คิวพิเศษที่ หยิบตัวที่ “สำคัญที่สุด” ออกก่อน ในที่นี้ “สำคัญ” หมายถึง มีค่า priority ต่ำสุด เช่น ต้นทุนน้อยที่สุดใน UCS ก็จะถูกดึงออกมาก่อนเสมอนะ ขั้นตอนที่ 2 ฟังก์ชันหลัก uniform_cost_search() ฟังก์ชัน uniform_cost_search จะพารามิเตอร์คือ graph คือ กราฟที่แสดงการเชื่อมต่อระหว่างโหนดต่าง ๆ ในรูปแบบของ dictionary start คือ โหนดเริ่มต้น goal คือ โหนดเป้าหมาย ต่อมาการใส่จุดเริ่ม [start] ลงใน queue พร้อมต้นทุนเริ่มต้นคือ 0 visited จะเก็บ node ที่เคยผ่านแล้ว เพื่อไม่ให้วนซ้ำ ขั้นตอนที่ 3 เข้าสู่ลูปสำรวจ เราหยิบเส้นทางที่ cost น้อยที่สุด ออกมาแล้วดูว่า node ปลายทางตอนนี้เป็นอะไร ขั้นตอนที่ 4 ตรวจว่าเคยไป node นี้หรือยัง? ถ้าไปแล้วก็ skip แต่ถ้ายัง ก็ mark ว่าไปมาแล้วนะ ขั้นตอนที่ 5 เจอเป้าหมายหรือยัง? ถ้าใช่ก็ไม่ต้องหาต่อแล้วจ้า ส่งคำตอบกลับเลย โดยจะได้ทั้ง path (เส้นทางทั้งหมด) และ cost (ต้นทุนรวม) ขั้นตอนที่ 6 ถ้ายังไม่เจอ ก็ขยายไปเพื่อนบ้านต่อ ลูปดูเพื่อนบ้านของ node ปัจจุบัน ถ้ายังไม่เคยไปก็สร้างเส้นทางใหม่ พร้อมคำนวณต้นทุนใหม่ใส่เข้า priority queue เพื่อรอให้ UCS หยิบไปพิจารณาในรอบถัดไป ขั้นตอนที่ 7 ถ้าไม่เจอทางไป ถ้าหาไม่เจอจริง ๆ ก็ return ค่า null และต้นทุนเป็น ∞ (แปลว่าไปไม่ได้) ตัวอย่างการใช้งาน UCS กับกราฟกัน นี่คือกราฟที่เขียนด้วย Dictionary โดยใช้ key เป็นชื่อ node นั่นก็คือ 'A','B','C','D','E','F','G' ส่วน value เป็น list ของ tuple แต่ละ tuple แสดงว่า node นี้เชื่อมกับใคร และระยะทาง (cost) เท่าไหร่ เช่น หมายความว่า 'A' เชื่อมไปหา 'B' ด้วย cost 1 และ 'C' ด้วย cost 4 ต่อไปมาดูผลลัพธ์ที่ได้กัน ผลลัพธ์ Path ที่ถูกที่สุด คือ A → B → E → G ต้นทุนรวม 1 + 5 + 2 = 8 โดยจะเริ่มต้นที่ 'A' ปลายทางคือ 'G' จากนั้น ฟังก์ชัน uniform_cost_search() จะหาทางที่ cost รวมทั้งหมดน้อยที่สุด แล้วส่งกลับทั้ง path และ cost เราได้ศึกษาเรื่องของกราฟกันไปแล้ว แต่ความจริงแล้ว Uniform Cost Search (UCS) ไม่ได้จำกัดอยู่แค่กราฟเท่านั้นนะ! วันนี้เราเลยขอพาไปดูตัวอย่างแบบง่าย ๆ ที่ใคร ๆ ก็เข้าใจได้ โดยไม่ต้องวาดกราฟเลยสักนิด ตัวอย่าง Uniform Cost Search แบบไม่ใช้กราฟ โดยสิ่งที่เราต้องการคือการเปลี่ยนเลขจาก 0 ให้กลายเป็น 15 ด้วยการบวกเลขที่มีต้นทุนต่างกัน แล้วหาวิธีที่ "คุ้มค่าที่สุด" โดยในโค้ดจะมี 7 ขั้นตอน ขั้นตอนที่ 1 เริ่มจาก Import ตัวช่วยก่อน ใช้ priority queue เพื่อให้เราสามารถดึง path ที่มีต้นทุนน้อยที่สุดมาคำนวณก่อนได้ คล้าย ๆ กับการเข้าคิวแบบ “ใครถูกที่สุดมาก่อน” นั่นเอง ขั้นตอนที่ 2 สร้างฟังก์ชัน uniform_cost_search_number() เราสร้าง queue ขึ้นมา และใส่ node เริ่มต้น (เลข 0) เข้าไป พร้อมต้นทุนเริ่มต้น 0 visited คือชุดสำหรับเก็บตัวเลขที่เราเคยไปแล้ว เพื่อไม่ให้วนลูปซ้ำซาก (เช่น ไปๆมาๆที่เลขเดิม) โคร

Apr 7, 2025 - 14:46

เข้าใจ Uniform Cost Search แบบง่าย ๆ พร้อมตัวอย่างเส้นทางการเดินทางที่มีต้นทุนน้อยที่สุด

ในการแก้ปัญหาเกี่ยวกับการค้นหาเส้นทาง เช่น การหาทางเดินที่ประหยัดที่สุดจากจุดหนึ่งไปอีกจุดหนึ่ง หลายคนอาจจะนึกถึง BFS (Breadth First Search) หรือ DFS (Depth First Search) เป็นหลัก แต่วันนี้เราจะมารู้จักอีกหนึ่งอัลกอริทึมที่มีพลังมากกว่าในการคำนวณเส้นทางที่ “ต้นทุนต่ำที่สุด” และใช้งานได้จริงในหลายสถานการณ์ นั่นคือ Uniform Cost Search (UCS) นั่นเอง!!

Uniform Cost Search คืออะไร?

Uniform Cost Search หรือที่เรียกสั้น ๆ ว่า UCS เป็นหนึ่งในเทคนิคพื้นฐานของการเขียนโปรแกรมด้าน AI ที่ใช้สำหรับ “ค้นหาเส้นทาง” ที่ดีที่สุดจากจุดหนึ่งไปยังอีกจุดหนึ่ง โดยคำว่า “ดีที่สุด” ในที่นี้ไม่ได้หมายถึง เร็วที่สุด หรือ สั้นที่สุด แต่หมายถึง เส้นทางที่ “มีต้นทุนรวมน้อยที่สุด” หรือก็คือทางที่ คุ้มค่าที่สุด

ลองนึกภาพว่าคุณอยากเดินทางจากบ้านไปมหาวิทยาลัย แล้วมีหลายเส้นทางให้เลือก บางเส้นทางอาจจะใกล้แต่รถติดมาก หรือค่ารถแพงกว่า บางเส้นทางอาจจะอ้อมหน่อย แต่ประหยัดทั้งเงินและเวลาในภาพรวม UCS จะช่วยคุณตัดสินใจว่า เส้นทางไหน “เหมาะที่สุด” ในแง่ของต้นทุนโดยรวม

แนวคิดของ UCS ก็คือ มันจะเลือกทางที่มี “ต้นทุนสะสม” น้อยที่สุดในทุก ๆ ขั้นตอน เช่น ถ้าเราต้องเดินผ่านเมืองหลายเมือง มันจะเลือกเมืองต่อไปที่รวมค่าผ่านทาง ค่าเดินทาง หรือระยะทาง แล้วมีค่าน้อยที่สุดก่อนเสมอ ต่างจากอัลกอริทึมอื่น ๆ อย่าง DFS หรือ BFS ที่ไม่สนเรื่องต้นทุนเลย

หลักการทำงาน UCS แบบเข้าใจง่ายๆเลยนะ

โดย “เริ่มจากโหนดเริ่มต้น” จากนั้น “ใช้ Priority Queue” จัดการโหนดที่ต้องไปเยี่ยม โดย “เรียงตามค่าcostสะสม” ต่อด้วย “ขยายโหนดที่มี cost น้อยที่สุดก่อน” และ “หยุดเมื่อถึง goal”

UCS ใช้ที่ไหนได้บ้าง?

Uniform Cost Search ไม่ได้ใช้แค่ในหนังสือเรียนหรือโจทย์เท่านั้นนะคะ แต่มันถูกนำไปใช้จริงในหลายระบบรอบตัวเราเลย ยกตัวอย่างง่าย ๆ ที่หลายคนอาจจะคาดไม่ถึง
นั่นก็คือ ระบบนำทาง (Navigation System) อย่างเช่น Google Maps หรือแอปแผนที่อื่น ๆ ที่เราคุ้นเคย UCS จะช่วยในการหาทางที่ประหยัดเวลาที่สุดหรือต้นทุนน้อยที่สุด เช่น เส้นทางที่หลีกเลี่ยงค่าทางด่วน หรือเส้นทางที่น้ำมันหมดน้อยที่สุด

สรุปง่ายๆเลยคือ UCS เหมาะกับทุกสถานการณ์ที่เราต้องเลือก “เส้นทาง” หรือ “ทางเลือก” ที่มี “ต้นทุนรวมต่ำที่สุด” ไม่ว่าจะเป็นต้นทุนเวลา, เงิน, พลังงาน หรือแม้แต่ความเสี่ยง

ต่อไปเรามาดูการทำงานของ Uniform Cost Search ในรูปแบบของcodeกันเถอะ

เราจะเริ่มจากการสร้างฟังก์ชัน uniform_cost_search ที่รับโครงสร้างของ กราฟ เข้ามา พร้อมจุดเริ่มต้น (start) และจุดหมาย (goal) แล้วให้มันหาทางที่ "ต้นทุนรวมต่ำที่สุด"

โดยในโค้ดจะมี 7 ขั้นตอน
ขั้นตอนที่ 1 เริ่มจาก Import ตัวช่วยก่อน

การนำเข้าโมดูลที่จำเป็น ซึ่งจากในโค้ดการ import heapq ถูกนำเข้าเพื่อใช้ในการจัดการ priority queue ซึ่งช่วยให้สามารถดึง path ที่มี cost ต่ำที่สุดได้อย่างมีประสิทธิภาพ

เกล็ดความรู้เล็กๆ Priority Queue คือ คิวพิเศษที่ หยิบตัวที่ “สำคัญที่สุด” ออกก่อน ในที่นี้ “สำคัญ” หมายถึง มีค่า priority ต่ำสุด เช่น ต้นทุนน้อยที่สุดใน UCS ก็จะถูกดึงออกมาก่อนเสมอนะ

ขั้นตอนที่ 2 ฟังก์ชันหลัก uniform_cost_search()

ฟังก์ชัน uniform_cost_search จะพารามิเตอร์คือ

graph คือ กราฟที่แสดงการเชื่อมต่อระหว่างโหนดต่าง ๆ ในรูปแบบของ dictionary
start คือ โหนดเริ่มต้น
goal คือ โหนดเป้าหมาย

ต่อมาการใส่จุดเริ่ม [start] ลงใน queue พร้อมต้นทุนเริ่มต้นคือ 0 visited จะเก็บ node ที่เคยผ่านแล้ว เพื่อไม่ให้วนซ้ำ

ขั้นตอนที่ 3 เข้าสู่ลูปสำรวจ

เราหยิบเส้นทางที่ cost น้อยที่สุด ออกมาแล้วดูว่า node ปลายทางตอนนี้เป็นอะไร

ขั้นตอนที่ 4 ตรวจว่าเคยไป node นี้หรือยัง?

ถ้าไปแล้วก็ skip แต่ถ้ายัง ก็ mark ว่าไปมาแล้วนะ

ขั้นตอนที่ 5 เจอเป้าหมายหรือยัง?

ถ้าใช่ก็ไม่ต้องหาต่อแล้วจ้า ส่งคำตอบกลับเลย โดยจะได้ทั้ง path (เส้นทางทั้งหมด) และ cost (ต้นทุนรวม)

ขั้นตอนที่ 6 ถ้ายังไม่เจอ ก็ขยายไปเพื่อนบ้านต่อ

ลูปดูเพื่อนบ้านของ node ปัจจุบัน ถ้ายังไม่เคยไปก็สร้างเส้นทางใหม่ พร้อมคำนวณต้นทุนใหม่ใส่เข้า priority queue เพื่อรอให้ UCS หยิบไปพิจารณาในรอบถัดไป

ขั้นตอนที่ 7 ถ้าไม่เจอทางไป

ถ้าหาไม่เจอจริง ๆ ก็ return ค่า null และต้นทุนเป็น ∞ (แปลว่าไปไม่ได้)

ตัวอย่างการใช้งาน UCS กับกราฟกัน

นี่คือกราฟที่เขียนด้วย Dictionary

โดยใช้ key เป็นชื่อ node นั่นก็คือ 'A','B','C','D','E','F','G'
ส่วน value เป็น list ของ tuple แต่ละ tuple แสดงว่า node นี้เชื่อมกับใคร และระยะทาง (cost) เท่าไหร่ เช่น

หมายความว่า 'A' เชื่อมไปหา 'B' ด้วย cost 1 และ 'C' ด้วย cost 4

ต่อไปมาดูผลลัพธ์ที่ได้กัน

ผลลัพธ์
Path ที่ถูกที่สุด คือ A → B → E → G
ต้นทุนรวม 1 + 5 + 2 = 8

โดยจะเริ่มต้นที่ 'A' ปลายทางคือ 'G'
จากนั้น ฟังก์ชัน uniform_cost_search() จะหาทางที่ cost รวมทั้งหมดน้อยที่สุด แล้วส่งกลับทั้ง path และ cost

เราได้ศึกษาเรื่องของกราฟกันไปแล้ว แต่ความจริงแล้ว Uniform Cost Search (UCS) ไม่ได้จำกัดอยู่แค่กราฟเท่านั้นนะ! วันนี้เราเลยขอพาไปดูตัวอย่างแบบง่าย ๆ ที่ใคร ๆ ก็เข้าใจได้ โดยไม่ต้องวาดกราฟเลยสักนิด

ตัวอย่าง Uniform Cost Search แบบไม่ใช้กราฟ

โดยสิ่งที่เราต้องการคือการเปลี่ยนเลขจาก 0 ให้กลายเป็น 15 ด้วยการบวกเลขที่มีต้นทุนต่างกัน แล้วหาวิธีที่ "คุ้มค่าที่สุด"

โดยในโค้ดจะมี 7 ขั้นตอน

ขั้นตอนที่ 1 เริ่มจาก Import ตัวช่วยก่อน

ใช้ priority queue เพื่อให้เราสามารถดึง path ที่มีต้นทุนน้อยที่สุดมาคำนวณก่อนได้ คล้าย ๆ กับการเข้าคิวแบบ “ใครถูกที่สุดมาก่อน” นั่นเอง

ขั้นตอนที่ 2 สร้างฟังก์ชัน uniform_cost_search_number()

เราสร้าง queue ขึ้นมา และใส่ node เริ่มต้น (เลข 0) เข้าไป พร้อมต้นทุนเริ่มต้น 0
visited คือชุดสำหรับเก็บตัวเลขที่เราเคยไปแล้ว เพื่อไม่ให้วนลูปซ้ำซาก (เช่น ไปๆมาๆที่เลขเดิม)

โครงสร้างข้อมูลใน pq จะเก็บเป็น 3 ค่า คือ

cost = ต้นทุนรวมจนถึงตอนนี้
current = เลขปัจจุบันที่เราอยู่
path = รายชื่อเลขที่เราผ่านมา

ขั้นตอนที่ 3 วนลูปสำรวจเส้นทาง

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

ขั้นตอนที่ 4 ตรวจสอบและขยายเส้นทางต่อ

ถ้าเลขนี้เรายังไม่เคยเจอมาก่อน (not in visited) เราจะเริ่มสร้าง “ทางเลือกใหม่”
moves คือทางเลือกการเดินที่เรามี (เพิ่ม 1, 2 หรือ 5 พร้อมต้นทุน)
เราจะเอาเส้นทางใหม่ที่ได้ ไปใส่ต่อใน priority queue โดยคิด ต้นทุนรวมใหม่ แล้วเก็บ path ไว้ด้วย

จุดนี้คือ การขยาย node แบบที่ UCS ทำกับกราฟนั่นแหละ แต่เราทำกับ เลขธรรมดา แทน

ต่อไปก็มาดูผลลัพธ์ของโค้ดนี้กันเลย

ทำไมผลลัพธ์ถึงเป็นแบบนี้?

ถึงแม้ +1 จะดูเหมือนถูกที่สุด แต่ต้องทำถึง 15 ครั้งเลยนะ = ต้นทุนรวม 15
UCS จึงเลือกใช้ +5 ซึ่งใช้ต้นทุนแค่ 3 ต่อครั้ง และ 5+5+5 = 15 พอดี

ดังนั้นเส้นทาง [0, 5, 10, 15] จึงเป็น เส้นทางที่ “ต้นทุนต่ำที่สุด” นั่นเอง

สรุป
จากบทความนี้พูดถึง Uniform Cost Search (UCS) ซึ่งเป็นเทคนิคพื้นฐานในด้าน AI สำหรับการค้นหาเส้นทางที่มีต้นทุนรวมน้อยที่สุด โดยต่างจาก DFS หรือ BFS ตรงที่ UCS คำนึงถึง “ต้นทุนสะสม” ในแต่ละเส้นทางด้วย เหมาะมากกับสถานการณ์ที่ต้องการหาทางเลือกที่ “คุ้มค่าที่สุด” ไม่ว่าจะเป็นเส้นทางในแผนที่หรือกระบวนการตัดสินใจอื่น ๆ บทความได้อธิบายหลักการทำงานแบบเข้าใจง่ายๆ พร้อมตัวอย่างทั้งในรูปแบบกราฟและตัวเลข เพื่อให้เห็นภาพว่า UCS ใช้งานได้หลากหลายจริง ๆ ผู้อ่านจะได้เข้าใจทั้งแนวคิด วิธีทำงานของ UCS และสามารถนำไปปรับใช้กับปัญหาต่าง ๆ ที่ต้องการเลือกทางเลือกที่ดีที่สุดในเชิงต้นทุน ไม่ว่าจะเป็นเงิน เวลา หรือทรัพยากรอื่น ๆ ได้อย่างมีประสิทธิภาพ หวังว่าผู้อ่านจะได้รับความรู้แล้วสามารถนำไปต่อยอดในด้านต่างๆกันได้นะคะ

reference 1 : https://www.geeksforgeeks.org/uniform-cost-search-ucs-in-ai/
reference 2 : https://stackoverflow.com/questions/43354715/uniform-cost-search-in-python
reference 3 : https://www.educative.io/answers/what-is-uniform-cost-search
reference 4 : https://images.app.goo.gl/2eSzyxyB1Roy8Ui99