3 ms·
About the C++ implementation, instead of BFS, you most likely want to use Uniform search. In general; search algorithms like BFS, DFS, Uniform, A* and variants
by PartiallyTyped 2y ago
About the C++ implementation, instead of BFS, you most likely want to use Uniform search.
In general; search algorithms like BFS, DFS, Uniform, A* and variants have the following structure:
do
current_state, cost <- container.pop()
container <- container.update(expand(current_state))
while current_state != goal
where container is a datastructure, and this is the key difference. DFS simply prepends all nodes, so every expansion just goes deeper, we use a stack. BFS simply appends, it's a queue (an expensive one too!), uniform uses a priority queue based on the cost. This allows you to blend actions of variable cost, and still reach minimal cost nodes. A* simply augments this with a heuristic when sorting.