Differences

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

Link to this comparison view

cs-312:hw25 [2014/12/31 23:08]
ringger created
cs-312:hw25 [2014/12/31 23: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 $ito 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.
  
cs-312/hw25.txt · Last modified: 2014/12/31 23:22 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0