If an animal has a distance of 2 to its cage in the cage graph, then we need at least 2 moves to fix this. Since in every move only one animal is moved (well, the empty cage changes too, but emptyness is not an animal), the sum of the distances of all animals to their cages is a lower bound for the time needed--- meaning that we cannot do it in less time. However, often we need longer, even when playing optimally. Try it out in this modification of the random start and target state applet, which also shows the lower bound. Check out that there are cases where you cannot decrease this lower bound, no matter how you move. Another side remark: How is the bound related to the average distance of the graph, which, remember, equals 11/9? Create 50 random instances of the puzzle by clicking 50 times on the button "New Game", and write down the bound. Then calculate the average bound. I got a value of 6.64---what did you get? How do you think is this average bound related to the average distance of 11/9? |
|