شرح خوارزمية لي بالأمثلة

تعد خوارزمية Lee أحد الحلول الممكنة لمشاكل توجيه المتاهة. إنه يعطي دائمًا الحل الأمثل ، إن وجد ، ولكنه بطيء ويتطلب ذاكرة كبيرة للتخطيط الكثيف.

فهم كيف يعمل

الخوارزمية هي خوارزمية breadth-firstمبنية تستخدم queuesلتخزين الخطوات. عادة ما تستخدم الخطوات التالية:

1. اختر نقطة البداية وأضفها إلى قائمة الانتظار.
2. أضف الخلايا المجاورة الصالحة إلى قائمة الانتظار.
3. أزل الموضع الذي أنت فيه من قائمة الانتظار وتابع إلى العنصر التالي.
4. كرر الخطوتين 2 و 3 حتى تصبح قائمة الانتظار فارغة.

أحد المفاهيم الأساسية التي يجب فهمها هو أن breadth-firstعمليات البحث تتم على نطاق واسع ، بينما depth-firstتتعمق عمليات البحث.

باستخدام مثال خوارزمية حل المتاهة ، depth-firstسيحاول النهج كل مسار ممكن واحدًا تلو الآخر حتى يصل إلى طريق مسدود أو النهاية ويعيد النتيجة. ومع ذلك ، قد لا يكون المسار الذي ترجع إليه هو الأكثر فاعلية ، ولكنه ببساطة المسار الأول الكامل للنهاية الذي تمكنت الخوارزمية من العثور عليه.

و breadth-firstسوف البحث بدلا الخروج إلى كل مساحة مفتوحة المجاور لنقطة البداية، ثم ابحث عن المساحات المفتوحة المحتملة الأخرى. سيستمر في القيام بذلك ، بالخروج طبقة تلو الأخرى ومحاولة كل مسار ممكن بالترادف ، حتى يجد نقطة النهاية. نظرًا لأنك تحاول كل مسار في نفس الوقت ، يمكنك التأكد من أن المسار الكامل الأول من البداية إلى النهاية هو الأقصر أيضًا.

التنفيذ

يحتوي C ++ على قائمة الانتظار التي تم تنفيذها بالفعل في المكتبة ، ولكن إذا كنت تستخدم شيئًا آخر ، فنحن نرحب بك لتطبيق الإصدار الخاص بك من قائمة الانتظار.

كود C ++:

int dl[] = {-1, 0, 1, 0}; // these arrays will help you travel in the 4 directions more easily int dc[] = {0, 1, 0, -1}; queue X, Y; // the queues used to get the positions in the matrix X.push(start_x); //initialize the queues with the start position Y.push(start_y); void lee() { int x, y, xx, yy; while(!X.empty()) // while there are still positions in the queue { x = X.front(); // set the current position y = Y.front(); for(int i = 0; i < 4; i++) { xx = x + dl[i]; // travel in an adiacent cell from the current position yy = y + dc[i]; if('position is valid') //here you should insert whatever conditions should apply for your position (xx, yy) { X.push(xx); // add the position to the queue Y.push(yy); mat[xx][yy] = -1; // you usually mark that you have been to this position in the matrix } } X.pop(); // eliminate the first position, as you have no more use for it Y.pop(); } }