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

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

นิยาม แก้

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

ค่าระยะทางทางจากโหนดเริ่มต้นมายังโหนดปัจจุบัน (ใช้สัญลักษณ์ $g(x)$ )
ค่าประมาณฮิวริสติกที่ยอมรับได้ ของระยะทางที่จะถึงจุดหมาย(ใช้สัญลักษณ์ $h(x)$ )

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

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

ประวัติ แก้

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

หลักการ แก้

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

กระบวนการ แก้

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

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

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

คุณสมบัติ แก้

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

$h(x)\leq d(x,y)+h(y)$

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

$L(X)+h(x)\leq L(X)+d(x,y)+h(y)=L(Y)+h(y)$

โดยที่ $L(\cdot )$ แสดงถึงความยาวของเส้นทาง และ $Y$ แสดงเส้นทางที่เกิดจากเส้นทาง $X$ รวมกับเส้นทางไปยัง $y$ ซึ่งจะไม่สามารถลดค่าของระยะทางสะสมได้โดยใส่โหนดที่อยู่ติดกันในเส้นทางนั้น ๆ (มีลักษณะคล้ายกับขั้นตอนวิธีของเดกสตาร์ที่มีข้อจำกัดว่าไม่สามารถจัดการกับเส้นที่ติดลบได้) รูปแบบโมโนโทนิกอาจถือได้ว่าเป็นรูปแบบที่ยอมรับได้เมื่อค่าประมาณฮิวริสติกที่ทุก ๆ โหนดเป้าหมายนั้นเองมีค่าเป็นศูนย์ ซึ่งแสดงได้โดยอสมการต่อไปนี้ เมื่อกำหนดให้ $P=(f,v_{1},v_{2},\ldots ,v_{n},g)$ เป็นเส้นทางที่สั้นที่สุดจากจุด $f$ ใด ๆ ไปยังจุดหมาย $g$

$h(f)\leq d(f,v_{1})+h(v_{1})\leq d(f,v_{1})+d(v_{1},v_{2})+h(v_{2})\leq \ldots \leq L(P)+h(g)=L(P)$

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

กรณีพิเศษ แก้

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

การนำไปปรับใช้ แก้

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

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

การยอมรับได้และความเหมาะสม แก้

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

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

ซึ่งข้อพิสูจน์ดังกล่าวจะเป็นจริงก็ต่อเมื่อเอสตาร์สอดคล้องกับเงื่อนไขต่อไปนี้

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

ความซับซ้อนของขั้นตอนวิธี แก้

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

$|h(x)-h^{*}(x)|=O(\log h^{*}(x))$

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

ขั้นตอนวิธีของเดสตาร์ใช้การประมาณฮิวริสติกเป็น 0 หรืออาจกล่าวได้ว่าไม่มีการประมาณเลย	ขั้นตอนวิธีเอสตาร์มีการประมาณฮิวริสติก

การนำไปใช้ แก้

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

ดูเพิ่ม แก้

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

ดูเพิ่ม แก้

อ้างอิง แก้

↑ Hart, P. E.; Nilsson, N.J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics. 4 (2): 100–7. doi:10.1109/TSSC.1968.300136.
↑ eecs.berkeley.edu
↑ Dechter, Rina; Judea Pearl (1985). "Generalized best-first search strategies and the optimality of A*". Journal of the ACM. 32 (3): 505–536. doi:10.1145/3828.3830. S2CID 2092415.
↑ Koenig, Sven; Maxim Likhachev; Yaxin Liu; David Furcy (2004). "Incremental heuristic search in AI". AI Magazine. 25 (2): 99–112.
↑ Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. ISBN 978-0-201-05594-8.
↑ Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. pp. 97–104. ISBN 0-13-790395-2.
↑ Buckland, Mat (2004). Programming Game AI by Example. Jones & Bartlett Publishers. pp. 241–247. ISBN 1556220782.
↑ XiaoLi Guo; Ping Guo. (2009). "A* Algorithm Analysis and Optimization in Network Game Design".

แหล่งข้อมูลอื่น แก้

[nilsson-1] Hart, P. E.; Nilsson, N.J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics. 4 (2): 100–7. doi:10.1109/TSSC.1968.300136.

[2] s.berkeley.edu

[:1-3] Dechter, Rina; Judea Pearl (1985). "Generalized best-first search strategies and the optimality of A*". Journal of the ACM. 32 (3): 505–536. doi:10.1145/3828.3830. S2CID 2092415.

[4] Koenig, Sven; Maxim Likhachev; Yaxin Liu; David Furcy (2004). "Incremental heuristic search in AI". AI Magazine. 25 (2): 99–112.

[pearl84-5] Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. ISBN 978-0-201-05594-8.

[6] Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. pp. 97–104. ISBN 0-13-790395-2.

[7] Buckland, Mat (2004). Programming Game AI by Example. Jones & Bartlett Publishers. pp. 241–247. ISBN 1556220782.

[8] XiaoLi Guo; Ping Guo. (2009). "A* Algorithm Analysis and Optimization in Network Game Design".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]