เมนูนำทาง
การค้นหาแบบเอสตาร์ รหัสเทียมอัลกอรึทึมสามารถแสดงด้วยรหัสเทียมได้ดังนี้
function A*(start,goal) closedset := the empty set // เซตของโหนดที่พิจารณาแล้ว openset := {start} // เซตของโหนดที่ยังไม่ได้พิจารณา เริ่มด้วยใส่โหนดเริ่มต้นลงไป came_from := the empty map // เพื่อหาโหนดที่ผ่านมา ซึ่งจะใช้ในการระบุเส้นทาง g_score[start] := 0 // ค่าระยะทางของจุดเริ่มต้น h_score[start] := heuristic_cost_estimate(start, goal) // เป็นฟังก์ชันที่ใช้หาค่าประมาณฮิวริสติก f_score[start] := g_score[start] + h_score[start] // ค่าประมาณการของจุดเริ่มไปยังจุดเป้าหมาย while openset is not empty x := the node in openset having the lowest f_score[] value if x = goal return reconstruct_path(came_from, came_from[goal]) remove x from openset add x to closedset foreach y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_score[x] + dist_between(x,y) if y not in openset add y to openset tentative_is_better := true else if tentative_g_score < g_score[y] tentative_is_better := true else tentative_is_better := false if tentative_is_better = true came_from[y] := x g_score[y] := tentative_g_score h_score[y] := heuristic_cost_estimate(y, goal) //ประมาณหาค่าฮิวริสติกจากจุด y ไปถึงเป้าหมาย f_score[y] := g_score[y] + h_score[y] //ปรับปรุงค่าการประมาณ return failure function reconstruct_path(came_from, current_node) if came_from[current_node] is set p = reconstruct_path(came_from, came_from[current_node]) return (p + current_node) else return current_node
หมายเหตุ รหัสเทียมด้านบนนี้ถือว่าฮิวริสติกฟังก์ชันเป็นฮิวริสติกแบบโมโนโทนิกซึ่งเป็นกรณีที่พบบ่อยในหลายๆ ปัญหาเช่น ปัญหาการหาเส้นทางที่สั้นที่สุดในระบบเครือข่าย อย่างไรก็ดีหากฮิวริสติกไม่ได้เป็นแบบโมโนโทนิกแล้ว โหนดในเซตปิดอาจใช้ซ้ำ ซึ่งอาจเพิ่มค่าระยะทางได้ ในอีกนัยหนึ่งหากวิธีแก้ปัญหานั้นมีอย่างแน่นอน หรือมีการปรับขั้นตอนวิธีให้โหนดใหม่อยู่ในเซตเปิดเมื่อมีค่า f ต่ำกว่าการวนซ้ำทั้งหมดที่ผ่านมาแล้ว อาจไม่ต้องใช้เซตปิด และสามารถใช้ขั้นตอนวิธีค้นหาต้นไม้ได้
ในตัวอย่างนี้สมมติให้โหนดแต่ละโหนดเป็นเมืองที่ต่อกับเมืองอื่นด้วยถนนและ h(x) เป็นเส้นตรงที่ระบุระยะทางไปยังจุดเป้าหมายตัวอย่างนี้ใช้ สีเขียวคือจุดเริ่มต้น สีฟ้าคือจุดเป้าหมาย สีส้มคือจุดที่ผ่านแล้ว และใช้สัญลักษณ์ ",” แสดงจุดทศนิยม
เมนูนำทาง
การค้นหาแบบเอสตาร์ รหัสเทียมใกล้เคียง
การค้าประเวณี การค้าประเวณีเด็ก การค้าประเวณีในประเทศไทย การค้นหาแบบทวิภาค การค้าเครื่องเทศ การค้นหาแบบเอสตาร์ การค้นหาและกู้ภัยในเขตเมือง การค้นหาในแนวกว้าง การค้าระหว่างประเทศ การค้นหาในแนวลึกแบบวนเพิ่มความลึกแหล่งที่มา
WikiPedia: การค้นหาแบบเอสตาร์ http://code.google.com/p/a-star-algorithm-implemen... http://code.google.com/p/jianwikis/wiki/AStarAlgor... http://www.heyes-jones.com/astar.html http://www.eecs.berkeley.edu/~klein/ http://portal.acm.org/citation.cfm?id=1017140 http://portal.acm.org/citation.cfm?id=3830&coll=po... //doi.org/10.1109%2FTSSC.1968.300136 //doi.org/10.1145%2F3828.3830 http://www.policyalmanac.org/games/aStarTutorial.h...