Monthly Archives: August 2007

A Generic ’solve’ Predicate

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) [...]

Breadth First Search

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 [...]

Depth First Search in Mercury—with Iterative Deepening

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], [], [...]

Link of the Day: Test your Hindsight Bias

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.

Depth First Search in Mercury—with Cycle Detection

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 [...]

Depth First Search in Mercury

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 [...]

Learning New Languages

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 [...]