Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Тюменский Государственный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

pathfinding.doc

Скачиваний:

Добавлен:

18.04.2015

Размер:

351.74 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 67 / 87 8 > Следующая >>>

Сравнительный анализ алгоритмов поиска пути

Как уже было замечено в начале работы, многообразие алгоритмов поиска пути обусловлено многообразием их применений, для каждого из которых эффективнее работает определённый алгоритм поиска пути.

Алгоритм Дейкстры приоритетен в случаях поиска пути до всех точек области поиска, а также в случае отсутствия сколь либо эффективной эвристической функции оценки расстояния между элементами области поиска.
Волновой алгоритм эффективен, если область поиска имеет неравномерную проходимость, что затрудняет эвристические вычисления для A*.
Алгоритм A* эффективен при одиночном поиске пути между двумя точками, если возможно эффективно эвристически получать примерную дистанцию между элементами области поиска.
Навигационная сетка с использованием алгоритма A* эффективна при созданииAI, в чьи задачи входит не только поиск пути. Также этот метод эффективен при необходимости построить реалистичную сглаженную траекторию движения между двумя точками. Данный метод предполагает наличие детальной информации об области поиска или возможности получения такой информации.
Эвристические алгоритмы поиска пути применимы и оптимальны, если необходим максимально простой алгоритм, при этом область поиска достаточно проста, а применения алгоритма допускают неточность полученного пути.

В данном разделе будет приведено практическое подтверждение некоторых из данных утверждений на основании скорости выполнения представленных в данной работе алгоритмов, а именно:

Алгоритм Дейкстры против алгоритма A* при поиске пути между двумя точками по двумерному массиву.
Алгоритм Дейкстры против алгоритма A* при поиске пути от данной точки для всех точек двумерного массива.

Волновой алгоритм для двумерного массива практически эквивалентен алгоритму Дейкстры для поиска пути между 2 точками, посему результаты, результаты, верные для алгоритма Дейкстры можно считать верными для Волнового алгоритма, а природа эвристических алгоритмов сравнительно проста для понимания.

Итак, для подобного анализа сначала необходимо адаптировать алгоритм Дейкстры для двумерного массива. Для определения связей обрабатываемых точек массива можно использовать созданную для A* функциюgetConnections.(см. подраздел «АлгоритмA*» - практика) Весь объём изменений обеих алгоритмов Дейкстры касается изменения операций над областью поиска, поэтому отдельно комментировать каждую часть алгоритма ещё раз попросту нецелесообразно.

Сам алгоритм при этом выглядит следующим образом:

def Dijkstramass(graph,start,end):

class NodeRecord:

node=None

connection=None

costSoFar=None

startRecord =NodeRecord()

startRecord.node = start

startRecord.connection = None

startRecord.costSoFar = 0

olist= [startRecord]

clist = []

while len(olist) > 0:

tlist=[i.costSoFar for i in olist]

current=olist[tlist.index(min(tlist))]

if current.node == end:

break

connections = getConnections(graph,current.node[0],current.node[1])

for connection in connections:

# прикидываем текущую стоимость

endNode = connection.getToNode

endNodeCost = current.costSoFar + connection.getCost

if endNode in [clist[ite].node for ite in range(len(clist))]:

endNodeRecord = clist[[clist[ite].node for ite in range(len(clist))].index(endNode)]

if endNodeRecord.costSoFar <= endNodeCost:

continue

clist.pop(clist.index(endNodeRecord))

elif endNode in [olist[ite].node for ite in range(len(olist))]:

endNodeRecord = olist[[olist[ite].node for ite in range(len(olist))].index(endNode)]

if endNodeRecord.costSoFar <= endNodeCost:

continue

else:

endNodeRecord = NodeRecord()

endNodeRecord.node = endNode

endNodeRecord.costSoFar = endNodeCost

endNodeRecord.connection = connection

if not endNodeRecord in olist :

olist.append(endNodeRecord)

clist.append(current)

olist.pop(olist.index(current))

else:

return -1

path = [end]

while current.node!=start:

for i in clist:

if current.connection.getFromNode==i.node:

current=i

path.insert(0,current.node)

break

return path

Также потребуется аналогичным образом адаптировать алгоритм Дейкстры для всех точек под двумерный массив:

def Dijkstra2mass(graph,start):

class NodeRecord:

node=None

connection=None

costSoFar=None

startRecord =NodeRecord()

startRecord.node = start

startRecord.connection = None

startRecord.costSoFar = 0

olist= [startRecord]

clist = []

while len(olist) > 0:

tlist=[i.costSoFar for i in olist]

current=olist[tlist.index(min(tlist))]

connections = getConnections(graph,current.node[0],current.node[1])

for connection in connections:

endNode = connection.getToNode

endNodeCost = current.costSoFar + connection.getCost

if endNode in [clist[ite].node for ite in range(len(clist))]:

endNodeRecord = clist[[clist[ite].node for ite in range(len(clist))].index(endNode)]

if endNodeRecord.costSoFar <= endNodeCost:

continue

clist.pop(clist.index(endNodeRecord))

elif endNode in [olist[ite].node for ite in range(len(olist))]:

endNodeRecord = olist[[olist[ite].node for ite in range(len(olist))].index(endNode)]

if endNodeRecord.costSoFar <= endNodeCost:

continue

else:

endNodeRecord = NodeRecord()

endNodeRecord.node = endNode

endNodeRecord.costSoFar = endNodeCost

endNodeRecord.connection = connection

if not endNodeRecord in olist :

olist.append(endNodeRecord)

clist.append(current)

olist.pop(olist.index(current))

paths=[]

for end in clist:

if end.node==start:continue

current=end

path = [end.node]

while current.node!=start:

for i in clist:

if current.connection.getFromNode==i.node:

current=i

path.insert(0,current.node)

break

path.insert(0,str(start)+':'+str(end.node))

paths.append(path)

return paths

Итак, для начала сравним алгоритм Дейкстры для 2 точек двумерного массива (первый из представленных в этом разделе алгоритмов) и алгоритм A* (представлен в подразделе «АлгоритмA*» - Практика).

Код программы-измерителя будет состоять из двух данных алгоритмов, функции getConnections, выдающей список связей для данной точки в области поиска, а также функции, отвечающей непосредственно за измерение:

def pftimer (function):

graph=[['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],

['#', ' ', ' ', ' ', '#', '#', ' ', ' ', ' ', ' ', '#', '#'],

['#', '#', '#', ' ', ' ', ' ', '#', ' ', '#', '#', ' ', '#'],

['#', ' ', ' ', ' ', '#', ' ', '#', ' ', ' ', ' ', ' ', '#'],

['#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', '#', ' ', '#'],

['#', ' ', '#', '#', ' ', ' ', ' ', ' ', '#', '#', ' ', '#'],

['#', '#', ' ', ' ', '#', '#', 'A', '#', ' ', '#', ' ', '#'],

['#', ' ', ' ', '#', ' ', ' ', ' ', '#', '#', '#', ' ', '#'],

['#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'],

['#', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],

['#', 'B', ' ', ' ', ' ', '#', '#', '#', '#', '#', ' ', '#'],

['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]

start=[6,6]

end=[10,1]

import time

starttime=time.time()

for i in range(1000):

tmp=function(graph,start,end)

print 'Большой лабиринт: ',(time.time()-starttime)/1000.0

graph=[['#', '#', '#', '#', '#'],

['#', 'A', ' ', ' ', '#'],

['#', ' ', '#', ' ', '#'],

['#', ' ', ' ', 'B', '#'],

['#', '#', '#', '#', '#']]

start=[1,1]

end=[3,3]

starttime=time.time()

for i in range(1000):

tmp=function(graph,start,end)

print 'Малый лабиринт : ',(time.time()-starttime)/1000.0

graph=[['#', '#', '#', '#', '#'],

['#', 'A', ' ', ' ', '#'],

['#', '#', '#', ' ', '#'],

['#', 'B', ' ', ' ', '#'],

['#', '#', '#', '#', '#']]

start=[1,1]

end=[3,1]

starttime=time.time()

for i in range(1000):

tmp=function(graph,start,end)

print 'Прямойлабиринт : ',(time.time()-starttime)/1000.0

Измерения проводятся соответственно на 3 типах лабиринтов:

Большой лабиринт, где путь до цели составляет незначительную долю от всех проходимых точек лабиринта.
Малый лабиринт, где путь до цели составляет 50% от всех проходимых точек лабиринта.
Прямая дорога, где путь до цели занимает всю проходимую часть лабиринта.

Для каждого случая функция вызывается 1000 раз и для вычисления времени, затраченного на 1 выполнение, вычисленный промежуток делится на 1000. Функция-счётчик выполняется последовательно для алгоритма Дейкстры и A*. Такие меры необходимы для того, чтобы влияние прочих процессов на вычисленную скорость работы функции было минимальным.

Все вычисления будут проводиться на ПК, укомплектованном процессором IntelCorei5-2410M(4-ядерный, частота ядра - 2.30ГГц) при минимальной и относительно неизменной загрузке его прочими задачами(0-4% в спокойном состоянии по показаниям с Диспетчера задач в течение минуты).

Итак, результаты:

Алгоритм Дейкстры

>>> pftimer(Dijkstramass)

Большой лабиринт: 0.00363999986649

Малый лабиринт : 0.000248000144958

Прямой лабиринт : 0.000137000083923

>>> pftimer(Dijkstramass)

Большой лабиринт: 0.00358099985123

Малый лабиринт : 0.00022000002861

Прямой лабиринт : 0.000140000104904

>>> pftimer(Dijkstramass)

Большой лабиринт: 0.00360800004005

Малый лабиринт : 0.000248999834061

Прямой лабиринт : 0.000141000032425

Алгоритм A*

>>> pftimer(AStar)

Большой лабиринт: 0.000667000055313

Малый лабиринт : 0.000141000032425

Прямой лабиринт : 0.000157999992371

>>> pftimer(AStar)

Большой лабиринт: 0.000709999799728

Малый лабиринт : 0.000140000104904

Прямой лабиринт : 0.000150000095367

>>> pftimer(AStar)

Большой лабиринт: 0.000717000007629

Малый лабиринт : 0.000156000137329

Прямой лабиринт : 0.000155999898911

Результаты вычислений подтверждают теоретические данные:

Для большого лабиринта, A* справляется с задачей в 3 раза быстрее алгоритма Дейкстры, поскольку алгоритм Дейкстры при своём выполнении будет равномерно обрабатывать всю область поиска в порядке удаления от начала. Согласно показаниям интерпретатораPython, алгоритм Дейкстры обследовал 45 узлов в большом лабиринте. АлгоритмA* позволяет уменьшить число обрабатываемых узлов за счёт эвристики, т.е. данный алгоритм обрабатывает узлы в порядке убывания вероятности их появления в искомом пути, и согласно тем же данным, алгоритмA* в большом лабиринте обрабатывает 8 точек + конец пути, что равно длине конечного пути.
Для малого лабиринта A* работает примерно в 1.6 раз быстрее алгоритма Дейкстры, поскольку он обрабатывает в 2раза меньше узлов, но при каждой обработке узла делает дополнительные эвристические вычисления, а также выполняет все прочие этапы алгоритма в тех же условиях, что и алгоритм Дейкстры.
Для прямой дороги алгоритм Дейкстры работает несколько быстрее (порядка 1.1 раз) алгоритма A*, поскольку оба алгоритма будут обрабатывать все проходимые точки лабиринта (все они лежат на конечном пути), но алгоритмA* дополнительно производит эвристические расчёты расстояния до конца пути.

Аналогичным образом, несколько изменив функцию-счётчик, можно произвести схожие измерения для вычисления расстояния от заданной точки до всех точек в области поиска.

A* в данном случае используется через вспомогательную функцию:

def Astar2all(graph,start):

paths=[]

for i in graph:

for j in graph[i]:

if graph[i][j]!='#' and [i,j]!=start:

path=AStar(graph,start,[i,j])

if path != -1:

path.insert(0, (str(start)+':'+str([i:j])))

paths.append(path)

return paths

Функция-счётчик принимает следующий вид:

def pftimer2 (function):