- •Олимпиада школьников «Шаг в будущее»
- •Введение
- •Алгоритм Дейкстры
- •Принцип работы
- •Эффективность алгоритма
- •Практика
- •Волновой алгоритм
- •Практика
- •Алгоритм a* История создания
- •Принцип работы
- •Эффективность.
- •Практика
- •Дальнейшая оптимизация
- •Навигационная сетка
- •Эвристические алгоритмы поиска пути
- •Сравнительный анализ алгоритмов поиска пути
- •Практическое применение алгоритмов поиска пути.
- •Заключение
- •Список использованной литературы
Сравнительный анализ алгоритмов поиска пути
Как уже было замечено в начале работы, многообразие алгоритмов поиска пути обусловлено многообразием их применений, для каждого из которых эффективнее работает определённый алгоритм поиска пути.
Алгоритм Дейкстры приоритетен в случаях поиска пути до всех точек области поиска, а также в случае отсутствия сколь либо эффективной эвристической функции оценки расстояния между элементами области поиска.
Волновой алгоритм эффективен, если область поиска имеет неравномерную проходимость, что затрудняет эвристические вычисления для 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):
graph=[['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
['#', ' ', ' ', ' ', '#', '#', ' ', ' ', ' ', ' ', '#', '#'],
['#', '#', '#', ' ', ' ', ' ', '#', ' ', '#', '#', ' ', '#'],
['#', ' ', ' ', ' ', '#', ' ', '#', ' ', ' ', ' ', ' ', '#'],
['#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', '#', ' ', '#'],
['#', ' ', '#', '#', ' ', ' ', ' ', ' ', '#', '#', ' ', '#'],
['#', '#', ' ', ' ', '#', '#', 'A', '#', ' ', '#', ' ', '#'],
['#', ' ', ' ', '#', ' ', ' ', ' ', '#', '#', '#', ' ', '#'],
['#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'],
['#', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
['#', ' ', ' ', ' ', ' ', '#', '#', '#', '#', '#', ' ', '#'],
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]
start=[6,6]
import time
starttime=time.time()
for i in range(100):
tmp=function(graph,start)
print 'Большой лабиринт: ',(time.time()-starttime)/100.0
graph=[['#', '#', '#', '#', '#'],
['#', 'A', ' ', ' ', '#'],
['#', ' ', '#', ' ', '#'],
['#', ' ', ' ', ' ', '#'],
['#', '#', '#', '#', '#']]
start=[1,1]
starttime=time.time()
for i in range(100):
tmp=function(graph,start)
print 'Малый лабиринт : ',(time.time()-starttime)/100.0
graph=[['#', '#', '#', '#', '#'],
['#', 'A', ' ', ' ', '#'],
['#', '#', '#', ' ', '#'],
['#', ' ', ' ', ' ', '#'],
['#', '#', '#', '#', '#']]
start=[1,1]
starttime=time.time()
for i in range(100):
tmp=function(graph,start)
print 'Прямой лабиринт : ',(time.time()-starttime)/100.0
Результаты вычислений получились следующие:
>>> pftimer2(Dijkstra2mass)
Большой лабиринт: 0.00671000003815
Малый лабиринт : 0.000309998989105
Прямой лабиринт : 0.000160000324249
>>> pftimer2(Dijkstra2mass)
Большой лабиринт: 0.00640000104904
Малый лабиринт : 0.000150001049042
Прямой лабиринт : 0.000160000324249
>>> pftimer2(Dijkstra2mass)
Большой лабиринт: 0.00609999895096
Малый лабиринт : 0.000300002098083
Прямой лабиринт : 0.000199999809265
>>> pftimer2(Astar2all)
Большой лабиринт: 0.0404799985886
Малый лабиринт : 0.00125
Прямой лабиринт : 0.00047000169754
>>> pftimer2(Astar2all)
Большой лабиринт: 0.0410400009155
Малый лабиринт : 0.00125
Прямой лабиринт : 0.000460000038147
>>> pftimer2(Astar2all)
Большой лабиринт: 0.0402600002289
Малый лабиринт : 0.00125
Прямой лабиринт : 0.000469999313354
Во всех случаях, алгоритм A* работает значительно (в 2 и более раз) медленнее алгоритма Дейкстры, при выполнении алгоритмаA*, для каждой точки заново производится обработка области поиска, в то время как алгоритм Дейкстры производит обработку только 1 раз. Полученные результаты полностью подтверждают теоретическую информацию: алгоритм А*, как модификация алгоритма Дейкстры, оптимизирован для вычисления расстояния между 2 точками, поэтому он менее полезен при вычислении пути до всех точек области поиска.