The examples of state space searching described previously have all been tailored to a particular problem — the algorithms have been general, but the implementation has included type signatures specific to the problem, e.g.:
:- type block —> a; b; c. :- type stack == list(block). :- type situation == list(stack). :- type solution == list(situation). :- pred solve(situation::in, solution::out) [...]
One disadvantage of the depth first search with iterative deepening is that it regenerates all the search paths from the start node every iteration. A true breadth first search, as described by Bratko on pages 250-252 doesn’t need to do that — it can start with a short search path (just the start node in [...]
Our last algorithm gave us a result much longer than the shortest possible. We can improve that by generating first all paths of length one, then two and so on, until we find one which reaches a goal state.
Bratko describes this on pages 248 and 249.
This version arrives at the optimal solution:
[[[c, a, b], [], [...]
Do you suffer from Hindsight bias?
This is not one of those irritating quizzes which leave you thinking “But they didn’t ask the right questions!”, just a simple demonstration of hindsight bias.
The algorithm implemented in my previous post pays no attention to the nodes in the search space already visited, so if the situation [[c,a,b],[],[]] is used as the starting point an infinite recursion will result, as the successor function starts to traverse a cycle in the state space graph before it finds a goal node.
On [...]
I’m working through Bratko’s “Prolog Programming for Artificial Intelligence” rewriting the examples in Mercury.This series of posts will be my notes on the changes I needed to make to make these programs work.Page 243-244, defining successor states for stacks of blocks and performing a depth first search. Note that it’s a naive depth first search [...]
I’ve been programming in Java for the past 8 years. While I enjoy Java I think it’s important to keep your mind flexible and open by learning new languages where you have to think in different ways.About a year ago I decided to learn Haskell, which led on to an interest in CAL, a functional [...]