Изменения

Перейти к: навигация, поиск

Visibility graph и motion planning

133 байта убрано, 22:14, 8 февраля 2015
м
Нет описания правки
|[[Файл:notShort.png|300px|thumb|right|Такой путь не самый короткий]]
|}
Рассмотрим задачу нахождения пути от точки <tex> S </tex> до <tex> T </tex> с препятствиями. Для начала рассмотрим движение материальной точки, случай. Случай, когда размером и формой движимого объекта пренебречь нельзя, будет рассмотрен [[Visibility graph и motion planning#Motion planning|позднее]].
Обычно эта задача решается с помощью [[Трапецоидная карта | трапецоидной карты]], по которой . По ней строится граф, ребра которого соединяют центры трапедоидов , а также начальную и конечную вершины <tex> S </tex> и <tex> T </tex> с серединами вертикальных сторон трапецоидов. В этом таком графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) находится ищется путь от <tex> S </tex> до <tex> T </tex>между начальной и конечной вершинами.
Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и идеально подходит для нахождения какого-нибудь пути между конечными вершинами. Но иногда нужно найти кратчайший путь, и этот алгоритм не подходит, хоть и дает хорошее приближение. Однако , решения нахождения кратчайшего пути в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин).
== Visibility graph ==
Рассмотрим точное решение нахождения кратчайшего пути на плоскости от точки <tex> S </tex> до <tex> T </tex> между двумя точками с полигональными препятствиями с помощью построения графа видимости. После его построения, как и в случае с трапецоидной картой, кратчайший путь ищется стандартными алгоритмамилюбым стандартным алгоритмом поиска (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]).
Для простоты рассуждений начальную и конечную вершины <tex> S </tex> и <tex> T </tex> будем считать вершинами полигонов.
{{Лемма
222
правки

Навигация