Differences

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

Link to this comparison view

cs-312:hw26 [2014/12/31 23:08]
ringger created
cs-312:hw26 [2014/12/31 23:23] (current)
ringger
Line 4: Line 4:
 Show all work neatly. Show all work neatly.
  
-The setting is B&B for TSP.  Consider the following reduced cost matrix ​<​math>​M</​math> ​for a state, in which <​math>​M[i,j] = \infty</​math> ​means that the path from <​math>​i</​math> ​to <​math>​j</​math> ​has been excluded from consideration (by setting its cost to infinity), with the lower bound lb=25. ​ Note that the edge (2,5) has already been included for the partial tour represented by this state.+The setting is B&B for TSP.  Consider the following reduced cost matrix ​$Mfor a state, in which $M[i,j] = \inftymeans that the path from $ito $jhas been excluded from consideration (by setting its cost to infinity), with the lower bound lb=25. ​ Note that the edge (2,5) has already been included for the partial tour represented by this state.
  
 $$ $$
Line 19: Line 19:
 ===Question 1=== ===Question 1===
 Suppose your algorithm includes the edge from city 5 to city 3 next (this edge has cost 0 relative to the current lower bound lb=25). ​ Give a new reduced cost matrix and new lower bound that have the following properties: Suppose your algorithm includes the edge from city 5 to city 3 next (this edge has cost 0 relative to the current lower bound lb=25). ​ Give a new reduced cost matrix and new lower bound that have the following properties:
-* '''​All'''​ edges that can now be excluded from consideration,​ even on feasibility grounds, have had their entry in the matrix replaced with <​math>​\infty</​math>​.+* '''​All'''​ edges that can now be excluded from consideration,​ even on feasibility grounds, have had their entry in the matrix replaced with $\infty$.
 * The resulting matrix has been reduced. * The resulting matrix has been reduced.
 * The new lower bound includes the impact of the reduction. ​ * The new lower bound includes the impact of the reduction. ​
cs-312/hw26.txt ยท Last modified: 2014/12/31 23:23 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