Call
In computer science, fringe search is a 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.
If g is the cost of the search path from the first node to the current, and h is the heuristic estimate of the cost from the current node to the goal, then ƒ = g + h, 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 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* , 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.
Talk Doctor Online in Bissoy App