| dbo:abstract
|
- In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers. Jump point search preserves A*'s optimality, while potentially reducing its running time by an order of magnitude. (en)
- Le terme anglais : Jump Point Search (JPS, littéralement « Recherche du point par saut ») un algorithme de recherche de chemin. C'est une variante de l'algorithme A*, optimisée pour le cas des grilles à coût uniforme. L'évolution, JPS+, réduit les symétries dans la procédure de recherche, en supprimant des parties non nécessaire du graphe d'après une de leurs recherches de 2011. Si cette technique est avant tout utilisée pour l'intelligence artificielle, en particulier dans les jeux vidéo, d'autres auteurs ont proposé de les utiliser pour la construction des immeubles de grande hauteur, afin d'en améliorer la productivité. (fr)
- En informática, el algoritmo de búsqueda de punto de salto (Jump Point Search) es una optimización del algoritmo A* para redes de costo uniforme. Reduce las simetrías en el proceso de búsqueda mediante la poda(del inglés pruning) del grafo, es decir, se eliminan algunos nodos con base en las suposiciones respecto a los vecinos del nodo actual, siempre y cuando las condiciones las condiciones generales impuestas a la red sean satisfechas. El resultado es un algoritmo puede realizar "saltos" largos en los trayectos lineales (horizontales, verticales y diagonales) de la red, en lugar de dar pequeños pasos de una posición a otro como sucede en A*. El algoritmo de búsqueda de punto del salto preserva la heurística óptima de A*, pero ofrece una posible reducción de su tiempo de ejecución de hasta un orden de magnitud. (es)
- В информатике Поиск точки перехода (ПТП) (англ. Jump point search (JPS)) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные скачки по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой, как это учитывает обычный A*. Поиск точки перехода сохраняет оптимальность A*, потенциально сокращая время его выполнения на порядок. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3735 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En informática, el algoritmo de búsqueda de punto de salto (Jump Point Search) es una optimización del algoritmo A* para redes de costo uniforme. Reduce las simetrías en el proceso de búsqueda mediante la poda(del inglés pruning) del grafo, es decir, se eliminan algunos nodos con base en las suposiciones respecto a los vecinos del nodo actual, siempre y cuando las condiciones las condiciones generales impuestas a la red sean satisfechas. El resultado es un algoritmo puede realizar "saltos" largos en los trayectos lineales (horizontales, verticales y diagonales) de la red, en lugar de dar pequeños pasos de una posición a otro como sucede en A*. (es)
- In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers. (en)
- Le terme anglais : Jump Point Search (JPS, littéralement « Recherche du point par saut ») un algorithme de recherche de chemin. C'est une variante de l'algorithme A*, optimisée pour le cas des grilles à coût uniforme. L'évolution, JPS+, réduit les symétries dans la procédure de recherche, en supprimant des parties non nécessaire du graphe d'après une de leurs recherches de 2011. (fr)
- В информатике Поиск точки перехода (ПТП) (англ. Jump point search (JPS)) — это оптимизация алгоритма поиска A* для сеток с равномерной стоимостью. Уменьшает симметрию в процедуре поиска за счёт сокращения графа, удаляя определённые узлы в сетке на основе предположений, которые могут быть сделаны в отношении соседей текущего узла, если выполняются определённые условия, относящиеся к сетке. В результате алгоритм может учитывать длинные скачки по прямым (горизонтальным, вертикальным и диагональным) линиям в сетке, а не небольшие шаги от одной позиции сетки к другой, как это учитывает обычный A*. (ru)
|
| rdfs:label
|
- Búsqueda de punto de salto (es)
- Jump point search (fr)
- Jump point search (en)
- Поиск точки перехода (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
