Great deluge algorithm

The name comes from the analogy that in a great deluge a person climbing a hill will try to move in any direction that does not get his/her feet wet in the hope of finding a way up as the water level rises.

In a typical implementation of the GD, the algorithm starts with a poor approximation, S, of the optimum solution.

A numerical value called the badness is computed based on S and it measures how undesirable the initial approximation is.

Another numerical value called the tolerance is calculated based on a number of factors, often including the initial badness.

A new approximate solution S' , called a neighbour of S, is calculated based on S. The badness of S' , b' , is computed and compared with the tolerance.