المعلوماتية > عام
أبراج هانوي
إذا كنتَ أحدَ طلابِ علومِ الحاسوب، فلا بد أنكَ سمعتَ بلعبةِ أبراج هانوي ضمن الفقرةِ أو المادةِ الخاصةِ بالخوارزميات العَوديةِ والتكرارية، وحتى إن لم تكن طالباً لعلوم الحاسوب سنتعرفُ أكثرَ في هذا المقال عن هذه الأحجية.
أبراج هانوي هي أحجيةٌ وضعها العالم لوكاس عام 1883 وتنصُّ على ما يلي:
لدينا عدد n من الأقراص، متوضعّةٌ على عمودٍ بترتيبٍ منتَظَمٍ بناءً على أحجامِها، بحيثُ يتوضّعُ القرصُ الأكبر في الأسفل والقرصُ الاًصغر في الأعلى، نريد نقلَ هذه الأقراص من العمود الموجودة فيه إلى عمودٍ آخرَ باستخدامِ عمودٍ ثالثٍ للمساعدَة، لكنْ ضمنَ شروطٍ محددةٍ تُقيدنا بنقلِ قرصٍ واحدٍ فقط في النقلةِ الواحدة إضافةً لعدمِ وجوبِ توضُّعِ أحدِ الأقراص فوق قرصٍ أصغرَ منه، أي يجبُ المحافظةُ على الترتيب حتى عند الحركات الوسيطة للنقل (باستخدام العمودِ الثالث).
لنرى كيفيةَ حلِّ هذه المسألة بشكلٍ عَودي، وسنسمّي الأعمدةَ الثلاثةَ بـ "أ وَ ب وَ ج" بحيث تتوضعً الأقراصُ على العمودِ أ، ويتوجّبُ نقلُها للعمود ب باستخدام العمود ج كوسيط.
سنبدأُ بالحالة القاعديّة والتي نفرضُ فيها وجودَ قرصٍ واحدٍ فقط، نستطيع دوماً نقلَ قرصٍ وحيدٍ من العمود أ إلى العمود ب أو من أيِّ عمودٍ إلى آخر، وذلك لتحقيقِه الشروطَ المناسبةَ للعبة.
وسيكون مبدأُ الحلِّ دوماً عند n قرص هو حلُّ المسألة لـ n-1 قرص، إذ يستدعي التابعُ نفسّه حتى الوصول للحالة القاعدية المعلومة.
حسناً، سننتقل الآن إلى قرصين، أي أصبح لدينا n=2، يمكننا القيام بالنقلِ عبر ثلاثِ خطوات:
1- نقومُ بنقل القرص الأول (الأصغر) من العمودِ أ إلى العمود ج
2- ننقل القرص الثاني إلى العمود ب.
3- ننقل القرص الأول من العمود ج إلى العمود ب.
عبر هذه الخطواتِ الثلاثةِ يمكننا نقلُ القرصين من أيِّ عمودٍ إلى آخرَ ضمن شروط الأُحجية مُتَّبعين نفس الخطوات، إذاً نستنتج أنّ الخطوات اللازمة لـ n=2 هي ثلاث خطوات.
ماذا عن ثلاثة أقراص؟
في هذه الحالة سنُعامل القرصين 1 و2 على أنّهما قرصٌ واحدٌ -لقد أثبتنا سابقاً أنّه بإمكاننا نقلُ القرصينِ من عمودٍ إلى آخرَ بحرّيّة- ونُعامل القرصَ 3 على أنه قرص آخر مستقل.
نقومُ بتقسيم المسألةِ إلى مسائلَ جزئيةٍ ثمَّ نقوم بحلِّ كُلٍّ منها على حِدة، أي نقوم بالحلِّ لـ n-1 (في هذه الحالة n=3)
وذلك بنقل القرصين 1 و2 إلى العمودِ الوسيط كما ذكرنا سابقاً باستخدام الخطوات الثلاثة، بعدها نقوم بنقل القرص 3 من العمود أ إلى العمود ب، ولإنهاءِ المسألةِ نقومُ بنقلِ القرصين 1 و2 من العمود ج إلى العمود ب -نُذكِّر بأنّنا أثبتْنا إمكانيةَ نقلِ أيِّ قرصينِ بثلاثِ خطواتٍ بحرِّيَّةٍ بين عمودين-.
نُلاحظ هنا أنَّ نقلَ الأقراصِ الثلاثةِ من عمودٍ إلى آخرَ هو عمليةٌ غيرُ مقيَّدة، أي أننا نستطيعُ النقلَ بحرِّيَّةٍ من أيِّ عمودٍ إلى آخر، وتتمُّ هذه العملية بسبعِ خطوات، ثلاثِ خطواتٍ لكلِّ عمليةِ نقلٍ للقرصين 1 و2، وعمليةِ نقلٍ للقرص 3.
وعند رفعِ عددَ الأقراص إلى أربعة، فإن طريقة الحل ستبقى نفسها إذ:
* نقومُ بحلِّ المسألة لثلاثةِ أقراصٍ بشكلٍ عَوديٍّ كما ذكرنا ونقلِ الأقراص من العمود الأول إلى العمود الوسيط.
* نقوم بنقلِ القرص الأكبر من العمود الأول إلى العمود النهائي.
* نقوم بتكرارِ عمليّةِ نقلِ الأقراص الثلاثة الأولى بشكلٍ عَوديٍّ وذلكَ من العمودِ الوسيط إلى العمود النّهائي.
وتكونُ الخطوات اللازمةُ لحلِّ المسألة من أجل n=4 تساوي 15 خطوة (7 خطواتٍ لنقل الأقراص الثلاثةِ في كلِّ مرة + خطوةُ نقلِ القرص الأكبر).
بدأتْ تتضح الآن معالمُ المسألة وطريقةُ الحل، فنستنتجُ أنَّ:
* طريقةَ الحلِّ لـ n قرصٍ تتمُّ بشكلٍ عَودي، إذ تكونُ الحالة القاعدية هي نقلةٌ واحدةٌ عندما n=1، وتتم بـ:
- حلِّ المسألة بشكلٍ عَوديٍّ لجميعِ الأقراص من 1 إلى القرص n-1 وذلك بنقلِها من العمود الأول أياً كان، إلى العمود الوسيط.
- نقلِ القرص الأكبر n من العمود الأول إلى العمود النّهائي.
- نقلِ الأقراص من 1 إلى n-1 من العمود الوسيط إلى العمود النّهائي.
* لحل المسألة من أجل n قرص، فإنَّ ذلك يتطلّبُ 2^n -1 خطوة، إذ رأينا أنَّ العلاقةَ محقّقةٌ من أجل قِيَم n=1،2،3،4.
تروي الأساطيرُ أنَّ بعض الناسكين في جبال آسيا يعتقدون أنَّ لحظةَ حلِّ هذه اللعبة من أجل n=64 قرصٍ هي لحظةُ نهاية العالم، إذاً فالناسكون وحسب روايتهم بحاجةِ 2^64 -1 خطوة (2 مرفوع الى القوة n-1 )، وباعتبار أنَّهم يقومون بخطوة كل ثانية وعلى مدار اليوم دون انقطاعٍ فإنَّ حلَّ هذه اللعبة سيتطلَّب منهم ما يُقارب 584 مليار سنة.
المصادر: