SSS* - Algorithm


There is a priority queue OPEN that stores states or the nodes, where - node identificator (Dewey's notation is used to identify nodes, is a root), - state of the node (L - the node is live, which means it's not solved yet and S - the node is solved), - value of the solved node. Items in OPEN queue are sorted descending by their value. If more than one node has the same value of, a node left-most in the tree is chosen.

OPEN := { (e,L,inf) } while (true) // repeat until stopped pop an element p=(J,s,h) from the head of the OPEN queue if J == e and s == S STOP the algorithm and return h as a result else apply Gamma operator for p

operator for is defined in the following way:

if s == L if J is a terminal node (1.) add (J,S,min(h,value(J))) to OPEN else if J is a MIN node (2.) add (J.1,L,h) to OPEN else (3.) for j=1..number_of_children(J) add (J.j,L,h) to OPEN else if J is a MIN node (4.) add (parent(J),S,h) to OPEN remove from OPEN all the states that are associated with the children of parent(J) else if is_last_child(J) // if J is the last child of parent(J) (5.) add (parent(J),S,h) to OPEN else (6.) add (parent(J).(k+1),L,h) to OPEN // add state associated with the next child of parent(J) to OPEN

Read more about this topic:  SSS*

Other articles related to "algorithm":

Algorithm - History: Development of The Notion of "algorithm" - History After 1950
... further refinement of the definition of "algorithm", and activity is on-going because of issues surrounding, in particular, foundations of mathematics (especially the Church–Turing thesis) and ... For more, see Algorithm characterizations ...
Timeline Of Algorithms - 1960s
... Hoare 1962 - Ford–Fulkerson algorithm developed by L ... Fulkerson 1962 - Bresenham's line algorithm developed by Jack E ... Fedorenko 1965 - Cooley–Tukey algorithm rediscovered by James Cooley and John Tukey 1965 - Levenshtein distance developed by Vladimir Levenshtein 1965 - Cocke–Younger–Kasami (CYK ...
Barcode Reader - New Algorithms For Barcode Decoding - Symbology Decoding Algorithm
... The Symbology Decoding Algorithm for barcode scanners is the first symbology-based algorithm for decoding ... the entire image to detect transitions in the signal, whereas the traditional algorithm relies on the maxima and minima ... The Symbology Decoding Algorithm for Bar Code Scanners exhibited high resilience to blur and noise when tested on 1D Universal Product Codes ...
Tomasulo Algorithm
... The Tomasulo algorithm is a hardware algorithm developed in 1967 by Robert Tomasulo from IBM ... This algorithm differs from scoreboarding in that it utilizes register renaming ... The Tomasulo algorithm also uses a common data bus (CDB) on which computed values are broadcast to all the reservation stations that may need it ...
Markov Chain Monte Carlo - Random Walk Algorithms
... random walk MCMC methods Metropolis–Hastings algorithm Generates a random walk using a proposal density and a method for rejecting proposed moves ... Multiple-try Metropolis A variation of the Metropolis–Hastings algorithm that allows multiple trials at each point ... This allows the algorithm to generally take larger steps at each iteration, which helps combat problems intrinsic to large dimensional problems ...