Jump point search (original) (raw)
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*.
| Property | Value |
|---|---|
| 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 | 42146944 (xsd:integer) |
| dbo:wikiPageLength | 3735 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1071050708 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Search_algorithms dbr:Online_algorithm dbr:Computer_science dbc:Game_artificial_intelligence dbc:Graph_algorithms dbr:A*_search_algorithm |
| dbp:wikiPageUsesTemplate | dbt:Graph_search_algorithm dbt:Reflist |
| dct:subject | dbc:Search_algorithms dbc:Game_artificial_intelligence dbc:Graph_algorithms |
| gold:hypernym | dbr:Optimization |
| rdf:type | dbo:Software yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| 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 | freebase:Jump point search yago-res:Jump point search wikidata:Jump point search dbpedia-es:Jump point search dbpedia-fr:Jump point search dbpedia-hu:Jump point search dbpedia-ru:Jump point search dbpedia-sr:Jump point search https://global.dbpedia.org/id/fiuW |
| prov:wasDerivedFrom | wikipedia-en:Jump_point_search?oldid=1071050708&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Jump_point_search |
| is dbo:wikiPageDisambiguates of | dbr:JPS |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Any-angle_path_planning dbr:JPS dbr:A*_search_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Jump_point_search |