Farthest insertion heuristic
The Farthest-Insertion-Heuristic ( furthest insertion, FARIN ) is an insertion heuristic and thus a heuristic opening method from graph theory . It is used to approximate a good solution to the traveling salesman's problem , in which the shortest (cheapest) Hamiltonian circle is sought on a complete graph .
The algorithm starts with a partial route, which consists of a single, randomly chosen node. The remaining nodes are then added iteratively until the tour contains all nodes of the graph. In each step, the algorithm selects the node furthest away from the sub-route that has already been calculated. This node is built into the existing partial route at the point, so that the slightest extension of the previous partial route is created.
Strictly speaking, the FARIN algorithm consists of two parts:
- Selection of the "most expensive" node ( far thest selection)
- Insertion at the "cheapest" position (cheapest in sertion)
Alternatives
Alternative insertion heuristics add e.g. B. in each case the next (cheapest) node ( nearest insertion heuristic , NEARIN ) or a node selected with a uniformly distributing random number generator ( RANDIN ; from "random insertion").