File Nondeterminism.h
↰ Parent directory (ADS/complexity)
The nondeterministic algorithms of section 18.2 simulated by enumeration (section 18.3).
Definition (ADS/complexity/Nondeterminism.h)
Detailed Description
A nondeterministic algorithm is a function that receives a Chooser and calls choice( k ) to pick one of k alternatives, returning true for success and false for failure; it answers YES if some sequence of choices leads to success. run() replays the algorithm on every sequence of choices, in increasing order, a depth first visit of the tree of the choices that backtracks on the last choice that still has an untried alternative, and stops at the first success; its time is the number of leaves of the tree times the time of a run, exponential in the height of the tree, while the nondeterministic algorithm takes as much as one path.
The contracts [see File Contract.h]: choice() needs k >= 1 and returns a choice of [ 0 , k ). The operations are defined in Nondeterminism.tpp.
Montresor, Algoritmi e Strutture Dati, 2025, sections 18.2 and 18.3, https://algoritmicamente.it/materiali/libro/capitoli/cap18.pdf
- Donato Meoli
Dipartimento di Informatica Universita’ di Pisa
by Donato Meoli
Includes
ADS/Contract.h(File Contract.h)ADS/complexity/impl/Nondeterminism.tppcstddefvector