Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983. The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < p < 1. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let n be the input size, T(n) be the time complexity of the whole prune-and-search algorithm, and S(n) be the time complexity of the pruning step. Then T(n) obeys the following recurrence relation:
| Attributes | Values |
|---|
| rdfs:label
| - Prune and search (it)
- Prune and search (en)
|
| rdfs:comment
| - Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983. The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < p < 1. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let n be the input size, T(n) be the time complexity of the whole prune-and-search algorithm, and S(n) be the time complexity of the pruning step. Then T(n) obeys the following recurrence relation: (en)
- Prune and search (in italiano "sfoltisci e cerca") è un metodo per risolvere problemi di ottimizzazione ideato da nel 1983. L'idea alla base del metodo è una procedura ricorsiva, ad ogni passo della quale la taglia dell'input è ridotta (prune) di un fattore costante . Esso è dunque un algoritmo del tipo divide et impera. Sia la taglia dell'input, sarà la complessità temporale di tutto l'algoritmo e la complessità temporale dell'operazione di sfoltimento, allora obbedirà alla seguente relazione di ricorrenza: (it)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983. The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < p < 1. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let n be the input size, T(n) be the time complexity of the whole prune-and-search algorithm, and S(n) be the time complexity of the pruning step. Then T(n) obeys the following recurrence relation: This resembles the recurrence for binary search but has a larger S(n) term than the constant term of binary search. In prune and search algorithms S(n) is typically at least linear (since the whole input must be processed). With this assumption, the recurrence has the solution T(n) = O(S(n)). This can be seen either by applying the master theorem for divide-and-conquer recurrences or by observing that the times for the recursive subproblems decrease in a geometric series. In particular, Megiddo himself used this approach in his linear time algorithm for the linear programming problem when the dimension is fixed and for the minimal enclosing sphere problem for a set of points in space. (en)
- Prune and search (in italiano "sfoltisci e cerca") è un metodo per risolvere problemi di ottimizzazione ideato da nel 1983. L'idea alla base del metodo è una procedura ricorsiva, ad ogni passo della quale la taglia dell'input è ridotta (prune) di un fattore costante . Esso è dunque un algoritmo del tipo divide et impera. Sia la taglia dell'input, sarà la complessità temporale di tutto l'algoritmo e la complessità temporale dell'operazione di sfoltimento, allora obbedirà alla seguente relazione di ricorrenza: che si può provare, col metodo di Akra-Bazzi, avere soluzione , se , dove c è una costante. (it)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is known for
of | |
| is known for
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)