สุดมันกับ A* Search Algorithm -_-“

ตอนนี้งานค่อนข้างเยอะเลย -_-" เรียน Software Engineering แล้วทำ Term Project ที่เป็นระบบแผนที่ ตอนนี้หา Algorithm ที่มาใช้ในการค้นหาเส้นทางที่ดีที่สุด และเหมาะสมที่สุด หาไป หามา ก็ได้ A* (A-Star) Search Algorithm ซึ่งเป็น graph search algorithm ที่ค่อนข้างจะเข้าท่ามาก คิดโดย Peter Hart, Nils Nilsson และ Bertram Raphael ในปี 1968 แม้ว่าจะไม่เคยเรียนมาก่อน ก็ด้วยเหตุการณ์จำเป็น เลยต้องศึกษาเอาไว้ เดี่ยวทำระบบไม่ได้แล้วจะยุ่ง

โดย A* เนี่ย มันเป็น Algorithm ที่ใช้ในการหาเส้นทางที่ดีที่สุด (บอกไปแล้วจะบอกทำไมอีกหว่า -_-") คือมันจะมีทั้งหมด 3 ส่วนที่ทำให้เส้นทางต่าง ๆ นั้นถูกตัดสินใจให้ใช้ หรือไม่ให้ใช้โดย

1. Heuristic : คือค่าสำหรับการตัดสินใจในการผ่านจุดใด ๆ โดยให้เกณฑ์เป็นตัวเลข
2. Cost : คือค่าใด ๆ ที่บ่งบอกถึงค่าใช้จ่าย หรือระยะเส้นทางที่ใช้เวลา หรืออะไรก็แล้วแต่ ที่ทำให้เส้นทางนั้นเหมาะสมต่อการใช้หรือไม่ โดยให้เกณฑ์เป็นตัวเลข
3. Priority : เป็นค่าที่ได้จาก Heuristic + Cost จะได้เป็นค่า Priority ออกมา โดยจะเป็นตัวบ่งบอกว่าเส้นทางดังกล่าวนั้นเหมาะสมที่จะผ่านหรือไม่ โดยวัดจากตัวเลข

เรากำหนดให้

• Heuristic = H
• Cost = C
• Priority = F

โดยตัวอย่างนี้เรากำหนดจุดเริ่มต้นคือ S และจุดหมายปลายทางคือ G

• เส้นสีเหลียงคือเส้นทางที่ดีที่สุด
• เส้นสีส้มคือเส้นทางที่น่าจะเป็นไปได้
• สีเขียวคือจุดปลายทาง
• สีน้ำเงินคือจุดเริ่มต้น

1. S มีค่าคือ H:12,C:0,F:12 โดยมีจุดเชื่อมต่อสองจุดคือ A และ B
   
2. เราเลยตัดสินใจว่าจะทำการทดสอบว่าเส้นทางไหนมี Priority น้อยที่สุดในกลุ่ม (ในที่นี้คือ 2 ตัวเลือกคือ S-B และ S-A ) ซึ่งมีค่าดังต่อไปนี้ S-B มีค่า H:5,C:8,F:13 และ S-A H:5,C:10,F:15
   
3. ในตอนนี้เราตัดสินใจได้แล้วว่าเราจะไป S-B เพราะมีค่า F น้อยที่สุดในกลุ่ม เมื่อถึง S-B แล้วก็ทำการทดสอบเส้นทางอีกครั้งโดยมีจุดเชื่อมต่อ 2 จุดที่ต่อกับ B คือ D และ G เราก็จะได้ค่าที่ B-D และ B-G คือ S-B-D มีค่า H:2,C:16,F:18 และ S-B-G H:0,C:24,F:24 แต่เรายังมีค่าเก่าของ SA อยู่คือ H:5,C:10,F:15 ซึ่งเราต้องเอามาคิดด้วยก็จะได้ 3 ตัวเลือก โดยในตัวเลือกครั้งนี้นั้น S-A มีค่า F น้อยที่สุดในกลุ่ม (มีตัวเลือก 3 ตัวเลือกนะ อย่าลืมหล่ะ ไม่ใช่ 2 ) และ G นั้นมีการเชื่อต่อกับเส้นทางอื่น ๆ อยู่แสดงว่าน่าจะมีเส้นทางที่มีความเป็นไปได้ว่าจะดีกว่า S-B-G ด้วย
   
4. เมื่อถึง S-A แล้วก็ทำการทดสอบเส้นทางที่เชื่อมต่อกับ A ซึ่งมีเส้นทางอยู่ 2 เส้นทางคือ C และ G ก็จะได้ S-A-C ที่มีค่า H:5,C:12,F:17 และ S-A-G ที่มีค่า H:0,C:20,F:20 เราอย่าลืมว่าเรามีค่าเก่าอยู่อีก 2 ตัวคือ S-B-D มีค่า H:2,C:16,F:18 และ S-B-G H:0,C:24,F:24 แต่ S-B-G นั้นมีค่ามากที่สุด และยังมีจุด G ซึ่งซ้ำกับ S-A-G ที่มีค่าน้อยกว่า เราเลยตัดทิ้งไปเพราะจุดหมายปลายทางคือ G ซึ่งเราต้องการหาค่าเส้นทางที่ไปถึง G ที่น้อยที่สุดเท่านั้นจึงตัด S-A-G ทิ้งไป โดยในที่นี้ ค่า F ของ S-A-C นั้นน้อยที่สุดในกลุ่ม เราก็เลือกให้เดินต่อไปที่ S-A-C โดย S-A-G นั้นยังมีเส้นทางอื่นที่เชื่อต่อแสดงว่าน่าจะมีเส้นทางที่ดีกว่าอยู่
   
5. เมื่อถึง S-A-C เรามีเส้นทางอยู่ 2 เส้นคือ E และ G โดยที่ S-A-C-E นั้นมีค่า H:2,C:15,F:17 และ S-A-C-G  นั้นมีค่า H:5,C:21,F:26 และค่าที่เหลืออยู่คือ S-B-D มีค่า H:2,C:16,F:18 และ S-A-G H:0,C:20,F:20 โดยที่ค่า F ของ S-A-C-E นั้นน้อยที่สุดในกลุ่มทั้ง 4 ตัวเราก็จะเลือกเดินไปที่ E และ S-A-C-G ก็ต้องนำออกจากกลุ่มด้วยเพราะ S-A-G นั้นมีค่า F น้อยกว่า
   
6. โดยเมื่อถึง E แล้ว เส้นทางมีเส้นเดียวคือเส้น S-A-C-E-G ซึ่งมีค่า H:0,C:17,F:17 ซึ่งน้อยกว่า SBD H:2,C:16,F:18 และ S-A-G มีค่า H:0,C:20,F:20 เราก็จะเลือกเส้นทาง S-A-C-E-G เป็นเส้นทางที่ดีที่สุดในการเดินทางจาก S ไปถึง G โดยใช้ Priority ที่ 17, Cost ที่ 17 และ Heuristic ที่ 0
   

Animation สามารถทดลองเล่นได้ที่ JSearch demo ครับ
ซึ่งวิธีการ A* นั้นส่วนใหญ่จะใช้ในการเดินทางของ AI ในเกมส์ต่าง ๆ โดยหลักการนี้มีเขียนไว้ที่ Game Character Path Finding in Java โดยใช้ในการเขียนการค้นหาคู่ต่อสู้ในแผนที่ของเกมส์โดยใช้ Heuristic ที่เปลี่ยนแปลงไปโดยตลอด และเส้นทางที่น่าจะเป็นไปได้ หรือใช้ระยะทางในการกำหนดค่าของ Cost ในการค้นหาศัตรูด้วย ส่วน Code นั้นเดี่ยวขอเวลาเขียนก่อน ตอนนี้ได้ Idea เท่านั้น -_-"