مقدمة
تُعرف خوارزمية البحث A* باسم خوارزمية A-Star. هذه خوارزمية تحتوي على عقد متعددة على مستوى الرسم البياني للعثور على أدنى تكلفة للمرور. شائع الاستخدام في الألعاب
تمثل متاهة تم إنشاؤها من خلال صفيف ثنائي الأبعاد ، "٪" الجدار ، A هي نقطة البداية ، B هي نقطة النهاية ، "#" تمثل العقبة ، ويمثل "*" المسار المحسوب بواسطة الخوارزمية
هيكل رمز هذه المقالة:
٪ ٪ ٪ ٪ ٪ ٪ ٪ ٪ oooo ٪ oo ===================================================================================================سف oo * oo ٪ ٪ O * # * O ٪ A O # O B ٪ OO # 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 * */ Class Public Class {private int x ؛ // x إحداثيات خاصة int y ؛ // y ينسق قيمة السلسلة الخاصة ؛ // قيمة العقدة الخاصة fvalue المزدوجة = 0 ؛ // f value private double gvalue = 0 ؛ // G Value Private Double Hvalue = 0 ؛ // H VALUES Private Boolean يمكن الوصول إليها ؛ // هل يمكن الوصول إليه (هل هو عقبة) عقدة خاصة pnode ؛ // node node public node (int x ، int y ، string string ، boolean actible) {super () ؛ this.x = x ؛ this.y = y ؛ this.value = القيمة ؛ يمكن الوصول إليه = يمكن الوصول إليه ؛ } العقدة العامة () {super () ؛ } public int getx () {return x ؛ } public void setx (int x) {this.x = x ؛ } public int gety () {return y ؛ } public void sety (int y) {this.y = y ؛ } السلسلة العامة getValue () {return value ؛ } public void setValue (قيمة السلسلة) {this.value = value ؛ } public double getFvalue () {return fvalue ؛ } public void setfvalue (double fvalue) {fvalue = fvalue ؛ } public double getGvalue () {return gvalue ؛ } public void setgvalue (double gvalue) {gvalue = gvalue ؛ } gethvalue المزدوج العام () {return hvalue ؛ } public void sethvalue (hvalue double) {hvalue = hvalue ؛ } boolean public isReachable () {return actible ؛ } public void setReachable (منطقي يمكن الوصول إليه) {actable = يمكن الوصول إليه ؛ } العقدة العامة getPnode () {return pnode ؛ } public void setPnode (node pnode) {pnode = pnode ؛ }}تحتاج أيضا إلى فئة الخريطة. في طريقة بناء الخريطة ، أقوم بتطبيق خريطة متاهة من خلال إنشاء مجموعة ثنائية الأبعاد من العقد ، والتي تتضمن نقاط البداية والنهاية.
حزمة A_STAR_Search ؛ خريطة الفئة العامة {node private [] [] [] map ؛ // node array startNode ؛ Node (i ، j ، "o" ، true) ؛}} لـ (int d = 0 ؛ d <7 ؛ d ++) {map [0] [d] .SetValue ("٪") ؛ map [0] SE) ؛ MAP [6] = MAP [3] [1] ؛ MAP [3] [5] .SetValue ("B") ؛ endnode = map [3] [5] ؛ for (int k = 1 ؛ k <= 3 ؛ k ++) {map [k+1] [3]. MAP Public void showmap () {for (int i = 0 ؛ i <7 ؛ i ++) {for (int j = 0 ؛ j <7 ؛ j ++) {system.out.print (map [i] setMap (node [] [] map) {this.map = map ؛} node public getStartNode () {return startNode ؛} public void setStartNode (node startNode) {this.startnode = startNode ؛} public node getendnode () {return endnode ؛ endnode ؛}}فيما يلي أهم فصول أستار
عملية التشغيل
1 ابدأ عند نقطة البداية A وحفظها كنقطة معلقة في "القائمة المفتوحة" ، وهي قائمة من المربعات التي سيتم فحصها.
2 ابحث عن جميع المربعات التي يمكن الوصول إليها أو قابلة للمرور حول نقطة البداية وتخطي المربعات غير القابلة للتطبيق. إضافتها إلى قائمة الافتتاح كذلك. حفظ النقطة أ لجميع هذه الشبكات مثل "الشبكة الأصل". عندما نريد وصف المسار ، المربع الأصل
المواد مهمة جدا. سيتم شرح هدفه المحدد لاحقًا.
3 قم بحذف نقطة البداية A من القائمة المفتوحة وأضفها إلى "قائمة إغلاق" لحفظ جميع المربعات التي لا تحتاج إلى التحقق مرة أخرى.
بعد الخطوات المذكورة أعلاه ، تحتوي "القائمة المفتوحة" على جميع العقد حول نقطة البداية A باستثناء العقبات. العقد الأصل هي كلها A. من خلال الصيغة f = g+h المذكورة سابقًا ، فإنها تحسب القيم G و H و F لكل عقدة ، ووفقًا لقيمة F ، فهي صغيرة
الفرز إلى كبيرة. وقم بالعمليات التالية على العقدة مع أصغر قيمة f
4. قم بإزالته من القائمة وأضفه إلى القائمة الإيقاف.
5. تحقق من جميع الشبكات المجاورة. تخطي تلك التي لم يتم تمريرها (1. في "القائمة الإغلاق" و 2. العقبات) وأضفها إلى القائمة المفتوحة إذا لم تكن موجودة بالفعل. خذ المربع المحدد مثل العقدة الأصل للمربع الجديد.
6. إذا كانت الشبكة المجاورة بالفعل في القائمة المفتوحة ، تحقق مما إذا كان المسار الحالي أفضل. بمعنى آخر ، تحقق مما إذا كانت قيمة G أقل إذا وصلنا إليها بمسار جديد. إذا لم يكن كذلك ، فلا شيء
يفعل. (هنا ، لا يوجد حكم في رمزتي)
7. نكرر هذه العملية حتى تتم إضافة الشبكة المستهدفة (نقطة النهاية "B") إلى "القائمة المفتوحة" ، مما يشير إلى أن نقطة النهاية B موجودة بالفعل حول العقدة السابقة التي تمت إضافتها إلى "القائمة الإغلاق". ما عليك سوى اتخاذ خطوة واحدة للوصول إلى نهاية نقطة ب.
8. نضيف نقطة نهاية B إلى "القائمة الإغلاق"
9. في الخطوة الأخيرة ، نحتاج إلى تمثيل المسار من نقطة البداية إلى نقطة النهاية ب. يتم عرض دور العقدة الأصل. عن طريق تغيير قيمة العقدة الأصل لعقدة نقطة النهاية في "إغلاق القائمة" ، يمكنك عرض المسار باتباع القرائن.
تحقق من الرمز
حزمة a_star_search ؛ استيراد java.util.arraylist ؛ الفئة العامة ASTAR {/*** استخدم ArrayList Array كـ "قائمة مفتوحة" و "إغلاق قائمة"*/arrayList <Node> open = new ArrayList <Node> () ؛ ArrayList <Node> elut = new ArrayList <node> () ؛ point* @return*/public double gethvalue (node currentnode ، node endnode) {return (math.abs (currentnode.getx () - endnode.getx ()) + math.abs (currentnode.gety () - endnode.gety ())* 10 ؛ CurrentNode) {if (currentnode.getpnode ()!! = null) {if (currentNode.getx () == currentnode.getpnode (). currentnode.getgvalue ()+10 ؛} return currentnode.getgvalue ()+14 ؛} return currentnode.getgvalue () ؛}/** * احصل على القيمة f: g+h * param currentnode */return */public getfvalue (node currentnode) {return currentnode.getgval () * أضف العقد حول العقدة المحددة إلى "القائمة المفتوحة" * param node * param map */public void inopen (node node ، map map) {int x = node.getx () ؛ int y = node.gety () ؛ for (int i = 0 ؛ i <3 ؛ i ++) {for ( هل ، ليست عقبة ، وليس في القائمة المغلقة) ، ولم يتم تضمين قائمة الافتتاح ، ولا يتم تحديدها 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]) ؛ // the يتم استخدام العقدة المحددة كأصوات الأصل map.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] 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 */public void sort (ArrayList <Node> arr) {for (int i = 0 ؛ i <arr.size ()-1 ؛ i ++) {for (int j = i+1 ؛ j <arr.size () ؛ 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) ؛ // set غير قابل للوصول إلى open.remove (node) ؛ close.add (node) ؛}} search public void (Map Map) {// قم بتشغيل العقد حول نقطة البداية ، أي ، هذا هو ، inopen (map.getMap () [map.getStartNode () node (). getx ()] [map.getStartNode () etstartnode (). gety ()] do {inopen (open.get (0) ، map) ؛ inclose (open.get (0) ، open) ؛ sort (open) ؛ end} بينما (! open.contains (map.getMap () [map.getendnode (). getx ()] [map.getendnode (). inclose (map.getMap () [map.getendnode (). getx ()] [map.getendnode (). Node () ؛ // <span style = "White-Space: pre"> </span> node = map.getMap () [map.getendnode (). getx ()] [map.getendnode (). gety ()] == map.getStartNode () style = "white-space: pre"> </span> map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()].أخيرا اكتب طريقة رئيسية
حزمة a_star_search ؛ Maintest الفئة العامة {public static void main (string [] args) {map map = new map () ؛ Astar Astar = New Astar () ؛ map.showmap () ؛ ASTAR.Search (MAP) ؛ System.out.println ("======================================================================================================================= =================================================================================================================================================================== =================================================================================================================================================================== ================================================================================================================================================ map.showmap () ؛قم بتعديل الخريطة واختبارها لمعرفة التأثير
٪ ٪ ٪ ٪ ٪ ٪ ٪ ٪ oooo ٪ oo ===================================== يتعلق ٪ ٪ ٪ ٪ ٪
لخص
لضمان وجود أقصر مسار (الحل الأمثل) ، يكمن المفتاح في اختيار وظيفة التقدير H (n): قيمة المسافة الفعلية لقيمة التقدير h (n) <= n إلى العقدة الهدف. في هذه الحالة ، هناك العديد من النقاط التي تم تفتيشها ، ونطاق البحث كبير ، والكفاءة منخفضة. لكن يمكن الحصول عليها
الحل الأمثل. إذا كانت القيمة المقدرة> القيمة الفعلية ، فإن عدد بحث النقاط صغير ، ومدى البحث صغير ، والكفاءة عالية ، ولكن لا يمكن أن تضمن الحصول على الحل الأمثل.
أكبر شعور هو: أكثر الأشياء المحرمة في الصيد لمدة ثلاثة أيام ويومين من تجفيف الشبكة. قد لا يكون المبلغ كبيرًا ، ولكن يجب أن يكون الاستمرارية ، والمفتاح هو الثبات.
آمل أن يتمكن كل مبرمج من كتابة التعليمات البرمجية بسعادة ويفعل ما يحب القيام به.
ما سبق هو كل محتوى هذه المقالة حول برمجة Java وتنفيذ الكود الكامل لخوارزمية*. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها.