File Heuristics.h

↰ Parent directory (ADS/intractable)

The heuristics of section 19.4 and of the exercises 19.13 and 19.16 to 19.19: feasible solutions, neither optimal nor approximate, greedy or by local search.

Definition (ADS/intractable/Heuristics.h)

Detailed Description

  • greedyTsp(): the edges by increasing weight, each added if its ends have fewer than two edges and are in different components of an MFSET, until a Hamiltonian chain, closed by the edge of its two ends, :math:` O( n^2 log n ) `;

  • minMaxGreedy() for the BISEZIONE: from a node in :math:` V_0 ` and one in :math:` V_1 , a node added to :math: V_0 ` and then one to :math:` V_1 `, the one with fewest edges to the other side and, among those, most edges to its own; the counts are kept by the structure with buckets of exercise 19.17 [see Buckets];

  • twoOpt(): the local search on the neighbourhood :math:` I_2( pi ) , the circuits made of :math: pi ` by replacing two edges that do not touch with the two that close it again, :math:` n ( n - 1 ) / 2 - n ` of them; kOptNeighbours() counts :math:` I_k( pi ) ` (exercise 19.15);

  • partitionLocalSearch(): the PARTIZIONE that minimizes the difference of the sums, moving an element or swapping two (exercise 19.16);

  • greedySuperstring(): the greedy of greedyTsp() on the graph of the overlaps, an oriented path (exercise 19.13);

  • starAlignment(): the multiple alignment against the string with the best sum of the global scores (exercise 19.18);

  • dsatur(): the coloring by saturation degree (exercise 19.19).

The contracts [see File Contract.h]: the distances are square and symmetric, the graphs unoriented, the circuits permutations; each heuristic checks that its result is feasible, not that it is good, and the structure with buckets keeps its invariant at level 3. The operations are defined in Heuristics.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 19.4 and exercises 19.13-19.19, https://algoritmicamente.it/materiali/libro/capitoli/cap19.pdf

    1. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell System Technical Journal 49(2), 291-307, 1970, doi:10.1002/j.1538-7305.1970.tb01770.x

  1. Lin, Computer solutions of the traveling salesman problem, Bell System Technical Journal 44(10), 2245-2269, 1965, doi:10.1002/j.1538-7305.1965.tb04146.x

  1. Gusfield, Efficient methods for multiple sequence alignment with guaranteed error bounds, Bulletin of Mathematical Biology 55(1), 141-154, 1993, doi:10.1007/BF02460299

  1. Brelaz, New methods to color the vertices of a graph, Communications of the ACM 22(4), 251-256, 1979, doi:10.1145/359094.359101

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions