- خوارزمية تسلق التل هي خوارزمية بحث محلية تتحرك باستمرار في اتجاه زيادة الارتفاع/القيمة للعثور على قمة الجبل أو أفضل حل للمشكلة. وينتهي عندما يصل إلى قيمة الذروة حيث لا يوجد جار له قيمة أعلى.
- خوارزمية تسلق التل هي تقنية تستخدم لتحسين المسائل الرياضية. أحد الأمثلة التي تمت مناقشتها على نطاق واسع لخوارزمية تسلق التل هي مشكلة البائع المتجول حيث نحتاج إلى تقليل المسافة التي يقطعها البائع.
- ويسمى أيضًا بالبحث المحلي الجشع لأنه ينظر فقط إلى الدولة المجاورة الجيدة وليس أبعد من ذلك.
- تحتوي عقدة خوارزمية تسلق التل على مكونين هما الحالة والقيمة.
- يتم استخدام تسلق التلال في الغالب عندما يتوفر إرشاد جيد.
- في هذه الخوارزمية، لا نحتاج إلى صيانة شجرة البحث أو الرسم البياني والتعامل معها لأنها تحتفظ فقط بحالة حالية واحدة.
مميزات لعبة تسلق التلال:
فيما يلي بعض الميزات الرئيسية لخوارزمية تسلق التل:
مخطط مساحة الدولة لتسلق التلال:
يعد مشهد مساحة الحالة تمثيلًا رسوميًا لخوارزمية تسلق التل والتي تعرض رسمًا بيانيًا بين الحالات المختلفة للخوارزمية والوظيفة/التكلفة الموضوعية.
على المحور ص، اتخذنا الوظيفة التي يمكن أن تكون دالة موضوعية أو دالة تكلفة، ومساحة الحالة على المحور السيني. إذا كانت الدالة على المحور Y هي التكلفة، فإن هدف البحث هو العثور على الحد الأدنى العالمي والحد الأدنى المحلي. إذا كانت دالة المحور Y هي دالة موضوعية، فإن هدف البحث هو العثور على الحد الأقصى العالمي والحد الأقصى المحلي.
مناطق مختلفة في المشهد الفضائي للدولة:
الحد الأقصى المحلي: الحد الأقصى المحلي هو حالة أفضل من الدول المجاورة لها، ولكن هناك أيضًا حالة أخرى أعلى منها.
الحد الأقصى العالمي: الحد الأقصى العالمي هو أفضل حالة ممكنة للمشهد الفضائي للدولة. لديها أعلى قيمة للوظيفة الموضوعية.
الوضع الحالي: إنها حالة في مخطط أفقي حيث يتواجد الوكيل حاليًا.
الحد الأقصى المحلي المسطح: إنها مساحة مسطحة في المشهد حيث جميع الدول المجاورة للدول الحالية لها نفس القيمة.
كتف: إنها منطقة هضبة ذات حافة شاقة.
أنواع خوارزمية تسلق التلال:
- تسلق التلال البسيطة:
- أشد درجات صعود التلال:
- تسلق التل العشوائي:
1. تسلق التلال البسيط:
يعد تسلق التل البسيط أبسط طريقة لتنفيذ خوارزمية تسلق التل. فهو يقوم فقط بتقييم حالة العقدة المجاورة في كل مرة واختيار الحالة الأولى التي تعمل على تحسين التكلفة الحالية وتعيينها كحالة حالية . إنه يتحقق فقط من أنها حالة لاحقة واحدة، وإذا وجدت أفضل من الحالة الحالية، فسيتم نقلها إلى نفس الحالة. تحتوي هذه الخوارزمية على الميزات التالية:
- أقل استهلاكا للوقت
- أقل الحل الأمثل والحل غير مضمون
خوارزمية تسلق التلال البسيطة:
- إذا كانت حالة الهدف، فعد بالنجاح وانسحب.
- وإلا إذا كانت أفضل من الحالة الحالية، فقم بتعيين حالة جديدة كحالة حالية.
- وإلا، إن لم يكن أفضل من الحالة الحالية، فارجع إلى الخطوة 2.
2. تسلق التلال الأكثر انحدارًا:
خوارزمية الصعود الأكثر انحدارًا هي نسخة مختلفة من خوارزمية تسلق التل البسيطة. تقوم هذه الخوارزمية بفحص جميع العقد المجاورة للحالة الحالية وتختار عقدة مجاورة واحدة تكون الأقرب إلى حالة الهدف. تستهلك هذه الخوارزمية وقتًا أطول أثناء البحث عن العديد من الجيران
خوارزمية تسلق التلال الأكثر انحدارًا:
- لتكن SUCC دولة بحيث يكون أي خليفة للدولة الحالية أفضل منها.
- لكل عامل ينطبق على الحالة الحالية:
- قم بتطبيق العامل الجديد وإنشاء حالة جديدة.
- تقييم الحالة الجديدة.
- إذا كانت حالة الهدف، فقم بإعادتها والانسحاب منها، وإلا قم بمقارنتها بـ SUCC.
- إذا كانت أفضل من SUCC، فقم بتعيين الحالة الجديدة كـ SUCC.
- إذا كانت SUCC أفضل من الحالة الحالية، فقم بتعيين الحالة الحالية إلى SUCC.
3. تسلق التل العشوائي:
إن تسلق التل العشوائي لا يفحص كل جيرانه قبل التحرك. بدلاً من ذلك، تقوم خوارزمية البحث هذه باختيار عقدة مجاورة واحدة بشكل عشوائي وتقرر ما إذا كانت ستختارها كحالة حالية أو تفحص حالة أخرى.
مشاكل في خوارزمية تسلق التل:
1. الحد الأقصى المحلي: الحد الأقصى المحلي هو حالة ذروة في المشهد الطبيعي وهي أفضل من كل ولاية من الولايات المجاورة لها، ولكن هناك حالة أخرى موجودة أيضًا وهي أعلى من الحد الأقصى المحلي.
تجد في الخريطة C++
حل: يمكن أن تكون تقنية التراجع حلاً للحد الأقصى المحلي في المشهد الفضائي للحالة. قم بإنشاء قائمة بالمسار الواعد حتى تتمكن الخوارزمية من تتبع مساحة البحث واستكشاف المسارات الأخرى أيضًا.
2. الهضبة: الهضبة هي المنطقة المسطحة من مساحة البحث التي تحتوي فيها جميع الدول المجاورة للحالة الحالية على نفس القيمة، لأن هذه الخوارزمية لا تجد أي اتجاه أفضل للتحرك. قد يتم فقدان عملية البحث عن تسلق التل في منطقة الهضبة.
حل: الحل بالنسبة للهضبة هو اتخاذ خطوات كبيرة أو خطوات صغيرة جدًا أثناء البحث، لحل المشكلة. حدد بشكل عشوائي حالة بعيدة عن الحالة الحالية، لذلك من الممكن أن تتمكن الخوارزمية من العثور على منطقة غير هضبة.
3. التلال: التلال هي شكل خاص من الحد الأقصى المحلي. مساحتها أعلى من المناطق المحيطة بها، ولكنها في حد ذاتها منحدر، ولا يمكن الوصول إليها بحركة واحدة.
حل: باستخدام البحث ثنائي الاتجاه، أو من خلال التحرك في اتجاهات مختلفة، يمكننا تحسين هذه المشكلة.
محاكاة الصلب:
خوارزمية تسلق التل التي لا تتحرك أبدًا نحو قيمة أقل مضمونة لتكون غير مكتملة لأنها يمكن أن تتعثر عند الحد الأقصى المحلي. وإذا طبقت الخوارزمية سيرًا عشوائيًا، عن طريق تحريك خليفة، فقد تكتمل ولكنها ليست فعالة. محاكاة الصلب هي خوارزمية تنتج كلا من الكفاءة والاكتمال.
في المصطلح الميكانيكي التلدين هي عملية تصلب المعدن أو الزجاج لدرجة حرارة عالية ثم تبريده تدريجياً، مما يسمح للمعدن بالوصول إلى الحالة البلورية منخفضة الطاقة. يتم استخدام نفس العملية في محاكاة التلدين حيث تختار الخوارزمية حركة عشوائية، بدلاً من اختيار الحركة الأفضل. فإذا أدت الحركة العشوائية إلى تحسين الحالة، فإنها تتبع نفس المسار. بخلاف ذلك، تتبع الخوارزمية المسار الذي لديه احتمال أقل من 1 أو تتحرك لأسفل وتختار مسارًا آخر.