<p>I'm doing an assignment about planning for tower of Hanoi problem using linear planning and I'm not allowed to use any recursive functions. The matter is that my solution is not optimal like the one from recursive method. It produces redundant steps. For example:</p> <p>I have 3 rods named A, B, C respectively and there are 2 disks named 1, 2 (disk 1 is smaller than disk 2, disk 1 is on disk 2), then there are 2 ways to move all the disks from rod A to rod C using rod B as intermediate rod as follow:</p> <ol> <li>(optimal like the output of recursive algorithm) <ul> <li>Move disk 1 to rod B</li> <li>Move disk 2 to rod C</li> <li>Move disk 1 to rod C</li> </ul> </li> <li>(non optimal using planning) <ul> <li>Move disk 1 to rod C</li> <li>Move disk 2 to rod B</li> <li>Move disk 1 to rod A</li> <li>Move disk 2 to rod C</li> <li>Move disk 1 to rod C</li> </ul> </li> </ol> <p>So how do I (more precise: an algorithm which can be programmable) know that disk 1 must move to rod B first instead of moving to disk C to gain optimal solution? I'll really appreciate your help. Thanks!</p>

<p>I wanted to visualize <strong>ratchet freak</strong> answer.</p> <h3>Example of size 5</h3> <p><img src="https://i.stack.imgur.com/HqdI0.gif" alt="enter image description here"></p> <h3>Example of size 6</h3> <p><img src="https://i.stack.imgur.com/0iT4Z.gif" alt="enter image description here"></p> <p>Larger sizes work the same way.</p> <h3>Additional details</h3> <ul> <li>The task is to write Hamilton path algorithm implementation.</li> <li>There are 3 rods<code>{initial, spare, destination}</code>. Your starting move depends on reminder of 2 : <ul> <li> <code>if n % 2 == 0</code>, start with spare rod</li> <li> <code>if n % 2 == 1</code>, start with destination rod</li> </ul> </li> <li>It takes <strong>2^n-1</strong> moves, to move the whole stack to destination stack.</li> </ul>

<p>the key is knowing how many disks need to be moved:</p> <p>it there are a even number of disks in the stack you start to the "spare" rod<br> if there are an odd number of disks in the stack you start to the "destination" rod </p>

Tower of Hanoi problem - linear planning

I'm doing an assignment about planning for tower of Hanoi problem using linear planning and I'm not allowed to use any recursive functions. The matter is that my solution is not optimal like the one from recursive method. It produces redundant steps. For example:

I have 3 rods named A, B, C respectively and there are 2 disks named 1, 2 (disk 1 is smaller than disk 2, disk 1 is on disk 2), then there are 2 ways to move all the disks from rod A to rod C using rod B as intermediate rod as follow:

(optimal like the output of recursive algorithm)
- Move disk 1 to rod B
- Move disk 2 to rod C
- Move disk 1 to rod C
(non optimal using planning)
- Move disk 1 to rod C
- Move disk 2 to rod B
- Move disk 1 to rod A
- Move disk 2 to rod C
- Move disk 1 to rod C

So how do I (more precise: an algorithm which can be programmable) know that disk 1 must move to rod B first instead of moving to disk C to gain optimal solution? I'll really appreciate your help. Thanks!

What is the problem of Tower of Hanoi?

Initially, all the disks are placed on one rod, one over the other in ascending order of size similar to a cone-shaped tower. The objective of this problem is to move the stack of disks from the initial rod to another rod, following these rules: A disk cannot be placed on top of a smaller disk.

What is Tower of Hanoi formula?

Given a Colored Magnetic Tower of Hanoi, the number of moves of disk k are P(k) = 3(k-1) and the total number of moves is S(N) = (3N – 1)/2.

What are the applications of Tower of Hanoi problem?

Applications of Tower of Hanoi: It has been used to determine the extent of brain injuries and helps to build/rebuild neural pathways in the brain as attempting to solve, Tower of Hanoi uses parts of the brain that involve managing time, foresight of whether the next move will lead us closer to the solution or not.

I wanted to visualize ratchet freak answer.

Example of size 5

enter image description here

Example of size 6

enter image description here

Larger sizes work the same way.

Additional details

The task is to write Hamilton path algorithm implementation.
There are 3 rods{initial, spare, destination}. Your starting move depends on reminder of 2 :
- if n % 2 == 0, start with spare rod
- if n % 2 == 1, start with destination rod
It takes 2^n-1 moves, to move the whole stack to destination stack.

the key is knowing how many disks need to be moved:

it there are a even number of disks in the stack you start to the "spare" rod
if there are an odd number of disks in the stack you start to the "destination" rod

Tower of Hanoi problem - linear planning

Tags:

java

crazy_in_love

People also ask