Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Fringe_search> ?p ?o }
Showing triples 1 to 35 of
35
with 100 triples per page.
- Fringe_search abstract "In computer science, fringe search is a recent graph search algorithm that finds the least-cost path from a given initial node to one goal node.In essence, fringe search is a middle ground between A* and the iterative deepening A* variant (IDA*). If g(x) is the cost of the search path from the first node to the current, and h(x) is the heuristic estimate of the cost from the current node to the goal, then ƒ(x) = g(x) + h(x), and h* is the actual path cost to the goal. Consider IDA*, which does a recursive left-to-right depth-first search from the root node, stopping the recursion once the goal has been found or the nodes have reached a maximum value ƒ. If no goal is found in the first threshold ƒ, the threshold is then increased and the algorithm searches again. I.E. It iterates on the threshold. There are three major inefficiencies with IDA*. First, IDA* will repeat states when there are multiple (sometimes non-optimal) paths to a goal node - this is often solved by keeping a cache of visited states. IDA* thus altered is denoted as memory-enhanced IDA* (ME-IDA*), since it uses some storage. Furthermore, IDA* repeats all previous operations in a search when it iterates in a new threshold, which is necessary to operate with no storage. By storing the leaf nodes of a previous iteration and using them as the starting position of the next, IDA*'s efficiency is significantly improved (otherwise, in the last iteration it would always have to visit every node in the tree). Fringe search implements these improvements on IDA* by making use of a data structure that is more or less two lists to iterate over the frontier or fringe of the search tree. One list now, stores the current iteration, and the other list later stores the immediate next iteration. So from the root node of the search tree, now will be the root and later will be empty. Then the algorithm takes one of two actions: If ƒ(head) is greater than the current threshold, remove head from now and append it to the end of later; i.e. save head for the next iteration. Otherwise, if ƒ(head) is less than or equal to the threshold, expand head and discard head, consider its children, adding them to the beginning of now. At the end of an iteration, the threshold is increased, the later list becomes the now list, and later is emptied. An important difference here between fringe and A* is that the contents of the lists in fringe do not necessarily have to be sorted - a significant gain over A*, which requires the often expensive maintenance of order in its open list. Unlike A*, however, fringe will have to visit the same nodes repeatedly, but the cost for each such visit is constant compared to the worst-case logarithmic time of sorting the list in A*.".
- Fringe_search wikiPageExternalLink IJCAI07-385.pdf.
- Fringe_search wikiPageExternalLink cig2005.pdf.
- Fringe_search wikiPageExternalLink fringesearch.
- Fringe_search wikiPageID "21595579".
- Fringe_search wikiPageLength "5755".
- Fringe_search wikiPageOutDegree "10".
- Fringe_search wikiPageRevisionID "668507860".
- Fringe_search wikiPageWikiLink A*_search_algorithm.
- Fringe_search wikiPageWikiLink Category:Graph_algorithms.
- Fringe_search wikiPageWikiLink Computer_science.
- Fringe_search wikiPageWikiLink Depth-first_search.
- Fringe_search wikiPageWikiLink Goal_node_(computer_science).
- Fringe_search wikiPageWikiLink Graph_traversal.
- Fringe_search wikiPageWikiLink Heuristic_(computer_science).
- Fringe_search wikiPageWikiLink List_(abstract_data_type).
- Fringe_search wikiPageWikiLink Recursion_(computer_science).
- Fringe_search wikiPageWikiLink Vertex_(graph_theory).
- Fringe_search wikiPageWikiLinkText "Fringe".
- Fringe_search wikiPageUsesTemplate Template:Graph_search_algorithm.
- Fringe_search wikiPageUsesTemplate Template:Inline_citations.
- Fringe_search subject Category:Graph_algorithms.
- Fringe_search hypernym Algorithm.
- Fringe_search type Software.
- Fringe_search type Algorithm.
- Fringe_search comment "In computer science, fringe search is a recent graph search algorithm that finds the least-cost path from a given initial node to one goal node.In essence, fringe search is a middle ground between A* and the iterative deepening A* variant (IDA*). If g(x) is the cost of the search path from the first node to the current, and h(x) is the heuristic estimate of the cost from the current node to the goal, then ƒ(x) = g(x) + h(x), and h* is the actual path cost to the goal.".
- Fringe_search label "Fringe search".
- Fringe_search sameAs Q5504599.
- Fringe_search sameAs Búsqueda_por_Franjas.
- Fringe_search sameAs جستجو_فرینگ.
- Fringe_search sameAs m.05mxmkt.
- Fringe_search sameAs Претрага_ресицама.
- Fringe_search sameAs Q5504599.
- Fringe_search wasDerivedFrom Fringe_search?oldid=668507860.
- Fringe_search isPrimaryTopicOf Fringe_search.