PythonでA*(A-Star)アルゴリズムによる迷路探索

人材獲得なんちゃらとかいう少し前に流行った問題を解いてみる。時代おくれの人間。
といっても書いたコードはPythonでA*(A-Star)アルゴリズムに多くを負っている。

実践

処理手順や変数名および関数名はwikipedia:A*に準拠している。一応。評価関数を無駄に細かく腑分けしている。

ひとに説明する勇気がない。

結果

上：元の迷路(SがスタートでGがゴール)。下：最短経路を$で埋めた図。

ソースコード

# -*- coding: utf-8 -*-

problem = """**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************""".split("\n")

problem = map(list, problem)

class Node():
    start = None
    goal = None
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.pos = (x, y)
        self.parent_node = None
        self.h_star = abs(x - self.goal[0]) + abs(y - self.goal[1])
        self.f_star = 0

class NodeList(list):
    def find(self, n):
        l = [t for t in self if t.pos==n.pos]
        return l[0] if l != [] else None

    def remove(self,node):
        del self[self.index(node)]

def searchPoint(problem, point):
    x = y = 0
    for indexY, line in enumerate(problem):
        for indexX, char in enumerate(line):
            if char is point:
                x = indexX
                y = indexY
                break
    return (x, y)

directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]

Node.start = searchPoint(problem, 'S')
Node.goal = searchPoint(problem, 'G')
Start = Node(*Node.start)
Start.f_star = Start.h_star
Goal = Node(*Node.goal)
openList = NodeList()
closeList = NodeList()

def fPrime(n, m):
    gStar = lambda n, m: n.f_star - n.h_star
    hStar = lambda m: m.h_star
    cost = lambda n, m: (m.x - n.x) + (m.y - n.y)
    return gStar(n, m) + hStar(m) + cost(n, m)


openList.append(Start)
while openList:
    n = min(openList, key=lambda x: x.f_star)
    openList.remove(n)
    closeList.append(n)
    if n.pos == Node.goal:
        end_node = n
        break
    for direction in directions:
        m = Node(n.x + direction[0], n.y + direction[1])
        if problem[m.y][m.x] is '*':
            continue
        om = openList.find(m)
        cm = closeList.find(m)
        fp = fPrime(n, m)
        om_fp = fPrime(n, om) if om else None
        cm_fp = fPrime(n, cm) if cm else None
        if om is None and cm is None:
            m.parent_node = n
            m.f_star = fp
            openList.append(m)
        elif not om is None and om_fp < om.f_star:
            om.parent_node = n
            om.f_star = om_fp
        elif not cm is None and cm_fp < cm.f_star:
            cm.f_star = cm_fp
            closeList.remove(cm)
            openList.append(cm)

n = end_node.parent_node
while n:
    problem[n.y][n.x] = '$'
    n = n.parent_node

for p in problem:
    print "".join(p)