Поиск оптимального пути в 3D презентация

Подопригора Н.Б.

Лицей-интернат для одарённых детей Ставропольского края

означает определение компьютерной программой наилучшего, оптимального маршрута между двумя точками. Сегодня, поиск оптимального пути в пространстве является одной из ключевых задач современных систем ИИ и многих других областей науки и техники.

1

функции:


Поиск кратчайшего пути
в одно-, дву-, трехмерных пространствах.


Искусственный интеллект
обхода препятствий.


Визуализация поиска на плоскости.

2

разработал различные варианты их представления при помощи графов. Связи между вершинами являются вариантами передвижения из одной координаты в соседнюю.

рис 1.1

Модель одномерного пространства представляет собой совокупность вершин имеющих по две связи
(см. рис 1.1)

Пространство и способы и его представления:

3

представляет собой систему вершин, имеющих по шесть связей
(см. рис 1.2).
Таким образом вершины образовывают матрицу координат в которых будет происходить поиск.

рис 1.2

4

десять связей(см. рис 1.3).
Т.е. к каждой вершине пространства в отличие
от двумерного добавляются ещё и связи по высоте.

Пространство и способы и его представления:

рис 1.3

5

более широкий спектр задач.

Возможность при необходимости приспособить решение задачи для любой размерности пространства.

Универсальность метода.

6

рис 2.1).
по умолчанию выбрано 3D.

рис 2.1

Пункт 2.) На данном этапе пользователь ограничивает пространство заданной размерности в нужных ему диапазонах(так же см. рис. 2.1).

7

Элементы интерфейса:

в пространстве
точки начала и пункта
назначения(см. рис 2.2).
Затем по желанию располагаются препятствия(они могут располагаться случайно
или по усмотрению)
(см. рис 2.3).

Элементы интерфейса:

путь(см. рис 2.4) (если он существует), и выводит пользователю длину оптимального пути. В случае недосягаемости точки назначения программа выводит соответствующее сообщение(см. рис 2.5).

рис 2.4

рис 2.5

9

Элементы интерфейса:

Данный алгоритм построен на трассировке пространства лучами или волнами. Препятствия являются источниками вторичных волн, что позволяет отсканировать всё пространство.
Элемент в который пришла волна сам становится фронтом волны и т.д.(см. рис 3.1).

рис 3.1

10

доступные вершины, но так и не достигла пункт назначения, значит, путь от старта до финиша проложить невозможно.(см рис. 3.2).После достижения волной финиша, от финиша прокладывается путь до старта и сохраняется в массиве.

Алгоритм:

рис 3.2

11

низкую производительность и большой объем памяти требуемый для хранения информации. Но был осуществлён выбор именно этого метода так как в отличие от других методов, он в процессе своей работы находит кратчайший путь от начальной вершины до каждой. Это очень полезно в тех случаях когда точка назначения может динамически меняться, тогда нам потребуется только одиножды просчитать пространство.

Алгоритм:

12

алгоритмов трассировки обширна, одна из них – автоматизированная трассировка печатных плат(см. рис. 4.1).

картах местности(см. рис. 4.2-4.4.5).

рис 4.2

рис 4.3

рис 4.4

рис 4.5

14

у алгоритмов достаточно широкое применение и роль которую они начинают играть на рынке увеличивается с каждым годом. Существуют целые компании которые ведут свои исследования в данном направлении. В данном контексте стоит упомянуть фирмы Autodesk (U.S.A.) и Kynogon (Fr.).
Их главные направления разработки в этой области:
* Иерархический поиск пути в трёхмерном пространстве

* Алгоритмы координации командного взаимодействия

* Динамический анализ трёхмерной топологии и др.

15

системы трёхмерного рендеринга.


Считывание заданий из файла.

16

480)
Свободное место на HDD: 10 мб
Устройства взаимодействия с пользователем: клавиатура,мышь

17