Travelling Salesman Problem - Computing A Solution

Computing A Solution

The traditional lines of attack for the NP-hard problems are the following:

  • Devising algorithms for finding exact solutions (they will work reasonably fast only for small problem sizes).
  • Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver either seemingly or probably good solutions, but which could not be proved to be optimal.
  • Finding special cases for the problem ("subproblems") for which either better or exact heuristics are possible.

Read more about this topic:  Travelling Salesman Problem

Famous quotes containing the word solution:

    “Give a scientist a problem and he will probably provide a solution; historians and sociologists, by contrast, can offer only opinions. Ask a dozen chemists the composition of an organic compound such as methane, and within a short time all twelve will have come up with the same solution of CH4. Ask, however, a dozen economists or sociologists to provide policies to reduce unemployment or the level of crime and twelve widely differing opinions are likely to be offered.”
    —Derek Gjertsen, British scientist, author. Science and Philosophy: Past and Present, ch. 3, Penguin (1989)