Actual responses to actual questions from students of Math 344, Introduction to Combinatorics (Spring 2004).
This problem refers to Figure 3.20, which seems to be missing its final row.
Why, yes, it is missing its final row. According to this site, Figure 3.20 should be:
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | ∞ | 3 | 4 | 2 | 8 | 3 |
| 2 | 5 | ∞ | 3 | 4 | 4 | 5 |
| 3 | 4 | 1 | ∞ | 5 | 3 | 4 |
| 4 | 4 | 2 | 6 | ∞ | 4 | 5 |
| 5 | 3 | 3 | 3 | 5 | ∞ | 4 |
| 6 | 7 | 4 | 5 | 6 | 7 | ∞ |
I hope this helps.
Could you please tell me what the solution is for this problem, or at least what the final Hamilton circuit is?
I get a circuit 1–6–4–2–3–5–1, for a cost of 20. This is the cost the book gets, but a different circuit.
I've been using the branch-and-bound algorithm, but I keep on having to backtrack and never arrive at the solution, and have wasted several hours on it. I have also tried using the first few steps shown in Figure 3.21 in the text, but subsequent steps seem to require backtracking on the very first branch (not using c_51), so I'm not sure if I've been doing it correctly.
I'm not quite sure what you mean by ``backtracking on the very first branch.'' The algorithm (Figure 3.21) requires that you essentially build a tree. At each leaf you have a lower bound (L.B.). You extend the tree from the leaf that has the smallest L.B. – that is, you branch from the leaf with the smallest bound.
Yes, at some point you may have to ``backtrack'' to a higher level vertex, but you shouldn't ever have to re-draw the tree.
Also, I was wondering something: since we have to block subcircuits when we're constructing the Hamilton circuit, if we have already constructed a partial solution 5–1–4, and we next choose edge (2,6), then we have to set c62 (and only this edge cost) to ``infinity,'' correct?
I'm not sure what you mean here, either. If you have a partial solution 5–1–4, you shouldn't next choose edge (2,6). You should choose edge (4,x) for some x (not 5, 1, or 4), or possibly edge (x,5) for some x (not 5, 1, or 4). [You could choose (2,6), but this puts you in a position of building a circuit from disconnected pieces, which is less straightforward.] Say you choose edge (4,6). Then you should eliminate column 4 and row 6, and put c65 = ∞. Why c65? Because this way we block the subcircuit 5–1–4–6–5.