A* Search Algorithm

どうも、お久しぶりです。アメリカの中西部は今日と明日が最悪のブリザード日和で、もう外はカオス状態です。どのぐらいカオスかというと、ドアを解錠したはずのに何故か開かないと思ったら、実はドアが凍ってたとか、そのぐらいカオスです。

それはさておき、先日から散々tweetしていたように、最近AIの授業の課題で、A*探索を実装しました。あまり需要は無いかもしれませんが、何かの参考になれば幸いです。ちなみに、pythonで実装してます。「A* Searchって何ぞや？」って人はココら辺を参照してください。





以下、プログラムの具体的な説明(READMEから引用)です。
ソースコード？それをみせるなんて、とんでもない！

Description
-----------
This program implements the idea of A* algorithm
with following three heuristic functions:

- 1. Zero heuristic
- 2. Manhattan heuristic
- 3. Euclidean heuristic

In Zero heuristic, each space in a maze is equally cost,
so the next-exploring space totally depends on how spaces
are put into the queue. In this program, the spaces are
put into the queue in the way from top left to bottom right.
For example, if the program seeks the 3x3 map, it should put
as follows:

1 2 3
4 5 6
7 8 9


Manhattan heuristic calculates costs with Manhattan distance.
For example, in the following state, where the '*' is goal,
'x' is current location, and 'o' is the start, the cost
should be 4.

    * . .
    . x .
    . . o
  
In addition, if some elements in the queue has
same cost, the queue sorts them according to the sort of
Queue.PriorityQueue in Python library.

In particular, the priority queue sorts elements in the queue
by the ascend order of number x if given element's costs are
all same. Also, it sorts them by the ascend order of number y
if given element's costs and number of x are all same.


Euclidean heuristic calculates costs with Euclidean distance.
For example, in the following state, the cost should be 10.

f(x) = h(x) + g(x)
     = sqrt(3^2+4^2) + sqrt(4^2+3^2)
     = 5 + 5
     = 10

    * . . . . . . . .
    . . . . . . . . .
    . . . . . . . . .
    . . . . o . . . .
    . . . . . . . . .
    . . . . . . . . .
    . . . . . . . . x

So, using these heuristics, this program shows how A* algorithm
works step by step.



How To Run
----------
1. Get python 2.6 or higher

2. Type following command in your terminal.

  $ python main.py [options]

Options are not needed to run the program. But,
if you want to specify input files, heuristic
function, or make program display much information,
the following options will be useful.

  -h, --help          
show this help message and exit

  -f FILE, --file=FILE
choose a formatted text file for creating a maze. This program uses 'mazes/sample' by default.

  -H HEURISTICS      
choose a heuristic function for A* algorithm from 'zero', 'manhattan', 'euclidean' (or it's abbreviations: 'z', 'm', and 'e'). This option sets'zero' by default.

  -v, --verbose      
display information verbosely.

  -d, --diagonal      
switch to the program that allows diagonal travel for a cost of 3, and horizontal/vertical motion costs 2.

Get Latest Code

---------------

If you would like to see/run the latest code,

type following command to clone it with Git.

  $ git clone git://github.com/yasulab/a-star-algorithm.git

Or, visit the following repository.

  https://github.com/yasulab/a-star-algorithm

To clone the code, you need to install Git.

   Git - Fast Version Control System

   http://git-scm.com/

Tweet