2

Consider the standard recursive solution to the Towers of Hanoi problem. In the traditional problem, all moves cost the same. Now, suppose the cost of a move is the size of the disk, with $1$ being the cost of the smallest disk, $2$ the second smallest, and so on. Express, as a recurrence relation, the cost of solving the $n$-disk problem.

Hey I don't understand this question at all since the traditional problem the cost would just be $(2^n - 1) \cdot cost$. But now we have to keep track of each disk which is unknown.

Armando j18eos
  • 3,907
Darkflame
  • 21
  • "But now we have to keep track of each disk which is unknown." What is meant by "unknown"? You mean you don't know the cost to move a size $k$ disk, or you don't know how to solve it? – k99731 Mar 01 '16 at 22:27
  • Suppose that you know the cost of moving the n biggest disks from one pile to the other, deduce the cost of moving the n+1 biggest disks from one pile to the other – H. Potter Mar 01 '16 at 22:28
  • 1
    I think the recursive solution, which minimizes the number of moves, will also minimize your cost function. The biggest disk (highest cost) only has to be moved once in the recursive solution, and of course it has to be moved at least once in any solution. Before it can be moved, all the other disks have to be reassembled, and after the big disk is moved they again have to be reassembled. So perhaps there's the germ of a proof by induction. – hardmath Mar 01 '16 at 22:30
  • The moves of each disk is unknown to me is what i meant like how would we know if the small disk was moved x amount of time – Darkflame Mar 01 '16 at 22:32
  • A cost per disk doesn't change the sequence of moves in any way since the solution is already the minimum number of moves (and minimum per disk) required to move all disks to the goal. – Carser Mar 01 '16 at 22:34
  • @Jedediyah: you make it sound as if the solution won't depend upon the cost function. Do you really think that's right? (I'm sure hardmath's suggestion will work out for the cost function given in the question.) – Rob Arthan Mar 01 '16 at 22:41
  • alright let say we have 3 disk . we would have to move the smallest disk 4 time, med 2 time, and biggest 1 time . so the cost would just be 41 + 2 2 + 1*3 = total cost correct? – Darkflame Mar 01 '16 at 22:41
  • This is an entertaining argument, but isn’t it somewhat irrelevant to the question? That only asks you to compute to cost of the standard solution, not to find an optimal-cost solution. – amd Mar 01 '16 at 22:53
  • I'm stumped now lol >.> I mean from my point of view the cost of each disk are different for the different size of disk. so what i did was check how many time the small one moves and medium and largest one and multiply it by each cost – Darkflame Mar 01 '16 at 22:59
  • @amd: the question says "cost of solving the problem", which is being reasonably interpreted as "minimal cost". Darkflame: can you fix your question to make it clear what you are actually asking, please. – Rob Arthan Mar 01 '16 at 23:15
  • @RobArthan, yes that's correct, adding a cost will not change the solution for $n$ disks since the solution already moves each disk its minimum number of times. – Carser Mar 01 '16 at 23:24
  • @Jedediyah: your line of argument doesn't work in general (but it may well be right in this particular case): there might be a solution that moves a disk that is cheap to move many more times than the minimum number while reducing the cost of more expensive moves. Minimising $\Sigma x_i$ is not the same as minimising $\Sigma c_i x_i$. – Rob Arthan Mar 01 '16 at 23:33
  • @RobArthan Oh yes of course you are correct about that general minimization, but in Towers of Hanoi you can see quickly that every move in its solution is required to progress toward the goal state. There are no excess moves or alternative sequences (such as the shifting of smaller tiles to make a shorter path for larger tiles). This is in part why String's solution below is correct. – Carser Mar 01 '16 at 23:45

1 Answers1

1

As the question asks you to simply write a recurrence relation for the cost, I am assuming it is for the original recursive solution. If instead you mean to at the same time minimize the cost, that could potentially be a different problem. The latter I have not considered in any detail.

Suppose $C(n)$ denotes the cost of solving it with $n$ discs. Then the $C(n+1)$ case goes as follows:

  1. We have the cost $C(n)$ of a sequence that will have to be performed twice
  2. Just add the cost of moving the $(n+1)$-th disc, and you are done

Writing out the details of this will establish a recurrence relation for $C(n+1)$ expressed in terms of $C(n)$ and some simple expression for the cost of the $(n+1)$-th disc. Can you take it from there?

String
  • 18,395
  • It is not so simple as just adding the cost of the $(n+1)$-th disc since there will be an intermediate phase of moving all of the discs above that to the middle peg, then moving the $(n+1)$-th disc, then moving all of the previous disks again to be on top. – Carser Mar 01 '16 at 23:22
  • @Jedediyah: Which is exactly why it says "twice" under item 1. This is just the well known recursive solution. – String Mar 01 '16 at 23:24
  • Ha yes that is a rather important oversight on my part. – Carser Mar 01 '16 at 23:26
  • I don't get why we are looking for n+1 disk T_T sorry – Darkflame Mar 01 '16 at 23:37
  • @Darkflame: It is a recurrence relation. In comparison, the recurrence relation for the number of steps $S(n)$ in the original solution of the problem is given as $$S(n+1)=2\cdot S(n)+1$$ which means that the solution for $n+1$ discs has as many steps as two times the solution with $n$ discs plus one extra step. Some authors prefer to write it as $$S(n)=2\cdot S(n-1)+1$$ instead, but that is just a matter of taste regarding indices. – String Mar 02 '16 at 15:38