รหัสเทียม ของ การค้นหาแบบเอสตาร์

อัลกอรึทึมสามารถแสดงด้วยรหัสเทียมได้ดังนี้

 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...