I managed to implement graph search using C # using PDF .
I used 3 lists - frontier (open list), list of leaves and list of tree branches.
Frontier is the order mentioned in the PDF, it's the usual priority queue, sorted from best to worst.
The list of leaves contains only leaves sorted from worst to best, we will need it when we determine which leaf to forget. SMA forgets only leaves, not whole branches.
The list of tree branches contains fully expanded nodes whose children are in memory. We will need this to verify the intersection of states.
I used fast binary heaps for a list of borders and leaves, and a hash table for a list of tree branches.
The nodes must contain the following additional information:
Successor iterator with a position (a position is required to indicate the successors in the list). We absolutely must not reset to list our successors to zero if we forget when we go, because it is possible that we forget about the node that we just added. I use IEnumerator, int for position, and bool for the "finished" flag.
List of successors. We inevitably need this for f-cost spread up. I also keep a list of simple successors - as [blocked, forgotten, exists]. This is necessary to track forgotten and blocked nodes. (blocked - in the graph - by some node, which expanded faster)
The two Fs mentioned in the PDF, our current F and the best forgotten successor to F.
Node depth
Sorting nodes in both the border and the leaf list should be performed as follows: "if we have a" finished "enumeration flag, select the best forgotten successor F, otherwise select the current F, if it is equal, select the deepest". The list of leaves is sorted in reverse using the same condition.
The outline of the main algorithm is similar to this (similar to PDF files):
We select the best node from the border if it has a "completed" flag - we know that we will remember to reset the iterator, and we must reset the best-forgotten successor F in this case (for complex reasons).
If we don’t have this successor in the list already (maybe when we remember) - we will generate it and install it as described in PDF.
The following is the most difficult thing - we check whether a node with the same state exists in the list of branches or tree branches. If so, then I will describe what to do later. If not, we simply add the child to the border (and remove the parent from the list of sheets).
In all cases when the listing of successors ends, we make a so-called backup copy of f-costs, and if we do not have forgotten nodes (and there are some successors), we remove the current node from the border and add it to the list of tree branches.
How to forget: we select the first sheet from the list of leaves (the worst sheet), delete it from the border, delete it from the list of successor parents, update (decrease) the parent best forgotten successor F, if necessary, and if the parent is not on the border, we delete it from the list of tree branches and add it to the border, and also add to the list sheet if it is now a sheet (no longer has successors).
What to do if we generated a successor that is already on the border or tree list. First, we need to test it better - we are comparing PathCost + H (the “original” F) of these two nodes. Please note that we cannot compare F backed by F - this will not work. If this is not better, we simply block the successor state. If so, there may be a case that worse node is the root of a huge subtree (too complicated to explain). In this single case, we completely cut the subtree, and the SMA immediately forgets a bunch of nodes. After replacing the worst node with a better node, we will remove the worse node from the list of parent successors, from the list of borders, sheets, or even the list of tree branches (it could even be there!), Set the status of the successor to parent blocked for it and do not forget to check if the node is worse the parent node is now locked by all nodes - we need to set it to infinity because it has become a node terminal.
I may not have the simplest implementation, but it is the only one that works for me. I used 8 puzzles for tests - solving n-steps with a minimum of (n + 1) -memory (counting the start of a node) and checking the optimality of the solution using a regular a-star. I spent 20-30 hours trying to figure out all the details - the main problem was the complexity of the tests with an error - I have logical errors "replacement with the best node" only at 20 + steps with extensive testing of thousands of random seeds. Also, follow the priority queues - I had to reinsert the element in many cases, cause any changes in F, the best forgotten F or the "finished" flag - it changes the sort order. I ended up checking my sequence of binary heaps on each detection. And the main idea to get rid of the most difficult thing to understand the error of an infinite loop is to check that in all cases you are not decreasing F. Thus, F will continue to increase.
I am going to share a working source of implementation in a couple of weeks.