This shows you the differences between two versions of the page.

cs-312:hw25 [2014/12/31 16:08] ringger created |
cs-312:hw25 [2014/12/31 16:22] (current) ringger |
||
---|---|---|---|

Line 8: | Line 8: | ||

- | For questions 1 and 2, consider the following instance of the TSP with cost matrix <math>M</math>: | + | For questions 1 and 2, consider the following instance of the TSP with cost matrix $M$: |

$$ | $$ | ||

Line 19: | Line 19: | ||

$$ | $$ | ||

- | in which (for example) it costs 4 to get from city 1 to city 2, there is no edge from city 1 to city 1 (hence the <math>\infty</math>), and in general it costs <math>M[i,j]</math> to get from city <math>i</math> to city <math>j</math>. | + | in which (for example) it costs 4 to get from city 1 to city 2, there is no edge from city 1 to city 1 (hence the $\infty$), and in general it costs $M[i,j]$ to get from city $i$ to city $j$. |

===Question 1=== | ===Question 1=== | ||

- | Reduce all rows and columns of the cost matrix <math>M</math>. Give both the reduced cost matrix and the resulting lower bound on the cost of the optimal tour. | + | Reduce all rows and columns of the cost matrix $M$. Give both the reduced cost matrix and the resulting lower bound on the cost of the optimal tour. |

===Question 2=== | ===Question 2=== | ||

Generate a quick, correct, but not necessarily optimal solution to this TSP instance (i.e., an initial “BSSF”). List the cities in the resulting tour and give the cost of that tour. This tour cost will be an upper bound on the optimal tour cost. | Generate a quick, correct, but not necessarily optimal solution to this TSP instance (i.e., an initial “BSSF”). List the cities in the resulting tour and give the cost of that tour. This tour cost will be an upper bound on the optimal tour cost. | ||