| dbo:abstract
|
- IDA* (englisch iterative deepening A*) ist ein Begriff aus der Informatik. Er bezeichnet ein Verfahren zum Suchen des kürzesten Weges zwischen zwei Knoten (Graphentheorie) in einem Graphen. Der Algorithmus kombiniert die wünschenswerten Eigenschaften von Tiefensuche (geringer Speicherverbrauch)und einer Variante der Breitensuche, dem A*-Algorithmus (Steuerung der Suche durch eine Heuristik). (de)
- Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A* search algorithm. Since it is a depth-first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree. Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times. While the standard iterative deepening depth-first search uses search depth as the cutoff for each iteration, the IDA* uses the more informative , where is the cost to travel from the root to node and is a problem-specific heuristic estimate of the cost to travel from to the goal. The algorithm was first described by Richard Korf in 1985. (en)
- El método IDA* (Iterative Deepening A*) es un algoritmo de búsqueda en grafos desarrollado por Korf en 1985 de profundidad iterativa y es una modificación de DFS. Hace uso de la información heurística de que se dispone sobre el problema para decidir qué nodo expandir a continuación, y hasta dónde llegar en cada una de las iteraciones del proceso. En este algoritmo, como en cualquier algoritmo de profundización iterativa, cada iteración es una búsqueda primero en profundidad. En este caso la profundidad se basa en la información heurística y terminará no a una determinada profundidad, sino cuando se llegue a un nodo cuyo coste de la función heurística de evaluación sea mayor que el actual límite de coste de . De esta forma en cada iteración se revisan todos los nodos con un coste de menor o igual que el actual límite de coste. Además de esto se evalúan los nodos del contorno del árbol, que tienen un coste mayor que el actual límite de , para calcular el límite de que se utilizará en la siguiente iteración. Este nuevo límite será el valor mínimo de todos los valores de de los nodos del citado contorno. (es)
- Iterative deepening A* (noto anche con l'acronimo IDA*) è un algoritmo euristico proposto da nel 1985. È in grado di trovare il cammino minimo fra un nodo indicato come iniziale e ciascun membro di un insieme di "nodi soluzione" in un grafo pesato. L'algoritmo è una variante dell'iterative deepening depth-first search usata per migliorare le prestazioni di A*. Il vantaggio principale di IDA* è infatti l'uso lineare della memoria, al contrario di A* che ha bisogno, nel caso peggiore, di uno spazio esponenziale. D'altro canto, questo algoritmo usa fin troppa poca memoria, che potrebbe essere invece sfruttata per migliorare le prestazioni in termini di tempo (cfr. memoizzazione). (it)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9376 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:class
| |
| dbp:data
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- IDA* (englisch iterative deepening A*) ist ein Begriff aus der Informatik. Er bezeichnet ein Verfahren zum Suchen des kürzesten Weges zwischen zwei Knoten (Graphentheorie) in einem Graphen. Der Algorithmus kombiniert die wünschenswerten Eigenschaften von Tiefensuche (geringer Speicherverbrauch)und einer Variante der Breitensuche, dem A*-Algorithmus (Steuerung der Suche durch eine Heuristik). (de)
- El método IDA* (Iterative Deepening A*) es un algoritmo de búsqueda en grafos desarrollado por Korf en 1985 de profundidad iterativa y es una modificación de DFS. Hace uso de la información heurística de que se dispone sobre el problema para decidir qué nodo expandir a continuación, y hasta dónde llegar en cada una de las iteraciones del proceso. (es)
- Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A* search algorithm. Since it is a depth-first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree. Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times. (en)
- Iterative deepening A* (noto anche con l'acronimo IDA*) è un algoritmo euristico proposto da nel 1985. È in grado di trovare il cammino minimo fra un nodo indicato come iniziale e ciascun membro di un insieme di "nodi soluzione" in un grafo pesato. (it)
|
| rdfs:label
|
- IDA* (de)
- IDA* (es)
- Iterative deepening A* (en)
- Iterative deepening A* (it)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
