Algorithm 版 (精华区)

发信人: sino (茶水), 信区: Algorithm
标  题: A* algorithm tutorial 
发信站: 哈工大紫丁香 (2002年08月29日00:50:56 星期四), 站内信件

发信人: jamguo (卜卜熊的耙耙兔), 信区: Algorithm
标  题: A* algorithm tutorial
发信站: 日月光华 (2002年08月03日07:53:29 星期六), 站内信件

A* algorithm tutorial

Author : Justin Heyes-Jones BSc

Introduction
This document contains a description of the AI algorithm known as A*, and tw
o example programs showing the kind of problems it can solve.
Please note that this tutorial does not assume you will use any particular l
anguage, but you must be able to program fairly competently to make use of t
his information. I can't give individual advice on C or C++ programming but
I'm happy to answer questions specifically about the A*.
Book recommendations. "Artificial Intelligence" by Elaine Rich, Kevin Knight
. This book is a very clear and useful introduction to many AI topics. Altho
ugh the book does not cover in depth new areas of AI research such as Geneti
c Algorithms or Neural Networks, it is ideal for classical AI topics such as
 knowledge representation and search.
I've included two example programs to which show the search in action and en
able you, by example, to see the diversity of problems which can be solved u
sing this algorithm.
State space search
Almost any problem can be solved (given infinite resources) by using a searc
h program. You have to find a way to describe the problem in terms of a set
of states, and rules you can apply to get between those states. Imagine the
state space as being a tree with the start of your problem as the root, and
expanding downwards branching at each point depending on how many rules you
can apply at each point.
To solve a problem described like this you just find the first goal state in
 this tree and make a path back up to the start.
The problem is that even quite simple problems create huge trees for you to
search. The A* algorithm requires help to search the tree in the most effici
ent way. You provide it with a heuristic. This returns an evaluation of how
good each state is, so that the search can go down the most promising routes
 first.
8 Puzzle
A good example of a search problem is the 8 puzzle. This is a simple sliding
 tile puzzle on a 3*3 grid where one tile is missing and you can move the ot
her tiles into the gap until you get the puzzle into the goal position.
Although not exactly a real life problem, or even the kind of problem your v
ideo game enemies are likely to need to do, it is a great example of how to
represent the states and rules for the purpose of example. It is also quite
hard to solve. There are 362,880 different states that the puzzle can be in,
 and to find a solution the search has to find a route through them.
The 8 puzzle game state is as simple as representing a list of the 9 squares
 and what's in them. Here are two states for example; the last one is the GO
AL state, at which point we've found the solution. The first is a jumbled up
 example that you may start from.
A start state [ C, E, H, D, G, F, B, A, SPACE ]
Goal state [ A, B, C, H, SPACE, D, G, F, E ]
The rules that you can apply to the puzzle are also simple. If there is a bl
ank tile above, below, to the left or to the right of a given tile, then you
 can move that tile into the space. To solve the puzzle you need to find the
 path from the start state, through the "OR graph" as the tree is known, dow
n to the GOAL state. We've reduced the abstract problem of how to do a puzzl
e to a simple search.
What makes the problem useful from an academic point of view is that it is h
ard to write a good heuristic function. The heuristic I used here is to add
the distances together that each tile is from where it should be. Then, sinc
e the tiles are clockwise around the centre in the goal state, tiles get 2 p
oints added to the heuristic (low is good in heuristic terms) if they are no
t followed by the tile they should be followed by in a clockwise direction.
Although usually effective this does not work for every arrangement. The exa
mple program puzzle.zip (Win95 DirectX only) shows this particular problem b
eing solved using the algorithm. The puzzle is solved, then the program walk
s through the solution on screen for you. When it's done you can mess it up
and watch it solve the puzzle from the new position. The program shows how m
any states it has evaluated giving some idea of the size of the search space
 for even such a simple puzzle.
Map route finding
The most common use for A* in games is pathfinding. For clarity the example
program is pretty simple but should show you the basic principles of using A
* to move your enemies intelligently around objects and mazes. Each state is
 simply where you are, stored as say a grid co-ordinate. The rules that you
can apply to each state are similar to the 8-puzzle. At each point you can m
ove up to 4 directions depending on whether you're at the edge of the map an
d whether walls block your path.
Implementing A*
The idea is to search the state space and find the shortest route to the goa
l state. I'll refer to the demo program through-out and include bits of code
 where appropriate.
During the search we need to keep track of two lists of states (referred to
as nodes as well from now on, as they are nodes in a tree). The first list i
s the OPEN list. This stores nodes which we have generated by using the rule
s from an existing node, but we don't yet know where they lead to.
The second list is nodes that we have generated and we have also explored wh
ere they go.
Each state is stored along with some extra data required to help us in our s
earch. The first thing that is required is a parent pointer. We need to know
 how we got to this node, as the end result of finding the GOAL state will b
e to generate a path back to the start. Tracking which node parented this no
de allows to do this.
The node also has three ratings used during the search which are the cost of
 the node, the heuristic estimate of this node and 'f' which is the total of
 the other two.
The cost of a node is easy to work out. Each move can usually be assigned a
cost. In the example program on a simple grid, the cost is always one, but s
ince we want to know the cost of the path all the way from the start to this
 node, when we generate a node we add its cost to the cost of its parent.
The heuristic estimate can be much more complexas we have seen. We can guess
 how good the node is by how near it is to the GOAL. This works well on the
tiled maze. In practice though the more help you give the algorithm the bett
er. For example, if you know that all your enemies are going to go through a
 door on the map to get into a certain area, then the heuristic would need t
o support that.
In the case of my grid I'm using the x and y difference between the node and
 the GOAL as a heuristic.
Finally the 'f' rating of a node, which represents how good it is in terms o
f how much it cost to get there and how near to the goal we are, is used thr
oughout the search to always follow the most promising path.
Here's the "Pseudo C" for the search as I implemented it.
bool AStarSearch()
{
  // priority queues are explained in the next section
  priorityqueue OPEN
  list CLOSED
  NODE node
  node.application_stuff = (start conditions of application specific stuff)
  node.cost = 0;
  node.heuristic = GetNodeHeuristic( node )
  node.f = node.cost + node.heuristic
  node.parent = null
  push node on OPEN
  // this is the body of the search
  while OPEN is not empty
  {
    node = Pop the best node from OPEN
     // ie: take the node off the open list
    if node is a goal node
    {
      construct path  (by following the parent pointers)
      return success
    }
    // otherwise we need to find what nodes can be generated from this node
    NodePushSuccessors( OPEN, CLOSED, node ); // see below
    push node onto CLOSED list // as we have now examined this node
  }
  // if we got here we emptied the OPEN list and found no GOAL states
  // the search failed
  return FALSE
}
// Create the successors for the given node and add them to the open or clos
ed
// lists as required
void NodePushSuccessors( priorityqueue OPEN, list CLOSED, parent_node )
{
  // This is where you apply each valid rule to the node we're checking out
  // In the case of a pathfinder, for example, a rule is a direction of move
ment
  for each rule we can apply create the successor new_node
  {
    new_node.cost = (application specific cost of this node) + parent_node.c
ost
    // you need to write this function for your application
    // usually the toughest part of implementing the astar.
    new_node.heuristic = GetNodeHeuristic( new_node )
    new_node.f = new_node.cost + new_node.heuristic
    if the new_node is on CLOSED but the node on CLOSED has a lower 'f'
    {
      break
    }
    if the new_node is on OPEN but the node on OPEN has a lower 'f'
    {
      break
    }
    remove new_node from the OPEN list if it is on it
    remove new_node from the CLOSED list if it is on it
    push new_node on to the OPEN list
  }
}Simple as that. If you run the demo you can move the pacman about with the
cursor keys and watch the generated path change. If you hold down the Ctrl k
ey you can move the target cherries around with the same cursor keys.
The best way to really understand the algorithm is to watch it working. Run
the demo with the command line argument 'showsearch' and it will slowly step
 through a search, and show squares that are on the OPEN list with O, and sq
uares on the CLOSED list as C.
Most A* implementations I've seen on the web use a simple linked list to do
the OPEN list of nodes. This is a bad idea because you need to retrieve the
lowest 'f' valued item, and doing that in an un-ordered list is slow. The ne
xt section will describe the way I implemented the Priority Queue data struc
ture which is used instead. A priority queue is a neat algorithm based on a
heap, which is perfect for our purposes.
Another important issue is the data structure and algorithm you select for t
he CLOSED list. As pointed out by Aneel Nazareth, a hash table is very usefu
l for this purpose. When I next spend some time on this tutorial I will impl
ement the CLOSED list in this way and provide more of the source code for th
e project.
Thanks to Steve Rabin for pointing out an error in my pseudo code which may
have caused problems in implenetation. I'd forgotten to point out that in th
e end of NodePushSuccessors you must not add the new_node that you've create
d to the OPEN list, if it is already on it. Don't worry the algorithm as sta
ted should work fine now.
Priority Queues and Heaps
References? I got this info on heaps and in particular the stuff on using th
em from "Dr Dobb's Essential Books on Algorithms and Data Structures" which
should be in every programmers libarary as it iss extremely useful. The Heap
 and PQueue stuff is the whole of Chapter 9 in the book "Data structures fro
m arrays to Priority Queues". I've included my own source for the PQueue alg
orithm pqueue.cpp, because it's reasonably short, and I'll describe in this
section briefly how the code works. I recommend you read up the formal theor
y somewhere but the provided code should explain them pretty well.
A heap is a 'leftist-tree'. The heap always grows like this ...
A    add a node      A       add another  A  and another  A
                    B                    B C             B C
                                                        D
If you remove nodes you must maintain this structure. Another thing that mak
es them cool for the priority queue is that they are sorted from top to bott
om. If you sort them so that the top item has the lowest value then they are
 perfect for the A* algorithm which sorts on lowest f values.
A useful thing about this data structure is that if we know how big our open
 list is going to get we can store the queue as an array. The array represen
ts the tree. We leave element 0 blank because then we have the useful proper
ty that any nodes children are at the array of the index parent *2 and *2+1.

In the same way a nodes parent is at the index given by the nodes array inde
x /2;
The push and pop functions in the source files add and take away nodes from
the tree making sure that the tree is still leftist (all the layers above th
e bottom layer are filled and the bottom layer is filled left to right), and
 making sure that from top to bottom the nodes are sorted in descending orde
r. You provide an application specific routine to return the rating of a nod
e.
Linked lists
I won't go into detail here. The code is here if you want a look, list.c ,bu
t otherwise, linked lists are pretty simple. Your node has a next pointer to
 the node following it, and my list structure maintains a head (start of lis
t) and a tail (end of list).
Copyright 1998 Justin Heyes-Jones
All rights Reserved.
Linking to this site is welcome and encouraged, but reproduction in whole or
 in part either on the WWW or other media is prohibited under appropriate co
pyright laws. Please ask for permission first.
To the maximum extent permitted by law, Justin Heyes-Jones disclaims all war
ranties regarding this software, express or implied, including but not limit
ed to warranties of merchantability and fitness for a particular purpose. In
 no event shall Justin Heyes-Jones be liable for consequential, special, inc
idental or indirect damages arising out of the use or inability to use this
software even if Justin Heyes-Jones is aware of the possibility of such dama
ges or a known defect.
By using this software and information, you are agreeing to the above terms.


--
数分，
    我恨你一万年！……

--
    把时髦的技术挂在嘴边

             还不如把过时的技术记在心里

     -- Kingofark's 50 points of view about learning C++

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]