Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

List  length  involves  a  trade-off  that  you  refine  by  using  experimentation  after 

each test to determine whether enlarging or shrinking the candidate list brings an 

advantage or a disadvantage in terms of time to complete and solution quality.

Base the choice of the new solution on a heuristic and, given the problem, decide 

on the best solution. For instance, in the TSP problem, use the trip switches that 

shorten the total tour length the most. In certain cases, you can use a random 

solution  in  place  of  a  heuristic  (as  you  discover  in  the  SAT-2  problem  in  this 

 chapter). Even when you have a clear heuristic, the algorithm could find multiple 

best  solutions.  Injecting  some  randomness  could  make  your  local  search  more 

efficient. When faced with many solutions, you can safely choose one randomly.

Ideally, in a local search, you get the best results when you run multiple searches, 

injecting randomness as much as you can into the start solution and along the way 

as you decide the next process step. Let the heuristic decide only when you see a 

clear advantage to doing so. Local search and randomness are good friends.

Your search has to stop at a certain point, so you need to choose stopping rules for 

the local search. When your heuristic can’t find good neighbors anymore or it can’t 

improve solution quality (for instance, computing a cost function, as it happens in 

TSP, by measuring the total length of the tour). Depending on the problem, if you 

don’t create a stopping rule, your search may go on forever or take an unacceptably 

long time. In case you can’t define a stopping, just limit the time spent looking for 

solutions or count the number of trials. When counting trials, you can decide that 

it’s not worth going on because you calculate the probability of success and at a 

certain point, the probability of success becomes too small.