File Paradigms.h

↰ Parent directory (ADS/algorithm)

The general schemes of the techniques of design of algorithms, beyond the book, as functions of the parts that make a technique concrete.

Definition (ADS/algorithm/Paradigms.h)

Detailed Description

A problem is a quintuple < I , S , R , O , Q >: the instances I, the solutions S, the relation R between them, the answers O and the function Q that gives the answer of an instance. In a problem of search the answer is a solution s with < i , s > in R, or none (written :math:` bot `); in one of decision it is whether such an s exists, and it may be found with the search (the constructive method) or not; in one of optimization it is a solution that is best for a measure m with values in an ordered set, or none. A search space Z of an instance is a set of objects with a function of admissibility a and one of answer o, such that a( z ) holds if and only if o( z ) is a solution; for a problem of optimization Z must also contain an optimal solution.

  • enumerateSearch() examines Z in a total order, first(), next() and last(), and returns the answer of the first admissible object, or nothing: the enumerative method;

  • enumerateOptimize() examines all of Z and returns the answer of an admissible object of best measure, or nothing;

  • backtrack() visits the tree of the partial solutions in depth: the root is the empty one and a node at level j has a child for each way of adding the component j + 1; a node that prune() rejects is not visited, its subtree with it, and each leaf is handed to visit(), which returns true to stop;

  • greedy() builds a solution by stages, choosing at each stage the best of the values admissible there and never going back;

  • divideEtImpera() solves an instance directly if it is small, and otherwise divides it into instances of the same problem, solves them recursively and combines their solutions;

  • maximal() returns the elements of a set that are maximal for a partial order, i.e., those with no element strictly better, in :math:` O( n^2 ) `: the answers of a problem of optimization whose measure is only partially ordered.

The functions are defined in Paradigms.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapters 13-16, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/algorithm/impl/Paradigms.tpp

  • optional

  • utility

  • vector

Namespaces

Functions