مسألة أبراج هانوي

في الترتيب بالدمج وبناء الأشجار الثنائية، فكّكنا المسألة الأصلية إلى مسألتين فرعيتين، حجم كل منهما نصف حجم المسألة الأصلية. أما في مسألة أبراج هانوي، فنتبنّى استراتيجية تفكيك مختلفة.

نرمز إلى مسألة أبراج هانوي ذات الحجم $i$ بالرمز $f(i)$. فمثلاً، تمثّل $f(3)$ نقل $3$ أقراص من A إلى C.

التفكير في الحالات الأساسية

كما يوضح الشكل أدناه، في المسألة $f(1)$، عندما يكون هناك قرص واحد فقط، يمكننا نقله مباشرةً من A إلى C.

وكما يوضح الشكل أدناه، في المسألة $f(2)$، عندما يكون هناك قرصان، وبما أنه يجب علينا دائماً إبقاء القرص الأصغر فوق القرص الأكبر، نحتاج إلى استخدام B للمساعدة في النقل.

1. أولاً، انقل القرص الأصغر من A إلى B.
2. ثم انقل القرص الأكبر من A إلى C.
3. وأخيراً، انقل القرص الأصغر من B إلى C.

ويمكن تلخيص عملية حل المسألة $f(2)$ بأنها: نقل قرصين من A إلى C بمساعدة B. ويُسمى C هنا العمود الهدف، ويُسمى B العمود المؤقت.

تفكيك المسائل الفرعية

في المسألة $f(3)$، عندما يكون هناك ثلاثة أقراص، يصبح الوضع أكثر تعقيداً بعض الشيء.

وبما أننا نعرف بالفعل حلّي $f(1)$ و$f(2)$، يمكننا التفكير من منظور التقسيم والتغلب، بمعالجة القرصين العلويين على A وحدةً واحدة، وتنفيذ الخطوات الموضحة في الشكل أدناه. وبذلك ننجح في نقل الأقراص الثلاثة من A إلى C.

1. اجعل B هو العمود الهدف وC هو العمود المؤقت، وانقل قرصين من A إلى B.
2. انقل القرص المتبقي من A مباشرةً إلى C.
3. اجعل C هو العمود الهدف وA هو العمود المؤقت، وانقل قرصين من B إلى C.

وفي جوهر الأمر، نفكّك المسألة $f(3)$ إلى مسألتين فرعيتين $f(2)$ ومسألة فرعية واحدة $f(1)$. ويمثّل حل هذه المسائل الفرعية الثلاث بالترتيب حلاً للمسألة الأصلية. وهذا يدل على أن المسائل الفرعية مستقلة ويمكن دمج حلولها.

ومن ذلك يمكننا تلخيص استراتيجية التقسيم والتغلب لحل مسألة أبراج هانوي، كما يوضح الشكل أدناه: فكّك المسألة الأصلية $f(n)$ إلى مسألتين فرعيتين $f(n-1)$ ومسألة فرعية واحدة $f(1)$، وحلّ هذه المسائل الفرعية الثلاث بالترتيب التالي.

1. انقل $n-1$ قرصاً من A إلى B بمساعدة C.
2. انقل القرص المتبقي $1$ مباشرةً من A إلى C.
3. انقل $n-1$ قرصاً من B إلى C بمساعدة A.

وبالنسبة إلى هاتين المسألتين الفرعيتين $f(n-1)$، يمكننا تفكيكهما تعاودياً بالطريقة نفسها حتى الوصول إلى أصغر مسألة فرعية $f(1)$. وحل $f(1)$ معروف ولا يتطلب سوى عملية نقل واحدة.

تنفيذ الشيفرة

في الشيفرة، نعرّف دالة تعاودية dfs(i, src, buf, tar)، غرضها نقل الأقراص $i$ العلوية من العمود src إلى العمود الهدف tar بمساعدة العمود المؤقت buf:

/* حل مسألة أبراج هانوي */
func solveHanota(A, B, C *list.List) {
	n := A.Len()
	// انقل الأقراص n العلوية من A إلى C بمساعدة B
	dfsHanota(n, A, B, C)
}

/* حل مسألة أبراج هانوي */
function solveHanota(A: number[], B: number[], C: number[]): void {
    const n = A.length;
    // انقل الأقراص n العلوية من A إلى C بمساعدة B
    dfs(n, A, B, C);
}

وكما يوضح الشكل أدناه، تشكّل مسألة أبراج هانوي شجرة تعاود بارتفاع $n$، حيث تمثّل كل عقدة مسألة فرعية تقابل استدعاءً للدالة dfs()، لذا يكون التعقيد الزمني $O(2^n)$ والتعقيد المكاني $O(n)$.