pythonはA*道探しアルゴリズムを実現します。
12632 ワード
A*アルゴリズムの概要
A*アルゴリズムは二つのデータ構造を維持する必要があります。OPENセットとCLOEDセットです。OPENセットは、検索済みの検出待ちノードをすべて含む。初期状態では、OPENセットには1つの要素しか含まれていません。開始ノードです。CLOSDセットは、検出されたノードを含む。初期状態はCLOED集が空です。各ノードはまた、親ノードを指すポインタを含み、追跡関係を決定する。
A＊アルゴリズムは、検索したノードごとにG＋Hの和値Fを計算する。 F=G+H G：開始ノードから現在ノードへの移動量である。開始ノードから隣接ノードへの移動量は1であると仮定すると、この値は開始点から遠くなるほど大きくなる。 H：現在のノードから対象ノードへの移動量推定値である。 もし4近傍への移動が許可されれば、マンハッタン距離を使用する。 は、8近傍への移動を許可する場合、対角線距離を使用する。 アルゴリズムは、ターゲットノードに到達するまで次のステップを繰り返します。
1は、OPENから最適ノードn（すなわち、F値が一番小さいノード）をまとめて検出する。
2ノードnをOPENから集中的に除去し、その後CLOSDセットに追加する。
3 nがターゲットノードである場合、アルゴリズムは終了する。
4そうでなければ、ノードnのすべての隣ノードn'を追加することが試みられる。隣ノードは、CLOSD集中において、検出されたことを表し、追加する必要がない。 隣ノードはOPENに集中している： 、再計算されたG値が隣のノードに保存されているG値より小さい場合、この隣のノードのG値とF値、および親ノードを更新する必要がある。 そうでなければ、操作をしません。
そうでなければ、隣接ノードをOPENセットに参加し、その親ノードがnであることを設定し、そのG値とF値を設定する。 スタートノードからターゲットノードまでが実際に接続されていない場合、スタートノードからターゲットノードに移動できない場合、アルゴリズムは、第1ステップで取得されたノードnが空であると判断し、終了することに注意する必要がある。
キーコードの紹介
基本情報を保存する地図類
地図の種類はランダムに1つの道を探すアルゴリズムの仕事の基礎の地図の情報を生成するために用います。
まずmapクラスを作成し、初期化パラメータは地図の長さと幅を設定し、地図情報を保存する二次元データmapの値を0とし、値は0として当該ノードに移動できることを示します。
OPENセットに追加されるノードを検索するごとに、イベントの位置情報（x，y）が保存されている次のノード類が作成され、算出されたG値とF値と、そのノードの親ノード（pre＿u）が格納されます。ベントリー
以下は、上のアルゴリズムの主なループで紹介されたコード実装であり、OPENセットとCLOSDセットのデータ構造は辞書を使用しており、一般的には、ノードの追加と削除の時間の複雑さはO（1）であり、遍歴時間の複雑さはO（n）であり、nは辞書の対象数である。
以下の関数はOPEN集中からF値が一番小さいノードを取得します。OPEN集会が空であればNoneに戻ります。は、上下、左、右の4近傍の移動を許可する 。は、上下、左、右、左上、右上、左下、右下の8近傍の移動を許可する 。
get MoveCost関数は、斜め移動かどうかによって消費を計算します。
地図の長さ、幅、および非移動ノードの数を調整することができる。
開始ノードおよび対象ノードの取得範囲を調整することができる。
第2の図の値が2のノードは、発見された経路を示す。
完全コード
python 3.7を使ってコンパイルします。
A*アルゴリズムは二つのデータ構造を維持する必要があります。OPENセットとCLOEDセットです。OPENセットは、検索済みの検出待ちノードをすべて含む。初期状態では、OPENセットには1つの要素しか含まれていません。開始ノードです。CLOSDセットは、検出されたノードを含む。初期状態はCLOED集が空です。各ノードはまた、親ノードを指すポインタを含み、追跡関係を決定する。
A＊アルゴリズムは、検索したノードごとにG＋Hの和値Fを計算する。
1は、OPENから最適ノードn（すなわち、F値が一番小さいノード）をまとめて検出する。
2ノードnをOPENから集中的に除去し、その後CLOSDセットに追加する。
3 nがターゲットノードである場合、アルゴリズムは終了する。
4そうでなければ、ノードnのすべての隣ノードn'を追加することが試みられる。
キーコードの紹介
基本情報を保存する地図類
地図の種類はランダムに1つの道を探すアルゴリズムの仕事の基礎の地図の情報を生成するために用います。
まずmapクラスを作成し、初期化パラメータは地図の長さと幅を設定し、地図情報を保存する二次元データmapの値を0とし、値は0として当該ノードに移動できることを示します。
class Map():
def __init__(self, width, height):
self.width = width
self.height = height
self.map = [[0 for x in range(self.width)] for y in range(self.height)]
def createBlock(self, block_num):
for i in range(block_num):
x, y = (randint(0, self.width-1), randint(0, self.height-1))
self.map[y][x] = 1
def showMap(self):
print("+" * (3 * self.width + 2))
for row in self.map:
s = '+'
for entry in row:
s += ' ' + str(entry) + ' '
s += '+'
print(s)
print("+" * (3 * self.width + 2))
def generatePos(self, rangeX, rangeY):
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
while self.map[y][x] == 1:
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
return (x , y)
OPENセットに追加されるノードを検索するごとに、イベントの位置情報（x，y）が保存されている次のノード類が作成され、算出されたG値とF値と、そのノードの親ノード（pre＿u）が格納されます。ベントリー
class SearchEntry():
def __init__(self, x, y, g_cost, f_cost=0, pre_entry=None):
self.x = x
self.y = y
# cost move form start entry to this entry
self.g_cost = g_cost
self.f_cost = f_cost
self.pre_entry = pre_entry
def getPos(self):
return (self.x, self.y)
以下は、上のアルゴリズムの主なループで紹介されたコード実装であり、OPENセットとCLOSDセットのデータ構造は辞書を使用しており、一般的には、ノードの追加と削除の時間の複雑さはO（1）であり、遍歴時間の複雑さはO（n）であり、nは辞書の対象数である。
def AStarSearch(map, source, dest):
...
openlist = {}
closedlist = {}
location = SearchEntry(source[0], source[1], 0.0)
dest = SearchEntry(dest[0], dest[1], 0.0)
openlist[source] = location
while True:
location = getFastPosition(openlist)
if location is None:
# not found valid path
print("can't find valid path")
break;
if location.x == dest.x and location.y == dest.y:
break
closedlist[location.getPos()] = location
openlist.pop(location.getPos())
addAdjacentPositions(map, location, dest, openlist, closedlist)
#mark the found path at the map
while location is not None:
map.map[location.y][location.x] = 2
location = location.pre_entry
以下の関数はOPEN集中からF値が一番小さいノードを取得します。OPEN集会が空であればNoneに戻ります。
# find a least cost position in openlist, return None if openlist is empty
def getFastPosition(openlist):
fast = None
for entry in openlist.values():
if fast is None:
fast = entry
elif fast.f_cost > entry.f_cost:
fast = entry
return fast
# add available adjacent positions
def addAdjacentPositions(map, location, dest, openlist, closedlist):
poslist = getPositions(map, location)
for pos in poslist:
# if position is already in closedlist, do nothing
if isInList(closedlist, pos) is None:
findEntry = isInList(openlist, pos)
h_cost = calHeuristic(pos, dest)
g_cost = location.g_cost + getMoveCost(location, pos)
if findEntry is None :
# if position is not in openlist, add it to openlist
openlist[pos] = SearchEntry(pos[0], pos[1], g_cost, g_cost+h_cost, location)
elif findEntry.g_cost > g_cost:
# if position is in openlist and cost is larger than current one,
# then update cost and previous position
findEntry.g_cost = g_cost
findEntry.f_cost = g_cost + h_cost
findEntry.pre_entry = location
def getNewPosition(map, locatioin, offset):
x,y = (location.x + offset[0], location.y + offset[1])
if x < 0 or x >= map.width or y < 0 or y >= map.height or map.map[y][x] == 1:
return None
return (x, y)
def getPositions(map, location):
# use four ways or eight ways to move
offsets = [(-1,0), (0, -1), (1, 0), (0, 1)]
#offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]
poslist = []
for offset in offsets:
pos = getNewPosition(map, location, offset)
if pos is not None:
poslist.append(pos)
return poslist
# check if the position is in list
def isInList(list, pos):
if pos in list:
return list[pos]
return None
get MoveCost関数は、斜め移動かどうかによって消費を計算します。
# imporve the heuristic distance more precisely in future
def calHeuristic(pos, dest):
return abs(dest.x - pos[0]) + abs(dest.y - pos[1])
def getMoveCost(location, pos):
if location.x != pos[0] and location.y != pos[1]:
return 1.4
else:
return 1
地図の長さ、幅、および非移動ノードの数を調整することができる。
開始ノードおよび対象ノードの取得範囲を調整することができる。
WIDTH = 10
HEIGHT = 10
BLOCK_NUM = 15
map = Map(WIDTH, HEIGHT)
map.createBlock(BLOCK_NUM)
map.showMap()
source = map.generatePos((0,WIDTH//3),(0,HEIGHT//3))
dest = map.generatePos((WIDTH//2,WIDTH-1),(HEIGHT//2,HEIGHT-1))
print("source:", source)
print("dest:", dest)
AStarSearch(map, source, dest)
map.showMap()
第2の図の値が2のノードは、発見された経路を示す。
完全コード
python 3.7を使ってコンパイルします。
from random import randint
class SearchEntry():
def __init__(self, x, y, g_cost, f_cost=0, pre_entry=None):
self.x = x
self.y = y
# cost move form start entry to this entry
self.g_cost = g_cost
self.f_cost = f_cost
self.pre_entry = pre_entry
def getPos(self):
return (self.x, self.y)
class Map():
def __init__(self, width, height):
self.width = width
self.height = height
self.map = [[0 for x in range(self.width)] for y in range(self.height)]
def createBlock(self, block_num):
for i in range(block_num):
x, y = (randint(0, self.width-1), randint(0, self.height-1))
self.map[y][x] = 1
def generatePos(self, rangeX, rangeY):
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
while self.map[y][x] == 1:
x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))
return (x , y)
def showMap(self):
print("+" * (3 * self.width + 2))
for row in self.map:
s = '+'
for entry in row:
s += ' ' + str(entry) + ' '
s += '+'
print(s)
print("+" * (3 * self.width + 2))
def AStarSearch(map, source, dest):
def getNewPosition(map, locatioin, offset):
x,y = (location.x + offset[0], location.y + offset[1])
if x < 0 or x >= map.width or y < 0 or y >= map.height or map.map[y][x] == 1:
return None
return (x, y)
def getPositions(map, location):
# use four ways or eight ways to move
offsets = [(-1,0), (0, -1), (1, 0), (0, 1)]
#offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]
poslist = []
for offset in offsets:
pos = getNewPosition(map, location, offset)
if pos is not None:
poslist.append(pos)
return poslist
# imporve the heuristic distance more precisely in future
def calHeuristic(pos, dest):
return abs(dest.x - pos[0]) + abs(dest.y - pos[1])
def getMoveCost(location, pos):
if location.x != pos[0] and location.y != pos[1]:
return 1.4
else:
return 1
# check if the position is in list
def isInList(list, pos):
if pos in list:
return list[pos]
return None
# add available adjacent positions
def addAdjacentPositions(map, location, dest, openlist, closedlist):
poslist = getPositions(map, location)
for pos in poslist:
# if position is already in closedlist, do nothing
if isInList(closedlist, pos) is None:
findEntry = isInList(openlist, pos)
h_cost = calHeuristic(pos, dest)
g_cost = location.g_cost + getMoveCost(location, pos)
if findEntry is None :
# if position is not in openlist, add it to openlist
openlist[pos] = SearchEntry(pos[0], pos[1], g_cost, g_cost+h_cost, location)
elif findEntry.g_cost > g_cost:
# if position is in openlist and cost is larger than current one,
# then update cost and previous position
findEntry.g_cost = g_cost
findEntry.f_cost = g_cost + h_cost
findEntry.pre_entry = location
# find a least cost position in openlist, return None if openlist is empty
def getFastPosition(openlist):
fast = None
for entry in openlist.values():
if fast is None:
fast = entry
elif fast.f_cost > entry.f_cost:
fast = entry
return fast
openlist = {}
closedlist = {}
location = SearchEntry(source[0], source[1], 0.0)
dest = SearchEntry(dest[0], dest[1], 0.0)
openlist[source] = location
while True:
location = getFastPosition(openlist)
if location is None:
# not found valid path
print("can't find valid path")
break;
if location.x == dest.x and location.y == dest.y:
break
closedlist[location.getPos()] = location
openlist.pop(location.getPos())
addAdjacentPositions(map, location, dest, openlist, closedlist)
#mark the found path at the map
while location is not None:
map.map[location.y][location.x] = 2
location = location.pre_entry
WIDTH = 10
HEIGHT = 10
BLOCK_NUM = 15
map = Map(WIDTH, HEIGHT)
map.createBlock(BLOCK_NUM)
map.showMap()
source = map.generatePos((0,WIDTH//3),(0,HEIGHT//3))
dest = map.generatePos((WIDTH//2,WIDTH-1),(HEIGHT//2,HEIGHT-1))
print("source:", source)
print("dest:", dest)
AStarSearch(map, source, dest)
map.showMap()