#!/usr/bin/python

from __future__ import generators

import math

import random

import sys

import time

import bisect

import string

import sets

infinity = 1.0e400

class Problem:

"""The abstract class for a formal problem. You should subclass this and

implement the method successor, and possibly __init__, goal_test, and

path_cost. Then you will create instances of your subclass and solve them

with the various search functions."""

def __init__(self, initial, goal=None):

"""The constructor specifies the initial state, and possibly a goal

state, if there is a unique goal. Your subclass's constructor can add

other arguments."""

self.initial = initial; self.goal = goal

def successor(self, state):

"""Given a state, return a sequence of (action, state) pairs reachable

from this state. If there are many successors, consider an iterator

that yields the successors one at a time, rather than building them

all at once. Iterators will work fine within the framework."""

abstract

def goal_test(self, state):

"""Return True if the state is a goal. The default method compares the

state to self.goal, as specified in the constructor. Implement this

method if checking against a single self.goal is not enough."""

return state == self.goal

def path_cost(self, c, state1, action, state2):

"""Return the cost of a solution path that arrives at state2 from

state1 via action, assuming cost c to get up to state1. If the problem

is such that the path doesn't matter, this function will only look at

state2. If the path does matter, it will consider c and maybe state1

and action. The default method costs 1 for every step in the path."""

return c + 1

def value(self):

"""For optimization problems, each state has a value. Hill-climbing

and related algorithms try to maximize this value."""

abstract

class Node:

"""A node in a search tree. Contains a pointer to the parent (the node

that this is a successor of) and to the actual state for this node. Note

that if a state is arrived at by two paths, then there are two nodes with

the same state. Also includes the action that got us to this state, and

the total path_cost (also known as g) to reach the node. Other functions

may add an f and h value; see best_first_graph_search and astar_search for

an explanation of how the f and h values are handled. You will not need to

subclass this class."""

def __init__(self, state, parent=None, action=None, path_cost=0):

"Create a search tree Node, derived from a parent by an action."

update(self, state=state, parent=parent, action=action,

path_cost=path_cost, depth=0)

if parent:

self.depth = parent.depth + 1

def __repr__(self):

return "<Node %s>" % (self.state,)

def path(self):

"Create a list of nodes from the root to this node."

x, result = self, [self]

while x.parent:

result.append(x.parent)

x = x.parent

return result

def expand(self, problem):

"Return a list of nodes reachable from this node. [Fig. 3.8]"

return [Node(next, self, act,

problem.path_cost(self.path_cost, self.state, act, next))

for (act, next) in problem.successor(self.state)]

class Graph:

"""A graph connects nodes (verticies) by edges (links). Each edge can also

have a length associated with it. The constructor call is something like:

g = Graph({'A': {'B': 1, 'C': 2})

this makes a graph with 3 nodes, A, B, and C, with an edge of length 1 from

A to B, and an edge of length 2 from A to C. You can also do:

g = Graph({'A': {'B': 1, 'C': 2}, directed=False)

This makes an undirected graph, so inverse links are also added. The graph

stays undirected; if you add more links with g.connect('B', 'C', 3), then

inverse link is also added. You can use g.nodes() to get a list of nodes,

g.get('A') to get a dict of links out of A, and g.get('A', 'B') to get the

length of the link from A to B. 'Lengths' can actually be any object at

all, and nodes can be any hashable object."""

def __init__(self, dict=None, directed=True):

self.dict = dict or {}

self.directed = directed

if not directed: self.make_undirected()

def make_undirected(self):

"Make a digraph into an undirected graph by adding symmetric edges."

for a in self.dict.keys():

for (b, distance) in self.dict[a].items():

self.connect1(b, a, distance)

def connect(self, A, B, distance=1):

"""Add a link from A and B of given distance, and also add the inverse

link if the graph is undirected."""

self.connect1(A, B, distance)

if not self.directed: self.connect1(B, A, distance)

def connect1(self, A, B, distance):

"Add a link from A to B of given distance, in one direction only."

self.dict.setdefault(A,{})[B] = distance

def get(self, a, b=None):

"""Return a link distance or a dict of {node: distance} entries.

.get(a,b) returns the distance or None;

.get(a) returns a dict of {node: distance} entries, possibly {}."""

links = self.dict.setdefault(a, {})

if b is None: return links

else: return links.get(b)

def nodes(self):

"Return a list of nodes in the graph."

return self.dict.keys()

class GraphProblem(Problem):

"The problem of searching a graph from one node to another."

def __init__(self, initial, goal, graph):

Problem.__init__(self, initial, goal)

self.graph = graph

def successor(self, A):

"Return a list of (action, result) pairs."

return [(B, B) for B in self.graph.get(A).keys()]

def path_cost(self, cost_so_far, A, action, B):

return cost_so_far + (self.graph.get(A,B) or infinity)

def h(self, node):

"h function is straight-line distance from a node's state to goal."

locs = getattr(self.graph, 'locations', None)

if locs:

return int(distance(locs[node.state], locs[self.goal]))

else:

return infinity

class Queue:

"""Queue is an abstract class/interface. There are three types:

Stack(): A Last In First Out Queue.

FIFOQueue(): A First In First Out Queue.

PriorityQueue(lt): Queue where items are sorted by lt, (default <).

Each type supports the following methods and functions:

q.append(item) -- add an item to the queue

q.extend(items) -- equivalent to: for item in items: q.append(item)

q.pop() -- return the top item from the queue

len(q) -- number of items in q (also q.__len())

Note that isinstance(Stack(), Queue) is false, because we implement stacks

as lists. If Python ever gets interfaces, Queue will be an interface."""

def __init__(self):

abstract

def extend(self, items):

for item in items: self.append(item)

class PriorityQueue(Queue):

"""A queue in which the minimum (or maximum) element (as determined by f and

order) is returned first. If order is min, the item with minimum f(x) is

returned first; if order is max, then it is the item with maximum f(x)."""

def __init__(self, order=min, f=lambda x: x):

update(self, A=[], order=order, f=f)

def append(self, item):

bisect.insort(self.A, (self.f(item), item))

def __len__(self):

return len(self.A)

def pop(self):

if self.order == min:

return self.A.pop(0)[1]

else:

return self.A.pop()[1]

def update(x, **entries):

"""Update a dict; or an object with slots; according to entries.

>>> update({'a': 1}, a=10, b=20)

{'a': 10, 'b': 20}

>>> update(Struct(a=1), a=10, b=20)

Struct(a=10, b=20)

"""

if isinstance(x, dict):

x.update(entries)

else:

x.__dict__.update(entries)

return x

def memoize(fn, slot=None):

"""Memoize fn: make it remember the computed value for any argument list.

If slot is specified, store result in that slot of first argument.

If slot is false, store results in a dictionary."""

if slot:

def memoized_fn(obj, *args):

if hasattr(obj, slot):

return getattr(obj, slot)

else:

val = fn(obj, *args)

setattr(obj, slot, val)

return val

else:

def memoized_fn(*args):

if not memoized_fn.cache.has_key(args):

memoized_fn.cache[args] = fn(*args)

return memoized_fn.cache[args]

memoized_fn.cache = {}

return memoized_fn

def graph_search(problem, fringe):

"""Search through the successors of a problem to find a goal.

The argument fringe should be an empty queue.

If two paths reach a state, only use the best one. [Fig. 3.18]"""

closed = {}

fringe.append(Node(problem.initial))

while fringe:

node = fringe.pop()

if problem.goal_test(node.state):

print Node.path

return node

if node.state not in closed:

closed[node.state] = True

fringe.extend(node.expand(problem))

print fringe.len()

return None

def best_first_graph_search(problem, f):

"""Search the nodes with the lowest f scores first.

You specify the function f(node) that you want to minimize; for example,

if f is a heuristic estimate to the goal, then we have greedy best

first search; if f is node.depth then we have depth-first search.

There is a subtlety: the line "f = memoize(f, 'f')" means that the f

values will be cached on the nodes as they are computed. So after doing

a best first search you can examine the f values of the path returned."""

f = memoize(f, 'f')

return graph_search(problem, PriorityQueue(min, f))

def astar_search(problem, h=None):

"""A* search is best-first graph search with f(n) = g(n)+h(n).

You need to specify the h function when you call astar_search.

Uses the pathmax trick: f(n) = max(f(n), g(n)+h(n))."""

h = h or problem.h

def f(n):

return max(getattr(n, 'f', -infinity), n.path_cost + h(n))

return best_first_graph_search(problem, f)

g = Graph({'A1': {'A2': 1, 'B1': 1}}, directed=False)

g.connect('A2','A3',1)

issue = GraphProblem('A1','A3',g)

astar_search(issue)

Which appears to work, and exits without any errors. However - 1/ does this solve the path? 2/ How can I get it to output the final path? I've tried with print statements within the code, and have tried adding an 'overall path' variable list, but can't seem to get it functional.

Any help would be much appreciated sorry if I've missed the obvious etc - still pretty new to this lark!

Cheers,

J