Lecture
In computer science, fringe search is a graph search algorithm that finds the lowest-cost path from a given start node to a single target node.
In essence, fringe search is something of a hybrid between A* and a variant of iterative-deepening A* (IDA*).
If g ( x ) — is the cost of the search path from the first node to the current one, 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 cost of the path to the goal. Consider IDA*, which performs a recursive depth-first search from left to right starting at the root node, halting the recursion as soon as the goal is found or nodes reach the maximum value of ƒ . If the goal is not found at the first threshold of ƒ , the threshold is increased and the algorithm performs the search again. I.e., it iterates over the threshold.
IDA* has three main drawbacks. First, IDA* will repeat states when there are several (sometimes suboptimal) paths to the target node — this is often solved by keeping a cache of visited states. IDA* modified in this way is referred to as memory-enhanced IDA* (ME-IDA*), since it uses some storage. In addition, IDA* repeats all previous operations in the search when it iterates at a new threshold, which is necessary for it to work without storage. By retaining the leaf nodes of the previous iteration and using them as the starting position for the next one, the efficiency of IDA* is significantly improved (otherwise, on the last iteration it would always have to visit every node in the tree).
Fringe search implements these improvements to IDA* using a data structure that is, more or less, two lists for iterating over the fringe, or edge, of the search tree. One list, now, stores the current iteration, while another list, later, stores the next iteration. Thus, starting from the root node of the search tree, now will be the root, and later will be empty. The algorithm then performs one of two actions: if ƒ (head) is greater than the current threshold, remove head from now and add it to the end of later ; that is, save head for the next iteration. Otherwise, if ƒ (head) is less than or equal to the threshold, expand head and discard head, considering its children by adding them to the beginning of now . At the end of the iteration, the threshold is increased, the later list becomes the now list, and later is cleared.
An important difference between fringe and A* is that the contents of the lists in fringe do not need to be sorted — a significant advantage over A*, which requires the often costly maintenance of order in its open list. However, unlike A*, fringe will have to visit the same nodes repeatedly, but the cost of each such visit is constant, compared to the worst-case logarithmic time of sorting the list in A*.
An implementation of both lists in a single doubly linked list, where the nodes preceding the current node are the later part, and everything else is the current list. Using an array of preallocated list nodes for each node in the grid, access time to nodes in the list is reduced to a constant. Similarly, an array of markers allows a node search in the list to be performed in constant time. g is stored as a hash table, and a final array of markers is stored for constant-time lookup of whether a node has been visited before and whether the cache entry is valid.
init(start, goal) fringe F = s cache C[start] = (0, null) flimit = h(start) found = false while (found == false) AND (F not empty) fmin = ∞ for node in F, from left to right (g, parent) = C[node] f = g + h(node) if f > flimit fmin = min(f, fmin) continue if node == goal found = true break for child in children(node), from right to left g_child = g + cost(node, child) if C[child] != null (g_cached, parent) = C[child] if g_child >= g_cached continue if child in F remove child from F insert child in F past node C[child] = (g_child, node) remove node from F flimit = fmin if reachedgoal == true reverse_path(goal)
Reverse pseudocode.
reverse_path(node) (g, parent) = C[node] if parent != null reverse_path(parent) print node
When tested on grid environments typical of computer games, including impassable obstacles, fringe outperformed A* by approximately 10–40 percent, depending on whether tiles or octiles were used. Possible further improvements include using a data structure that is more amenable to caching.
Comments