A* Search Algorithm
การประมาณเส้นทางที่สั้นที่สุดในสถานที่ต่างๆในชีวิตประจำวัน
ในแผนที่ต่างๆ
หรือในเกมส์ที่มีสิ่งกีดขวางต่างๆมากมาย
หากพิจารณา
2D Grid ที่มีสิ่งกีดขวางหรืออุปสรรคมากมายและพวกเราเริ่มต้นจากจุดกำเนิด(จุดสีแดง)เพื่อไปยังจุดมุ่งหมาย(จุดสีเขียว)
รูปภาพที่ 1. 2D Grid
ที่มา :
https://www.geeksforgeeks.org/a-search-algorithm/
A* Search
Algorithm คืออะไร
A* Search algorithm
เป็นหลักการที่ได้รับความนิยมที่นำไปใช้ในการค้นหาเส้นทางต่างๆและการนำไปใช้ในเส้นทางผ่านต่างๆในกราฟ
ทำไมต้องเป็น A* Search
Algorithm
เพราะว่า A* Search Algorithm ไม่เหมือนกับหลักการเดินทางผ่านอื่นๆ มันเป็นอัลกอลิทึมที่ดี มีรายละเอียดที่ชัดเจน และมีประโยชน์ในเกมส์มากมายและในเว็บแผนที่ต่างๆใช้อัลกอลิทึมนี้เพื่อค้นหาเส้นทางที่สั้นที่สุดได้อย่างมีประสิทธิภาพ(การประมาณ)
คำอธิบาย
พิจารณาตารางสี่เหลี่ยมที่มีสิ่งกีดขวางต่างๆมากมายและพวกเราจะเริ่มจากจุดเริ่มต้นเพื่อไปยังจุดเป้าหมายอย่างรวดเร็วที่สุดถ้าเป็นไปได้
เราจึงใช้ A* Search Algorithm
มาเป็นตัวช่วย
f คือ
ตัวแปรที่เท่ากับผลรวมของ 2 ตัวแปรอื่นๆ คือ g และ h มันคือการเลือกจุดหรือเซลล์ที่ค่า
f ต่ำที่สุด กระบวนการเลือกจุดหรือเซลล์เหล่านี้คือ
การที่เรากำหนด g และ h ให้เป็นเพียงค่าที่เป็นไปได้ตามตัวอย่างข้างล่างนี้
g คือ การประมาณค่าของการเคลื่อนย้ายจากจุดเริ่มต้นไปยังช่องสี่เหลี่ยมที่อยู่
บนตาราง
บนตาราง
h คือ การประมาณค่าของการเคลื่อนย้ายจากช่องสี่เหลี่ยมในตารางไปยังจุดเป้าหมาย
สิ่งนี้มักถูกเรียกว่า heuristic คือการคาดเดาที่มีหลักการ
เราจะไม่ทราบระยะทางจริงจนกว่าเราจะได้พบเส้นทางกับเส้นทางนั้นจริงๆ มันมีวิธีการคำนวณค่า h ได้หลากหลายวิธี
ตัวอย่าง Algorithm
// A* Search
Algorithm
1. Initialize the open list
2. Initialize the closed list
put the starting node on the open
list (you can leave its f at zero)
3. while the open list is not empty
a) find the node with the least f on
the open list, call it "q"
b) pop q off the open list
c) generate q's 8 successors and set their
parents to q
d) for each successor
i) if successor is the goal, stop
search
successor.g
= q.g + distance between
successor and q
successor.h
= distance from goal to
successor (This can be done using
many
ways, we will discuss three
heuristics-
Manhattan, Diagonal and Euclidean
Heuristics)
successor.f
= successor.g + successor.h
ii) if a node with the same position as
successor is in the OPEN list which
has a
lower f than successor,
skip this successor
iii) if a node with the same position
as
successor is in the CLOSED list which has
a lower f
than successor, skip this successor
otherwise, add the node to the open list
end (for loop)
e) push q on the closed list
end (while loop)
รูปภาพที่ 3. ตัวอย่างการใช้ A*
Search algorithm ในการค้นหาเส้นทาง
ที่มา : https://www.geeksforgeeks.org/a-search-algorithm/
ขอบคุณแหล่งข้อมูลจาก
https://www.geeksforgeeks.org/a-search-algorithm/
ความคิดเห็น
แสดงความคิดเห็น