การค้นหาแบบเอสตาร์

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีเอสตาร์ () เป็นขั้นตอนวิธีที่ใช้ในการหาเส้นทางและการท่องในกราฟซึ่งเป็นกระบวนการในการหาเส้นทางระหว่างจุด (เรียกจุดดังกล่าวว่า "โนด" (node)) ขั้นตอนวิธีนี้มีประสิทธิภาพและความแม่นยำสูงจึงมีการนำไปใช้งานอย่างแพร่หลาย ผู้นิยามขั้นตอนวิธีนี้คือ ปีเตอร์ ฮาท์, นิล นีลสัน และเบิร์ดแรม เรฟเซด ซึ่งนิยามไว้ในปี ค.ศ. 1968 ขั้นตอนวิธีนี้เป็นส่วนขยายของขั้นตอนวิธีของไดค์สตราซึ่งสร้างในค.ศ. 1959 เอสตาร์มีประสิทธิภาพที่ดีกว่า (โดยขึ้นกับเวลา) จากการนำเทคนิคฮิวริสติกมาใช้ แต่ถ้าฮิวริสติกเป็นแบบโมโนโทนจะทำให้ความเร็วในการทำงานเท่ากับขั้นตอนวิธีของไดค์สตรา

นิยาม 
เอสตาร์ใช้การค้นหาตามแนวกว้างและหาเส้นทางที่มีระยะทางน้อยที่สุดจากโหนดแรกไปสู่โหนดเป้าหมายซึ่งอาจจะมีได้หลายโหนด โดยใช้ฟังก์ชันฮิวริสติกแบบค่าของระยะทาง (ใช้สัญลักษณ์ ) เพื่อที่จะหาลำดับการผ่านโหนดในกราฟ โดยฟังก์ชันดังกล่าวเป็นผลรวมของสองฟังก์ชันดังนี้
 ค่าระยะทางทางจากโหนดเริ่มต้นมายังโหนดปัจจุบัน (ใช้สัญลักษณ์ )
 ค่าประมาณฮิวริสติกที่ยอมรับได้ ของระยะทางที่จะถึงจุดหมาย(ใช้สัญลักษณ์ )
ซึ่งฟังก์ชัน  ที่เป็นส่วนหนึ่งของ  จะต้องมีฮิวริสติกที่ยอมรับได้ กล่าวคือค่าประมาณฮิวริสติกยอมรับได้จะต้องไม่สูงกว่าระยะทางจากจุดเริ่มต้นไปยังจุดสิ้นสุด ตัวอย่างเช่นในการจัดเส้นทางซึ่งมีทั้งเส้นทางที่เป็นเส้นตรงและเส้นโค้ง  อาจแทนด้วยเส้นตรงจากจุดเริ่มต้นไปยังจุดสิ้นสุด ซึ่งหากวัดทางกายภาพแล้ว เส้นตรงที่เชื่อมจุดสองจุดจะมีระยะทางน้อยที่สุดในบรรดาเส้นเชื่อมทั้งหมดที่เชื่อมระหว่างจุดเริ่มต้นไปยังจุดสิ้นสุด

ถ้าฮิวริสติกของ h สอดคล้องกับเงื่อนไข  สำหรับทุกเส้นเชื่อม x,y ในกราฟ (เมื่อ d หมายถึงความยาวของเส้น) จะเรียก h ว่าเป็นฮิวริสติกชนิดโมโนโทน หรือฮิวริสติดแบบเสถียร ซึ่งในกรณีดังกล่าวเอสตาร์สามารถมีประสิทธิภาพสูงเทียบเท่าได้กับการใช้ขั้นตอนวิธีของเดสสตาร์แบบปรับแต่งให้  ซึ่งไม่มีโหนดใด ๆ จะต้องถูกดำเนินการมากกว่าหนึ่งครั้ง นอกจากนี้เอสตาร์ยังสามารถปรับปรุงเป็นรูปทั่วไปของการค้นหาแบบสองทิศทางได้อีกด้วย

ประวัติ 
นิลส์ นิลสัน สร้างวิธีที่ใช้ฮิวริสติก มาเพิ่มความเร็วของขั้นตอนวิธีของไดค์สตราในปี ค.ศ. 1964 และเรียกขั้นตอนวิธีนี้ว่า A1 ต่อมาในปี ค.ศ. 1967 เบิร์ดแรม เรมเซสปรับปรุงขั้นตอนวิธีตัวนี้เพิ่มเติม แต่ไม่สามารถพิสูจน์ถึงความเร็วที่เพิ่มนี้ได้ เขาเรียกขั้นตอนวิธีนี้ว่า A2 ในปี ค.ศ. 1968 ปีเตอร์ อี ฮาร์ทแสดงการพิสูจน์ว่า A2 เป็นขั้นตอนวิธีที่เร็วขึ้นได้ และการพิสูจน์ของเขาได้แสดงอีกด้วยว่าขั้นตอนวิธี A2 เป็นขั้นตอนวิธีที่ดีที่สุดในเงื่อนไขที่กำหนด เขาจึงใส่คลีนสตาร์ (*) หลังตัว A เพื่อตั้งชื่ออัลกอรึทึมตัวนี้ซึ่งหมายถึง A และทุกรูปแบบของ A

หลักการ 
หลักการทำงานของเอสตาร์คือ เมื่อเอสตาร์ท่องไปในกราฟ เอสตาร์จะเลือกเส้นทางที่มีค่าน้อยที่สุดที่มันทราบ โดยคงแถวคอยลำดับความสำคัญของเส้นทางอื่นๆ ระหว่างนั้นที่เรียบเรียงไว้แล้ว ถ้าระหว่างที่เอสตาร์ท่องไปแต่ละจุดแล้วเจอเส้นทางที่มีค่ามากกว่าเส้นทางอื่น ขั้นตอนวิธีนี้จะไม่พิจารณาเส้นทางที่มีค่ามากกว่า แต่จะไปเลือกเส้นทางที่มีค่าน้อยกว่าแทน กระบวนการนี้จะทำต่อไปเรื่อย ๆ จนกระทั่งถึงจุดหมาย

กระบวนการ 

เช่นเดียวกับขั้นตอนวิธีการหาแบบมีข้อมูลประเภทอื่น ๆ เอสตาร์จะเริ่มจากหาเส้นทางที่น่าจะไปถึงจุดหมายมากที่สุดก่อน นอกจากเซตเอสตาร์จะเป็นส่วนนึงของขั้นตอนวิธีแบบละโมบเชิงการค้นหาแนวกว้างแล้ว เซตเอสตาร์ยังจะเก็บค่าระยะทางที่ไปมาแล้ว โดย  จะเป็นส่วนของฮิวริสติกที่เก็บค่าระยะทางจากจุดเริ่มต้น ไม่ใช่ค่าระยะทางจากโหนดที่ผ่านมาเท่านั้น

การทำงานของเอสตาร์จะเริ่มจากโหนดแรกสุด จากนั้นจะนำโหนดที่อยู่ในเซตเปิดที่ต้องท่องไปเข้าสู่แถวคอยลำดับความสำคัญ แถวคอยลำดับความสำคัญที่ใช้จะจัดอันดับความสำคัญให้โหนด  ที่มีค่า  น้อยสุดมีความสำคัญมากกว่า ในแต่ละขั้นตอนของอัลกอรึทึมจะทำการดึงโหนด  ที่มีค่า  ต่ำที่สุด และปรับค่า  และ  ของโหนดที่อยู่ติดกัน แล้วนำโหนดที่อยู่ติดกับโหนด  นี้ใส่ในแถวคอย จากนั้นอัลกอรึทึมก็ทำกระบวนการนี้ต่อไปจนกระทั่งโหนดเป้าหมายมีค่า  น้อยกว่าโหนดทุกโหนดในแถวคอย หรือหยุดเมื่อแถวคอยไม่มีข้อมูลอยู่แล้ว ซึ่งกระบวนการนี้อาจจะมีการพิจารณาโหนดเป้าหมายหลายครั้ง เช่น หากมีโหนดที่มีค่า f ต่ำกว่าโหนดที่ถูกดึงไปแล้ว เพื่อให้แน่ใจว่าเส้นทางที่เลือกจะเป็นเส้นทางที่สั้นที่สุด ค่าระยะทางที่สั้นที่สุดคือค่า  ของจุดเป้าหมายโดย  ของจุดเป้าหมายจะเป็นศูนย์ในฮิวริสติกที่ยอมรับได้ ถ้าต้องการหาจุดทั้งหมดที่ทำให้ได้ค่าเส้นทางที่สั้นที่สุดอัลกอรึทึมตัวนี้อาจจะเพิ่มให้โหนดจำโหนดก่อนหน้านี้ถัดขึ้นไป 1 โหนดของเส้นทางที่ดีที่สุดเท่าที่พบ และข้อมูลนี้ก็จะช่วยในการสร้างเส้นทางได้โดยการกระทำย้อนกลับจากจุดเป้าหมายไปยังจุดเริ่มต้น นอกจากนี้หากฮิวริสติกมีลักษณะโมโนโทน หรือเสถียร อาจใช้เซตปิดของโหนดที่ท่องไปแล้วเพื่อให้การค้นหามีประสิทธิภาพมากขึ้นก็ได้

รหัสเทียม 
อัลกอรึทึมสามารถแสดงด้วยรหัสเทียมได้ดังนี้
 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) เป็นเส้นตรงที่ระบุระยะทางไปยังจุดเป้าหมาย
ตัวอย่างนี้ใช้ สีเขียวคือจุดเริ่มต้น สีฟ้าคือจุดเป้าหมาย สีส้มคือจุดที่ผ่านแล้ว และใช้สัญลักษณ์ ",” แสดงจุดทศนิยม

คุณสมบัติ 
เช่นเดียวกับการค้นหาตามแนวกว้างก่อน เอสตาร์จะมีจุดสิ้นสุดและได้คำตอบเสมอ ถ้ามีคำตอบที่เป็นไปได้นั้น
ในกรณีที่ฟังก์ชันฮิวริสติก  เป็นฮิวริสติกยอมรับได้ ซึ่งจะไม่ประมาณค่าเกินไปกว่าค่าคำตอบที่ต่ำที่สุดจริงๆ ของเป้าหมาย เอสตาร์จะยอมรับได้เมื่อไม่ได้ใช้เซตปิด หรือถ้ามีการใช้เซตปิด คำตอบของ  จะต้องเป็นแบบโมโนโทนิกจึงจะทำให้เอสตาร์จะเป็นคำตอบที่ยอมรับได้ ซึ่งการเป็นโมโนโทนิกนั้นหมายความว่าทุกๆ เส้นของโหนด  และ  ที่อยู่ติดกัน และ  หมายถึงความยาวของเส้นระหว่างโหนดทั้งสอง เราจะได้ว่า

ทำให้สามารถพิสูจน์ได้ว่าทุกเส้นทาง  จากโหนดเริ่มต้นไปยังโหนด  เป็น

โดยที่  แสดงถึงความยาวของเส้นทาง และ แสดงเส้นทางที่เกิดจากเส้นทาง  รวมกับเส้นทางไปยัง  ซึ่งจะไม่สามารถลดค่าของระยะทางสะสมได้โดยใส่โหนดที่อยู่ติดกันในเส้นทางนั้น ๆ (มีลักษณะคล้ายกับขั้นตอนวิธีของเดกสตาร์ที่มีข้อจำกัดว่าไม่สามารถจัดการกับเส้นที่ติดลบได้) รูปแบบโมโนโทนิกอาจถือได้ว่าเป็นรูปแบบที่ยอมรับได้เมื่อค่าประมาณฮิวริสติกที่ทุก ๆ โหนดเป้าหมายนั้นเองมีค่าเป็นศูนย์ ซึ่งแสดงได้โดยอสมการต่อไปนี้ เมื่อกำหนดให้  เป็นเส้นทางที่สั้นที่สุดจากจุด  ใด ๆ ไปยังจุดหมาย 

เอสตาร์จะมีประสิทธิภาพที่เหมาะสมสำหรับฮิวริสติก  ใดๆ ดังนั้นจะไม่มีขั้นตอนวิธีใดที่ใช้ฮิวริสติกแบบเดียวกันแล้วใช้จำนวนโหนดในการพิจารณาน้อยกว่าเอสตาร์ ยกเว้นในกรณีที่มีหลายคำตอบซึ่ง  จะประมาณค่าของเส้นทางที่ดีที่สุด ซึ่งแม้จะมีกรณีดังกล่าวเกิดขึ้นในแต่ละกราฟ ก็อาจมีลำดับของตัวเลือกในแถวคอยบุพริมภาพที่เอสตาร์จะนำมาใช้เพื่อพิจารณาโหนดจำนวนน้อยที่สุดที่เป็นไปได้

กรณีพิเศษ 
เราสามารถมองขั้นตอนวิธีของเดกสตาร์ ซึ่งเป็นตัวอย่างหนึ่งของขั้นตอนวิธีค้นหาระยะทางแบบเอกรูป เป็นกรณีพิเศษของเอสตาร์โดยที่  สำหรับทุก ๆ ค่า  การค้นตามแนวกว้างก็สามารถประยุกต์จากเอสตาร์ได้เช่นกันโดยสร้างตัวนับ “C” ให้มีค่าเริ่มต้นที่ใหญ่มากๆ เมื่อทำการพิจารณาโหนดใดแล้วเราจะใส่ “C” ไปยังทุกโหนดที่อยู่ติดกัน ระหว่างที่กำลังใส่ “C” ให้กับโหนดจะต้องลดค่า “C” ทีละหนึ่งด้วย วิธีนี้ถ้ายิ่งหาโหนดพบเร็วเท่าใด ค่าของ  ก็จะยิ่งสูงขึ้นเท่านั้น อย่างไรก็ดีถ้าต้องการเพิ่มประสิทธิภาพของขั้นตอนวิธีของเดสสตาร์และการค้นตามแนวกว้าง ก็สามารถทำได้โดยไม่ใส่ค่า  ในแต่ละโหนด

การนำไปปรับใช้ 
การปรับขั้นตอนวิธีเอสตาร์อย่างง่ายในเชิงรายละเอียดบางประการ ส่งผลต่อความสามารถในการนำไปปรับใช้ของเอสตาร์อย่างมีนัยสำคัญได้ เช่นวิธีที่แถวคอยความสำคัญจัดการกับปมนั้น อาจมีผลกระทบต่อประสิทธิภาพอย่างมีนัยสำคัญได้ในบางกรณี หากไม่มีปม และความสำคัญเป็นไปตามรูปแบบเข้าทีหลังออกก่อน เอสตาร์จะมีลักษณะเหมือนการค้นหาแนวกว้างในระยะทางที่เท่ากัน

เมื่อจำเป็นจะต้องมีเส้นทางหลังเสร็จสิ้นการค้นหา โดยปกติแล้วจะมีการคงอ้างอิงระหว่างโหนดก่อนหน้ากับโหนดปัจจุบันไว้เพื่อใช้หาเส้นทางที่เหมาะสม ซึ่งการคงอ้างอิงไว้อาจมีความสำคัญในเชิงโหนดเดียวกันจะไม่ปรากฏในแถวคอยความสำคัญเกินหนึ่งครั้ง (กล่าวคือ แต่ละจุดรับเข้าจะสอดคล้องกับเส้นทางที่ไม่เหมือนกันและมีค่าไม่เท่ากัน) แนวปฏิบัติทั่วไปเมื่อมีกรณีดังกล่าวคือการตรวจสอบว่าโหนดที่จะถูกเพิ่มเข้าไปอยู่ในแถวคอยความสำคัญแล้วหรือไม่ ถ้ามีแล้วความสำคัญและจุดเชื่อมของโหนดแม่จะเปลี่ยนไปเชื่อมกับเส้นทางที่มีค่าน้อยกว่า ในการใช้วิธีตรวจสอบโหนดลูกที่จะเก็บค่าน้อยกว่าโหนดแม่นี้จะใช้เวลา  หน่วย การแต่งเติมโหนดลูกโดยใช้ตารางแฮชอาจช่วยลดเวลาจากที่เป็นฟังก์ชันเป็นเวลาที่แน่นอนจำนวนหนึ่งได้

การยอมรับได้และความเหมาะสม 
เอสตาร์เป็นขั้นตอนวิธีที่ยอมรับได้และถือว่าใช้จำนวนโหนดน้อยกว่าการค้นหาที่ใช้ฮิวริสติกเดียวกันที่ยอมรับได้อื่น ๆ เนื่องจากเอสตาร์ใช้ค่าประมาณที่เหมาะสมของค่าระยะทางผ่านทุกโหนดที่เอสตาร์ถือว่ายอมรับได้ ทำให้ค่าระยะทางที่ผ่านโหนดดังกล่าวไปถึงโหนดเป้าหมายจะมีค่าน้อยกว่าหรือเท่ากับค่าที่ประมาณไว้ แต่ต้องเป็นเท่าที่เอสตาร์รู้ว่าค่าประมาณที่เหมาะสมนั้นมีอยู่และหาค่าได้เท่านั้น ซึ่งสามารถพิสูจน์ได้ดังนี้

"เมื่อเอสตาร์ยุติการค้นหา เอสตาร์จะพบเส้นทางที่มีค่าระยะทางจริงน้อยกว่าค่าระยะทางที่ประมาณไว้และผ่านโหนดเปิดใด ๆ แต่เนื่องจากค่าประมาณนี้เหมาะสมแล้ว เอสตาร์จึงจะไม่สนใจโหนดเปิดอีกต่อไป หรือก็คือเอสตาร์จะไม่ค้นหาความเป็นไปได้ที่จะมีระยะทางที่จะมีค่าต่ำกว่านี้ และถือว่าค่านี้ยอมรับได้แล้ว กรณีต่อไปนี้สมมุติว่าขั้นตอนวิธี B ยุติการค้นหาโดยค่าระยะทางจริงมีค่าไม่น้อยกว่าค่าที่ประมาณไว้ของเส้นทางที่ผ่านโหนดเปิดบางโหนด ขั้นตอนวิธี B ก็จะพิจารณาความเป็นไปได้ที่มีโหนดที่มีค่าต่ำกว่าโดยใช้ข้อมูลฮิวริสติกที่มันมี ซึ่งก็คือแม้ B จะถือได้ว่ามีจำนวนโหนดน้อยกว่าเอสตาร์แต่ก็ไม่อาจยอมรับได้ ซึ่งจะได้ว่าเอสตาร์มีจำนวนโหนดน้อยที่สุดในบรรดาขั้นตอนวิธีค้นหาที่ยอมรับได้"

ซึ่งข้อพิสูจน์ดังกล่าวจะเป็นจริงก็ต่อเมื่อเอสตาร์สอดคล้องกับเงื่อนไขต่อไปนี้
 เอสตาร์ใช้ฮิวริสติกที่ยอมรับได้ ไม่เช่นนั้นจะไม่สามารถรับประกันได้ว่าเอสตาร์จะค้นหาโดยใช้จำนวนโหนดน้อยกว่าขั้นตอนวิธีที่มีฮิวริสติกเดียวกัน
 เอสตาร์แก้ปัญหาการค้นหาเพียงปัญหาเดียว ไม่ได้ใช้แก้ปัญหาการค้นหาที่คล้าย ๆ กันหลายปัญหา ไม่เช่นนั้นจะไม่สามารถรับประกันได้ว่าเอสตาร์จะค้นหาโดยใช้จำนวนโหนดน้อยกว่าขั้นตอนวิธีที่มีฮิวริสติกที่มีส่วนเพิ่มขึ้นมา

ความซับซ้อนของขั้นตอนวิธี 
ความซับซ้อนของขั้นตอนวิธีเอสตาร์จะขึ้นอยู่กับฮิวริสติก ในกรณีที่แย่ที่สุดคือจำนวนโหนดที่เพิ่มขึ้นเป็นฟังก์ชันเลขชี้กำลังของความยาวที่สั้นที่สุด และจะเป็นฟังก์ชันพหุนามเมื่อกราฟที่ต้องการหาเส้นทางที่สั้นที่สุดซึ่งมีสภาพที่เป็นเป้าหมายอย่างเดียว ดังนั้นฟังก์ชันฮิวริกติกจะสอดคล้องกับสมการดังนี้

 คือฮิวริสติกที่เป็นคำตอบซึ่งเป็นค่าจาก  ไปถึงเป้าหมาย และค่าความผิดพลาดของ h จะโตช้ากว่าหรือเท่ากับค่าลอการิทึมของ ฮิวริสติกที่สมบูรณ์  ที่ซึ่ง  จะเป็นค่าความยาวของ  ถึงเป้าหมาย
เปรียบเทียบระหว่าง ขั้นตอนวิธีของเดสตาร์กับขั้นตอนวิธีเอสตาร์

การนำไปใช้ 
ในการพัฒนาเกมคอมพิวเตอร์ ได้ใช้เอสตาร์เป็นขั้นตอนวิธีในการหาเส้นทางการเคลื่อนที่ในพื้นที่ที่กำหนดที่ดีที่สุดของตัวละครในเกม ในพื้นที่นั้นอาจจะมีสิ่งกีดขวางหรือเป็นพื้นที่โล่ง นอกจากนี้ยังมีการนำเอสตาร์ไปใช้พัฒนาปัญญาประดิษฐ์อีกด้วย

ดูเพิ่ม 
สาเหตุที่เอสตาร์ได้รับความนิยมมากกว่าขั้นตอนวิธีของเดสสตาร์เพราะ ขั้นตอนวิธีเอสตาร์ใช้ความจำน้อยกว่าและทำงานเร็วกว่า แต่ถ้าฟังก์ชันการประมาณค่าฮิวริสติสไม่ดีพอ ประสิทธิภาพของขั้นตอนวิธีเอสตาร์จะได้พอๆกับการใช้การค้นหาตามแนวกว้างทั่วไป ในการพัฒนาเกมคอมพิวเตอร์ มีการใช้การค้นหาเส้นทางด้วยขั้นตอนวิธีเอสตาร์มากที่สุด(ทั้งแบบดั้งเดิมและแบบดัดแปลง) สาเหตุที่ต้องดัดแปลงขั้นตอนวิธีเอสตาร์เพราะถ้าพื้นที่การค้นหามีขนาดใหญ่มากๆ เอสตาร์อาจจะทำให้เกมค้างได้

ดูเพิ่ม 
 Breadth-first search
 Depth-first search
 Any-angle path planning

อ้างอิง

แหล่งข้อมูลอื่น 
 อธิบายขั้นตอนวิธีเอสตาร์แบบง่าย 
 อธิบายขั้นตอนวิธีเอสตาร์เขียนด้วยภาษาจาวา
 อธิบายขั้นตอนวิธีเอสตาร์เขียนด้วยภาษาซีพลัสพลัส และ สอนขั้นตอนวิธีแบบเอสตาร์ 
ขั้นตอนวิธี
ขั้นตอนวิธีการค้นหา