คำนำ
อัลกอริทึมการค้นหา* เป็นที่รู้จักกันทั่วไปว่าเป็นอัลกอริทึม A-Star นี่คืออัลกอริทึมที่มีหลายโหนดบนระนาบกราฟเพื่อค้นหาต้นทุนต่ำสุดของการผ่าน ใช้กันทั่วไปในเกม
เขาวงกตที่สร้างขึ้นผ่านอาร์เรย์สองมิติ "%" หมายถึงผนัง A คือจุดเริ่มต้น B คือจุดสิ้นสุด "#" หมายถึงอุปสรรคและ "*" หมายถึงเส้นทางที่คำนวณโดยอัลกอริทึม
โครงสร้างรหัสของบทความนี้:
% % % % % % % % % % % oooo % oo # oo % % a o # o b % % oo # oo % % oooo % % % % % % % % % % % % % % - oo * oo % % o * # * o % % a o # o b % % oo # oo % % oo % % % % % % % % % % <
ทฤษฎีอัลกอริทึม
สูตรหลักของอัลกอริทึมคือ: f = g+h
นึกถึงโหนดบนแผนที่เป็นกริด
G = การใช้การเคลื่อนไหวของการย้ายไปยังโหนดที่ระบุบนกริดจากจุดเริ่มต้น A ตามเส้นทางที่สร้างขึ้น ในตัวอย่างนี้เราทำให้การเคลื่อนไหวในแนวนอนหรือแนวตั้งมีค่าใช้จ่าย 10 และทิศทางแนวทแยงมุม 14 เราใช้ค่าเหล่านี้เพราะเราอยู่ตามแนวทแยงมุม
ระยะทางคือรูทหมายเลข 2 หรือประมาณ 1.414 เท่าของจำนวนเงินที่ใช้ในการเคลื่อนย้ายในแนวนอนหรือแนวตั้ง เพื่อความเรียบง่ายเราประมาณโดยใช้ 10 และ 14
เนื่องจากเรากำลังคำนวณค่า G ที่นำไปสู่สี่เหลี่ยมตามเส้นทางที่เฉพาะเจาะจงวิธีการประเมินคือการใช้ค่า G ของโหนดพาเรนต์ของมันจากนั้นเพิ่ม 14 และ 10 ตามลำดับตามทิศทางในแนวทแยงหรือมุมขวา ในตัวอย่างนี้
ความต้องการแต่ละวิธีมีมากขึ้นเนื่องจากเราได้รับมากกว่าหนึ่งตารางจากภายนอกกริดเริ่มต้น
H = การบริโภคการเคลื่อนไหวโดยประมาณจากตารางปัจจุบันถึงจุดสิ้นสุด B ทำไมจึงเรียกว่า "การประมาณ" เพราะเราไม่มีทางรู้ถึงความยาวของเส้นทางล่วงหน้า ที่นี่เราใช้วิธีแมนฮัตตันซึ่งคำนวณแนวนอนและแนวตั้งจากกริดปัจจุบันไปยังกริดปลายทาง
ผลรวมของจำนวนกำลังสองของสี่เหลี่ยมโดยไม่สนใจทิศทางในแนวทแยง จากนั้นคูณผลลัพธ์ด้วย 10
ค่าของ F คือผลรวมของ G และ H ซึ่งเป็นมาตรฐานที่เราใช้ในการตัดสินเส้นทางลำดับความสำคัญ กริดที่มีค่าที่เล็กที่สุดของ F ถือเป็นโหนดเส้นทางลำดับความสำคัญ
ขั้นตอนการดำเนินการ
อัลกอริทึมถูกเขียนใน Java ก่อนดูเนื้อหาของคลาสโหนด
แพ็คเกจ A_STAR_SEARCH; / ** * คลาสโหนด * @author zx * */ โหนดคลาสสาธารณะ {private int x; // x ประสานงานส่วนตัว int y; // y พิกัดค่าสตริงส่วนตัว; // ค่าของโหนด private สอง fvalue = 0; // f value ส่วนตัว double gvalue = 0; // g ค่า private สอง hvalue = 0; // h ค่าบูลีนส่วนตัวที่เข้าถึงได้; // มันสามารถเข้าถึงได้ (เป็นอุปสรรค) โหนดส่วนตัวโหนด pnode; // โหนดโหนด paren public node (int x, int y, ค่าสตริง, บูลีนที่สามารถเข้าถึงได้) {super (); this.x = x; this.y = y; this.value = ค่า; เข้าถึงได้ = เข้าถึงได้; } โหนดสาธารณะ () {super (); } สาธารณะ int getx () {return x; } โมฆะสาธารณะ setx (int x) {this.x = x; } สาธารณะ int getey () {return y; } โมฆะสาธารณะ sety (int y) {this.y = y; } สตริงสาธารณะ getValue () {ค่าคืน; } โมฆะสาธารณะ setValue (ค่าสตริง) {this.value = value; } สาธารณะ double getFvalue () {return fvalue; } โมฆะสาธารณะ setfvalue (double fvalue) {fvalue = fvalue; } สาธารณะ double getGvalue () {return gvalue; } โมฆะสาธารณะ setGvalue (double gvalue) {gvalue = gvalue; } สาธารณะ double gethvalue () {return hvalue; } โมฆะสาธารณะ sethvalue (double hvalue) {hvalue = hvalue; } บูลีนสาธารณะ isreachable () {return ecoable; } โมฆะสาธารณะ setReachable (บูลีนเข้าถึงได้) {เข้าถึงได้ = เข้าถึงได้; } โหนดสาธารณะ getPnode () {return pnode; } โมฆะสาธารณะ setpNode (โหนด pnode) {pnode = pnode; -ยังต้องการคลาสแผนที่ ในวิธีการก่อสร้างแผนที่ฉันใช้แผนที่เขาวงกตโดยการสร้างโหนดสองมิติซึ่งรวมถึงจุดเริ่มต้นและจุดสิ้นสุด
แพ็คเกจ A_STAR_SEARCH; แผนที่ระดับสาธารณะ {โหนดส่วนตัว [] [] แผนที่; // โหนดอาร์เรย์โหนดส่วนตัว startNode; // เริ่มโหนดส่วนตัว endnode; // จุดสิ้นสุดแผนที่สาธารณะ () {แผนที่ = โหนดใหม่ [7] [7]; สำหรับ (int i = 0; i <7; i ++) โหนด (i, j, "o", true);}} สำหรับ (int d = 0; d <7; d ++) {แผนที่ [0] [d] .setValue ("%"); แผนที่ [0] [d] SE); แผนที่ [6] [D] .SetValue ("%"); แผนที่ [D] [6] .SetValue ("%"); แผนที่ [D] [6] .SetReachable (เท็จ);} แผนที่ [3] [1] = แผนที่ [3] [1]; แผนที่ [3] [5] .SetValue ("B"); endNode = แผนที่ [3] [5]; สำหรับ (int k = 1; k <= 3; k ++) {แผนที่ [k+1] [3] .setValue ("#"); แผนที่ [k+1] [3] </span> // แสดงแผนที่โมฆะสาธารณะ showmap () {สำหรับ (int i = 0; i <7; i ++) {สำหรับ (int j = 0; j <7; j ++) {system.out.print (แผนที่ [i] [j] .getValue ()+"");} system.out.println ("" ") โมฆะ setMap (node [] [] แผนที่) {this.map = map;} โหนดสาธารณะ getStartNode () {return startNode;} โมฆะสาธารณะ setStartNode (โหนด startNode) {this.startNode = startNode; endnode;}}นี่คือคลาส Astar ที่สำคัญที่สุด
กระบวนการปฏิบัติการ
1 เริ่มต้นที่จุดเริ่มต้น A และบันทึกเป็นจุดที่ค้างอยู่ใน "รายการเปิด" ซึ่งเป็นรายการของสี่เหลี่ยมที่จะตรวจสอบ
2 ค้นหาสี่เหลี่ยมที่เข้าถึงได้หรือผ่านได้ทั้งหมดรอบจุดเริ่มต้นและข้ามสี่เหลี่ยมที่ไม่สามารถใช้ได้ เพิ่มลงในรายการเปิดเช่นกัน บันทึกจุด A สำหรับกริดเหล่านี้ทั้งหมดเป็น "กริดแม่" เมื่อเราต้องการอธิบายเส้นทาง
วัสดุมีความสำคัญมาก วัตถุประสงค์เฉพาะของมันจะถูกอธิบายในภายหลัง
3 ลบจุดเริ่มต้น A ออกจากรายการเปิดและเพิ่มลงใน "รายการปิด" เพื่อบันทึกสี่เหลี่ยมทั้งหมดที่ไม่จำเป็นต้องตรวจสอบอีกครั้ง
หลังจากขั้นตอนข้างต้น "รายการเปิด" มีโหนดทั้งหมดรอบ ๆ จุดเริ่มต้น A ยกเว้นอุปสรรค โหนดหลักของพวกเขาคือ A. ทั้งหมดผ่านสูตร F = G+H ที่กล่าวถึงก่อนหน้านี้พวกเขาคำนวณค่า G, H และ F ของแต่ละโหนดและตามค่าของ F พวกเขามีขนาดเล็ก
เรียงลำดับเป็นขนาดใหญ่ และดำเนินการต่อไปนี้บนโหนดด้วยค่า F ที่เล็กที่สุด
4. ลบออกจากรายการในและเพิ่มลงในรายการปิด
5. ตรวจสอบกริดที่อยู่ติดกันทั้งหมด ข้ามสิ่งที่ไม่ผ่าน (1. ใน "รายการปิด" และ 2. อุปสรรค) และเพิ่มลงในรายการที่เปิดหากพวกเขายังไม่ได้อยู่ในนั้น ใช้สแควร์ที่เลือกเป็นโหนดหลักของจัตุรัสใหม่
6. หากกริดที่อยู่ติดกันอยู่ในรายการเปิดให้ตรวจสอบว่าเส้นทางปัจจุบันดีกว่าหรือไม่ กล่าวอีกนัยหนึ่งตรวจสอบว่าค่า G จะต่ำกว่านี้หรือไม่หากเราไปถึงเส้นทางใหม่ ถ้าไม่เช่นนั้นไม่มีอะไร
ทำ. (ที่นี่ไม่มีการตัดสินในรหัสของฉัน)
7. เราทำซ้ำขั้นตอนนี้จนกว่ากริดเป้าหมาย (จุดสิ้นสุด "B") จะถูกเพิ่มลงใน "รายการเปิด" ซึ่งระบุว่าจุดสิ้นสุด B อยู่รอบ ๆ โหนดก่อนหน้านี้เพิ่มใน "รายการปิด" คุณจะต้องก้าวไปหนึ่งขั้นเพื่อถึงจุดสิ้นสุด B.
8. เราเพิ่มจุดสิ้นสุด B ใน "รายการปิด"
9. ในขั้นตอนสุดท้ายเราต้องแสดงเส้นทางจากจุดเริ่มต้น A ถึงจุดสิ้นสุด B บทบาทของโหนดพาเรนต์จะปรากฏขึ้น โดยการเปลี่ยนค่าของโหนดพาเรนต์ของโหนดจุดสิ้นสุดใน "ปิดรายการ" คุณสามารถแสดงเส้นทางได้โดยทำตามเบาะแส
ตรวจสอบรหัส
แพ็คเกจ A_STAR_SEARCH; นำเข้า Java.util.ArrayList; คลาสสาธารณะ ASTAR {/*** ใช้ ArrayList Array เป็น "Open List" และ "ปิดรายการ"*/ArrayList <Node> Open = New ArrayList <Node> (); endnode: จุดสิ้นสุด* @return*/public double gethValue (โหนด currentNode, โหนด endnode) {return (math.abs (currentNode.getx () - endnode.getx ()) + math.abs (currentNode.gety () - endnode.gety ())* 10; getGvalue (โหนด currentNode) {ถ้า (currentNode.getPnode ()! = null) {ถ้า (currentNode.getx () == currentNode.getPnode (). getx () || currentNode.gety () == currentNode.getPnode () currentNode.getGValue ()+10;} ส่งคืน currentNode.getGValue ()+14;} ส่งคืน currentNode.getGValue ();}/** * รับค่า f: g+h * @param currentNode * @return */public double getFvalue (Node CurrentNode) currentNode.getGvalue ()+currentNode.getHValue ();}/** * เพิ่มโหนดรอบ ๆ โหนดที่เลือกไปยัง "รายการเปิด" * @param Node * @param map */โมฆะสาธารณะ inopen (node node, map) {int x = node.getx (); j = 0; j <3; j ++) {// เงื่อนไขการตัดสินคือ: โหนดสามารถเข้าถึงได้ (นั่นคือไม่ใช่อุปสรรคไม่ใช่ในรายการปิด) รายการเปิดไม่รวมและไม่ได้เลือก if (map.getMap () [x-1+i] [y-1+j] .IsReachable () &&! open.contains (map.getMap () [x-1+i] [y-1+j]) & &! (x == (x-1+i) && y == (y-1+j))) {map.getMap () [x-1+i] [y-1+j] .setPnode (map.getMap () [x] [y]); โหนดที่เลือกใช้เป็นแผนที่โหนดพาเรนต์ getMap () [x-1+i] [y-1 +j] .setGvalue (getGvalue (map.getMap () [x-1+i] [y-1+j])); map.getMap () [x-1+i] [y-1+j] .sethvalue (gethvalue (map.getMap () tendnode ())); map.getMap () [x-1+i] [y-1+j] .setfvalue (getfvalue (map.getMap () [x-1+i] [y-1+j])); open.add (map.getMap () [x-1+i] [y-1+j]) * เรียงลำดับโหนดในรายการเปิดจากขนาดเล็กถึงใหญ่โดยค่า f * @param arr */การเรียงลำดับโมฆะสาธารณะ (arraylist <node> arr) {สำหรับ (int i = 0; i <arr.size ()-1; i ++) {สำหรับ (int j = i+1; j <arr.size (); j ++) arr.get (j) .getFvalue ()) {node tmp = new node (); tmp = arr.get (i); arr.set (i, arr.get (j)); arr.set (j, tmp);}}}}}} เปิด) {if (open.contains (node)) {node.setReachable (false); // ตั้งค่า unreachable open.remove (node); close.add (โหนด);}} การค้นหาโมฆะสาธารณะ (แผนที่) {// ใช้โหนดรอบจุดเริ่มต้นนั่นคือ inopen (map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()], แผนที่); close.add (map.getMap () [map.getStart node (). getx ()] [map.getStartNode (). getx ()] [map.getStartNode (). gety ()]); map.getMap () [map.getStartNode (). getx ()] [map.g etStartNode (). gety ()]. setReachable (false); map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()]. setpNode (map.getMap () ทำ {inopen (open.get (0), แผนที่); inclose (open.get (0), เปิด); เรียงลำดับ (เปิด);} ในขณะที่ (! open.contains (map.getMap () [map.get.getEndNode (). getx ()] [map.getEndNode () inclose (map.getMap () [map.getEndNode (). getx ()] [map.getEndNode (). gety ()], เปิด); showpath (ปิด, แผนที่);}/** * ทำเครื่องหมายเส้นทาง * @param arr * @param map */public void phowpath Node (); // <span style = "space สีขาว: pre"> </span> node = map.getMap () [map.getEndNode (). getx ()] [map.getEndNode (). gety (); == map.getStartNode (). getx () && node.gety () == map.getStartNode (). gety ())) {// <span style = "space สีขาว: pre"> </span> node.getPnode (). setValue ("*"); // <span style = "White-space: pre"> </span>}} // <span style = "space สีขาว: pre"> </span> map.getMap () [map.getStartNode (). getx ()] [map.getStartNode () gety ()ในที่สุดก็เขียนวิธีหลัก
แพ็คเกจ A_STAR_SEARCH; การบำรุงรักษาระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {แผนที่แผนที่ = แผนที่ใหม่ (); ASTAR ASTAR = ใหม่ ASTAR (); map.showmap (); ASTAR.Search (แผนที่); System.out.println ("================================================================================================================= - - - map.showmap ();}}ปรับเปลี่ยนแผนที่และทดสอบเพื่อดูเอฟเฟกต์
% % % % % % % % % % % oooo % oo # oo % % a o # o b % % oo # oo % % oooo % % % % % % % % % % % % % % % % ======================================================================================= % % % oo # a # a # a -
สรุป
เพื่อให้แน่ใจว่าเส้นทางที่สั้นที่สุด (โซลูชันที่ดีที่สุด) พบคีย์อยู่ในการเลือกฟังก์ชั่นการประมาณค่า H (N): ค่าระยะทางที่แท้จริงของค่าการประมาณค่า H (N) <= N ถึงโหนดเป้าหมาย ในกรณีนี้มีการค้นหาหลายจุดช่วงการค้นหามีขนาดใหญ่และประสิทธิภาพต่ำ แต่สามารถรับได้
ทางออกที่ดีที่สุด หากค่าโดยประมาณ> ค่าจริงจำนวนการค้นหาของคะแนนมีขนาดเล็กช่วงการค้นหามีขนาดเล็กและประสิทธิภาพสูง แต่ไม่สามารถรับประกันได้ว่าจะได้รับการแก้ปัญหาที่ดีที่สุด
ความรู้สึกที่ยิ่งใหญ่ที่สุดคือ: สิ่งต้องห้ามที่สุดเกี่ยวกับการตกปลาเป็นเวลาสามวันและสองวันของการทำให้ตาข่ายแห้ง จำนวนเงินอาจไม่ใหญ่ แต่ต้องมีความต่อเนื่องและกุญแจคือการคงอยู่
ฉันหวังว่าโปรแกรมเมอร์ทุกคนสามารถพิมพ์รหัสอย่างมีความสุขและทำสิ่งที่เขาชอบทำ
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการเขียนโปรแกรม Java และการใช้รหัสที่สมบูรณ์ของอัลกอริทึม A* ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น