Поиск оптимального пути в 3D

Сентябрь 7, 2022

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

Содержание

2. Введение Поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который означает определение компьютерной
3. На данный момент реализованы следующие функции: Поиск кратчайшего пути в одно-, дву-, трехмерных пространствах. Искусственный интеллект
4. Для поиска в пространствах с различной размерностью я разработал различные варианты их представления при помощи графов.
5. Пространство и способы и его представления: Модель двумерного пространства представляет собой систему вершин, имеющих по шесть
6. Модель трёхмерного представляет собой совокупность элементов имеющих по десять связей(см. рис 1.3). Т.е. к каждой вершине
7. Чем программа реализующая поиск в трёхмерном пространстве лучше других систем? Возможность решать более широкий спектр задач.
8. Пункт 1.) Сначала пользователь выбирает нужную ему размерность пространства(см. рис 2.1). по умолчанию выбрано 3D. рис
9. рис 2.2 рис 2.3 8 Пункты 3-4)Пользователь определяет в пространстве точки начала и пункта назначения(см. рис
10. Далее, по нажатии кнопки “рассчитать” программа определяет оптимальный путь(см. рис 2.4) (если он существует), и выводит
11. Алгоритм: В основу работы данной программы вложен алгоритм Ли. Данный алгоритм построен на трассировке пространства лучами
12. Если волна прошла все доступные вершины, но так и не достигла пункт назначения, значит, путь от
13. К отрицательным чертам данного метода следует отнести его низкую производительность и большой объем памяти требуемый для
14. рис 4.1 Сфера применения: 13 Сфера применения алгоритмов трассировки обширна, одна из них – автоматизированная трассировка
15. Сфера применения: Другая сфера применения – нахождение кратчайшего пути на оцифрованных картах местности(см. рис. 4.2-4.4.5). рис
16. Как видим у алгоритмов достаточно широкое применение и роль которую они начинают играть на рынке увеличивается
17. В программе планируются следующие дополнения: Исправление некоторых неполадок. Улучшение графического интерфейса. Введение наглядной системы трёхмерного рендеринга.
18. Системные требования: Процессор: 233 MHz Оперативная память: 64 Мб RAM Видеоадаптер и монитор: VGA (640 x
20. Скачать презентацию

Слайд 2

Введение
Поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который

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

Слайд 3

На данный момент реализованы следующие функции:
Поиск кратчайшего пути
в одно-,

дву-, трехмерных пространствах.
Искусственный интеллект
обхода препятствий.
Визуализация поиска на плоскости.

Слайд 4

Для поиска в пространствах с различной размерностью я разработал различные варианты

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

рис 1.1

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

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

Слайд 5

Пространство и способы и его представления:
Модель двумерного пространства представляет собой

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

рис 1.2

Слайд 6

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

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

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

рис 1.3

Слайд 7

Чем программа реализующая поиск в трёхмерном пространстве лучше других систем?
Возможность решать

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

Слайд 8

Пункт 1.) Сначала пользователь выбирает нужную ему размерность пространства(см. рис

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

рис 2.1

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

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

Слайд 9

рис 2.2
рис 2.3
8
Пункты 3-4)Пользователь определяет в пространстве

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

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

Слайд 10

Далее, по нажатии кнопки “рассчитать” программа определяет оптимальный путь(см. рис

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

рис 2.4

рис 2.5

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

Слайд 11

Алгоритм:
В основу работы данной программы вложен алгоритм Ли. Данный алгоритм

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

рис 3.1

Слайд 12

Если волна прошла все доступные вершины, но так и не

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

Алгоритм:

рис 3.2

Слайд 13

К отрицательным чертам данного метода следует отнести его низкую производительность и

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

Алгоритм:

Слайд 14

рис 4.1
Сфера применения:
13
Сфера применения алгоритмов трассировки обширна, одна

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

Слайд 15

Сфера применения:
Другая сфера применения – нахождение кратчайшего пути на оцифрованных

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

рис 4.2

рис 4.3

рис 4.4

рис 4.5

Слайд 16

Как видим у алгоритмов достаточно широкое применение и роль которую

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

Слайд 17

В программе планируются следующие дополнения:
Исправление некоторых неполадок.
Улучшение графического интерфейса.
Введение наглядной

системы трёхмерного рендеринга.
Считывание заданий из файла.

Слайд 18

Системные требования:
Процессор: 233 MHz
Оперативная память: 64 Мб RAM
Видеоадаптер и монитор: VGA (640 x

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

Поиск оптимального пути в 3D

Содержание

ВведениеПоиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который

На данный момент реализованы следующие функции:Поиск кратчайшего пути в одно-,

Для поиска в пространствах с различной размерностью я разработал различные варианты

Пространство и способы и его представления: Модель двумерного пространства представляет собой

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

Чем программа реализующая поиск в трёхмерном пространстве лучше других систем?Возможность решать

Пункт 1.) Сначала пользователь выбирает нужную ему размерность пространства(см. рис

рис 2.2 рис 2.38 Пункты 3-4)Пользователь определяет в пространстве

Далее, по нажатии кнопки “рассчитать” программа определяет оптимальный путь(см. рис

Алгоритм: В основу работы данной программы вложен алгоритм Ли. Данный алгоритм

Если волна прошла все доступные вершины, но так и не

К отрицательным чертам данного метода следует отнести его низкую производительность и

рис 4.1Сфера применения:13 Сфера применения алгоритмов трассировки обширна, одна

Сфера применения: Другая сфера применения – нахождение кратчайшего пути на оцифрованных

Как видим у алгоритмов достаточно широкое применение и роль которую

В программе планируются следующие дополнения:Исправление некоторых неполадок.Улучшение графического интерфейса.Введение наглядной

Системные требования:Процессор: 233 MHzОперативная память: 64 Мб RAMВидеоадаптер и монитор: VGA (640 x

Похожие презентации

Введение
Поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который

На данный момент реализованы следующие функции:
Поиск кратчайшего пути
в одно-,

Пространство и способы и его представления:
Модель двумерного пространства представляет собой

Чем программа реализующая поиск в трёхмерном пространстве лучше других систем?
Возможность решать

рис 2.2
рис 2.3
8
Пункты 3-4)Пользователь определяет в пространстве

Алгоритм:
В основу работы данной программы вложен алгоритм Ли. Данный алгоритм

рис 4.1
Сфера применения:
13
Сфера применения алгоритмов трассировки обширна, одна

Сфера применения:
Другая сфера применения – нахождение кратчайшего пути на оцифрованных

В программе планируются следующие дополнения:
Исправление некоторых неполадок.
Улучшение графического интерфейса.
Введение наглядной

Системные требования:
Процессор: 233 MHz
Оперативная память: 64 Мб RAM
Видеоадаптер и монитор: VGA (640 x