Loading ...
Sorry, an error occurred while loading the content.

Pathing

Expand Messages
  • James Clemence
    I ve been looking through the python code for the search algorithms. I must acknowledge that I am pretty new to python, so apologies for basic mistakes. Having
    Message 1 of 1 , May 2, 2009
    View Source
    • 0 Attachment
      I've been looking through the python code for the search algorithms. I must acknowledge that I am pretty new to python, so apologies for basic mistakes. Having dragged the various needed classes and subclasses etc. from the original setup, I'm left with:

      #!/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

    Your message has been successfully submitted and would be delivered to recipients shortly.