مساعدة كرمال النبي

[bassel01]

مرحبا لو سمحتو كيف ممكن أوجد كل الحلول الممكنة لهالمسألة باستخدام الخوارزمية التراجعية
لتكن لدينا مجموعة من أعداد صحيحة مختلفة، والمطلوب تشكيل سلسلة من هذه الأرقام بحيث يكون الفرق ما بين كل عددين متتاليين إما زيادة واحد أو ناقص واحد.
مثال: لتكن لدينا الأعداد التالية: 1 , 2 , 2 , 1 , 3 , 4 , 4 , 5 , 5 , 6
فتصبح على الشكل التالي : 1 , 2 , 1 , 2 , 3 , 4 , 5 , 4 , 5 , 6
أو: 1 , 2 , 1 , 2 , 3 , 4 , 5 , 6 , 5 , 4
أما مجموعة الأعداد التالية مثلاً ليس لها حل: 1 , 1 , 2 , 2 , 3 , 4 , 4 , 5 , 5 , 7

[أبو الفوارس]

- أول خوارزمية تتبادر إلى الذهن (خوارزمية ساذجةnaive ) هي:
تجريب كل السلاسل الممكنة، و من أجل كل سلسلة يجب التحقق ما إذا كانت حلا أم لا.
المشكل مع هذه الخورزمية هو عدد السلاسل التي يجب التحقق منها (n! إذا كان n هو عدد عناصر المجموعة)

- أما بالتراجع :
هي طريقة تشبه شجرة البحث (research tree )، حيث يجب إختيار العنصر الأول في السلسلة، ثم البحث عن العنصر الثاني الذي يحقق خاصية الحل (من العناصر المتبقية في المجموعة)، ثم إختيار العنصر الثالث و هكذا دواليك إلى أن تكتمل السلسلة، و في حالة عدم وجود عنصر يحقق الخاصية (أو في حالة إكتمال السلسلة)، يجب الرجوع خطوة إلى الوراء (و من هنا تسمى هذه الخوارزمية بالتراجعية) لتغير آخر عنصر مختار، بعنصر آخر يحقق الخاصية....و هكذا دواليك.

- يمكن تحسين هذه الخوارزمية لتفادي تكرار الحلول المزدوجة (نفس الحل الذي يتكرر أكثر من مرة)