Увеличение числа граней

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

Поскольку A* алгоритм с хорошей эвристикой действительно дает оптимальное решение для графа, это должно дать нам отличное решение для проблемы 'растрезации'. Но, тогда затраченное время как - Nlog(N) найденное в 4.2.5 больше не истинно (N - число вершин) поскольку число граней, М, больше не статическое, как было принято. Взамен мы имеем M=N² число соседей, для исследования в каждой итерации, тогда затраченное время будет рассчитано как O(NlogN + NM) = O(N³). Следовательно, стоимость для улучшения точности для всех размеров графов зависит в более высокой полиномиальной степени от времени и размера памяти. Однако, что является оптимальном числом соседей? То есть какой идеальный компромисс между ошибкой и эффективностью? Решение использовать восемь соседних ячеек было удобно, так как это то максимальное число, для которого функция стоимости грани легко определяется и вычисляется.

9.2.3

<< | >>

↑

Источник: F. Markus Jonsson. Поиск оптимального пути для транспортных средств на оцифрованых картах реальной местности. 1998

Еще по теме Увеличение числа граней:

- Автоматизация - Гидрология - Документоведение, делопроизводство - Информационные системы - Коммуникации - Криптография - Машиностроение - Метрология - Механика - Микроэлектроника - Нефтегазовое дело - Пищевая промышленность - Приборостроение - Программирование - Системный анализ, управление и обработка информации - Строительство - Технология и оборудование механической и физико-технической обработки - Электрическая энергия - Энергетика -

- Архитектура и строительство - Безопасность жизнедеятельности - Библиотечное дело - Бизнес - Биология - Военные дисциплины - География - Геология - Демография - Диссертации России - Естествознание - Журналистика и СМИ - Информатика, вычислительная техника и управление - Искусствоведение - История - Культурология - Литература - Маркетинг - Математика - Медицина - Менеджмент - Педагогика - Политология - Право России - Право України - Промышленность - Психология - Реклама - Религиоведение - Социология - Страхование - Технические науки - Учебный процесс - Физика - Философия - Финансы - Химия - Художественные науки - Экология - Экономика - Энергетика - Юриспруденция - Языкознание -