เนื้อหาที่เขียนในครั้งนี้เป็นเนื้อหาด้าน Programming เกี่ยวกับ Algorithm ตัวหนึ่งที่ชื่อว่า A star ซึ่ง Algorithm ตัวนี้เป็น Algorithm สำหรับการแก้ปัญหาในการหาเส้นทางจากต้นทางไปปลายทาง(Routing) ยกตัวอย่างการนำ A star ไปใช้ ที่เห็นได้ชัด คือ การหาเส้นทางการเดินทางบนแผนที่ จากอนุสาวรีชัย ไป วัดพระแก้ว เป็นต้น
เมื่อเข้าใจแล้วว่า A star Algorithm ไปใช้เกี่ยวกับอะไร ขั้นต่อไปก็จะอธิบายถึงหลักการทำงานแต่ก่อนที่จะอธิบายหลักการทำงานของ A star Algorithm ผมขอให้ผู้อ่านลองจินตนาการว่า ตอนนี้คุณถูกปล่อยอยู่ในป่าใหญ่ ซึ่งรอบๆเต็มไปด้วยต้นไม้และทะเลสาบ ในตัวคุณมีแต่แผนที่ และเข็มทิศ คุณต้องการออกจากป่านี้
เมื่อคุณดูไปที่แผนที่คุณเห็นว่ามีหมู่บ้านอยู่ใกล้ๆ คุณจึงคิดที่จะไปหมู่บ้านแห่งนั้นเพื่อขอความช่วยเหลือ
แต่ก่อนที่คุณจะเดินทางไปหมู่บ้านได้นั้น คุณต้องรู้ข้อมูลสามส่วนหลักๆ คือ
-ตำแหน่งหมู่บ้าน
-ตำแหน่งเรา ณ ปัจจุบัน ซึ่งอยู่ใกล้ทะสาบ
-ทิศทางที่เราจะไป ซึ่งสามารถใช้เข็มทิศในการบอกทิศทาง
ในขณะเดินทางบางครั้งคุณอาจจะเจอทางตันเช่น ข้างหน้าเป็นเหว, เป็นแม่น้ำ, โคลนดูด เป็นต้น แต่คุณไม่หมดความพยายามจนในที่สุดคุณก็ถึงหมู่บ้าน
หลักการทำงาน A star ก็จะคล้ายกับตัวอย่างข้างบนคือ เราจำเป็นที่จะต้องรู้ตำแหน่งเริ่มต้น ตำแหน่งปลายทาง และจะต้องมีฟังก์ชันที่ชื่อ ฮิวริสติก (heuristic) ซึ่งเป็นฟังก์ชันสำหรับการประมาณค่าระยะทางในการหาเส้นทางที่น้อยที่สุดจากตำแหน่งเริ่มต้นไปยังตำแหน่งปลายทาง(ถ้าจะให้เปรียบเทียบก็เหมือนกับเรามีเข็มทิศไว้ประมาณการเท่านั้น ว่าควรเดินไปเส้นทางใหน แต่ก็ไม่แน่ชัดว่าเส้นทางนั้นเป็นเส้นทางที่ไปถึงตำแหน่งเป้าหมายจริงๆ ซึ่งบางครั้งอาจจะเป็นเส้นทางที่เจอทางตันเช่น เหว, แม่น้ำ, โคลนดูด เป็นต้น)
หลักการทำงานของ A star Algorithm จะมีหลักการทำงานคร่าวๆดังนี้ตามลำดับครับ
1. A star จะทำการดูเส้นทางรอบๆตัวเองก่อนว่าสามารถเดินได้ทางใหนบ้างและจะทำการเลือกเส้นทางที่คาดว่าอยู่ใกล้ตำแหน่งปลายทางโดยอาศัยฟังก์ชันฮิวริสติก (heuristic) มาช่วยในการพิจราณา (คล้ายๆกับการใช้เข็มทิศในการพิจารณาเลือกเส้นทางที่จะไป) เพื่อเป็นการคาดว่าเส้นทางที่เลือกน่าจะเป็นเส้นทางที่ใกล้ที่สุดและสามารถไปยังตำแหน่งเป้าหมายได้
2.แต่ถ้าหากเส้นทางที่เลือกเป็นเส้นทางที่ผิดเป็นทางตัน ก็จะทำการเลือกเส้นทางอื่นโดยอาศัย
ค่าฮิวริสติก (heuristic) เข้ามาช่วยพิจารณาที่คาดว่าเส้นทางนั้นเป็นเส้นทางที่ใกล้ตำแหน่งเป้าหมายรองลงมา
ทำข้อ 1. และ ข้อ 2 ซ้ำไปเรื่อยๆ โดยไม่เลือกเส้นทางเดิมที่เคยผ่านมา จนเจอตำแหน่งเป้าหมายในที่สุด
และนี่ก็คือหลักการทำงานของ A star Algorithm อย่างคร่าวๆครับ
หลักการทำงาน A star ก็จะคล้ายกับตัวอย่างข้างบนคือ เราจำเป็นที่จะต้องรู้ตำแหน่งเริ่มต้น ตำแหน่งปลายทาง และจะต้องมีฟังก์ชันที่ชื่อ ฮิวริสติก (heuristic) ซึ่งเป็นฟังก์ชันสำหรับการประมาณค่าระยะทางในการหาเส้นทางที่น้อยที่สุดจากตำแหน่งเริ่มต้นไปยังตำแหน่งปลายทาง(ถ้าจะให้เปรียบเทียบก็เหมือนกับเรามีเข็มทิศไว้ประมาณการเท่านั้น ว่าควรเดินไปเส้นทางใหน แต่ก็ไม่แน่ชัดว่าเส้นทางนั้นเป็นเส้นทางที่ไปถึงตำแหน่งเป้าหมายจริงๆ ซึ่งบางครั้งอาจจะเป็นเส้นทางที่เจอทางตันเช่น เหว, แม่น้ำ, โคลนดูด เป็นต้น)
หลักการทำงานของ A star Algorithm จะมีหลักการทำงานคร่าวๆดังนี้ตามลำดับครับ
1. A star จะทำการดูเส้นทางรอบๆตัวเองก่อนว่าสามารถเดินได้ทางใหนบ้างและจะทำการเลือกเส้นทางที่คาดว่าอยู่ใกล้ตำแหน่งปลายทางโดยอาศัยฟังก์ชันฮิวริสติก (heuristic) มาช่วยในการพิจราณา (คล้ายๆกับการใช้เข็มทิศในการพิจารณาเลือกเส้นทางที่จะไป) เพื่อเป็นการคาดว่าเส้นทางที่เลือกน่าจะเป็นเส้นทางที่ใกล้ที่สุดและสามารถไปยังตำแหน่งเป้าหมายได้
2.แต่ถ้าหากเส้นทางที่เลือกเป็นเส้นทางที่ผิดเป็นทางตัน ก็จะทำการเลือกเส้นทางอื่นโดยอาศัย
ค่าฮิวริสติก (heuristic) เข้ามาช่วยพิจารณาที่คาดว่าเส้นทางนั้นเป็นเส้นทางที่ใกล้ตำแหน่งเป้าหมายรองลงมา
ทำข้อ 1. และ ข้อ 2 ซ้ำไปเรื่อยๆ โดยไม่เลือกเส้นทางเดิมที่เคยผ่านมา จนเจอตำแหน่งเป้าหมายในที่สุด
และนี่ก็คือหลักการทำงานของ A star Algorithm อย่างคร่าวๆครับ
