Классификационная схема характеристик сложности задачи выбора пути в условиях неопределенности - Модели и методы решения проблемы выбора в условиях неопределенности
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности задачи выбора пути в условиях неопределенности.
Для исследования задачи выбора эффективного алгоритма маршрутизации о априорно известному графу использовались следующие десять характеристик сложности задачи [1]:
- 1. Время построения пути. 2. Длина построенного пути. 3. Число ребер пути. 4. Число отброшенных ребер вдоль пути. 5. Размер фронта волны поиска (массива открытых вершин) на заключительной итерации. 6. Размер тела волны поиска (массив закрытых вершин) на заключительной итерации. 7. Число итераций. 8. Число элементов в волне на момент завершения поиска (сумма пятой и шестой характеристик). 9. Целенаправленность (число ребер в пути, деленное на восьмую характеристику, не считая начальной вершины). 10. Максимальная длина фронта волны поиска (массива открытых вершин).
Для характеристики сложности всего графа могут использоваться гистограммы указанных выше характеристик для выбранного тестового набора задач (в которые могут входить и все возможные задачи на данном графе). Численные эксперименты показали, что для алгоритмов выбора пути по априорно известному графу выполняется свойство несравнимости любых двух алгоритмов даже в пределах достаточно узкого множества возможных задач. Это означает, что если рассматриваются 2 алгоритма А и В, то существует задача, где алгоритм А эффективнее алгоритма В, и существует задача, где алгоритм В эффективнее алгоритма А.
Для исследования алгоритмов выбора пути в условиях неопределенности на террайнах могут использоваться три способа. Первый заключается в том, что на террайне выделяется конечный магистральный граф, для которого может использоваться указанный выше подход.
Второй способ заключается в построении характеристик структуры террайна.
Поскольку террайн представляет собой граф с континуумом вершин и ребер, построенных на основе отношений видимости, то на нем могут быть аналогично определены следующие две основные структурные характеристики графа: диаметр и число доминирования.
Целочисленная метрика k(x, y), задаваемая на точках носителя террайна определяется как минимальное число ребер в допустимом пути (ломаной) из x в y и наоборот. Максимум этой функции по точкам x, y и определяет диаметр террайна. Таким образом, диаметр террайна равен минимально необходимому числу сеансов измерений для передвижения между любыми двумя выбранными точками (в случае, если нет ограничений на радиус действия измерительной системы). Ниже эта характеристика будет обозначаться как г(V).
Аналогом числа доминирования для террайна является навигационное число. Пусть А - множество точек на террайне, а V - носитель террайна. Если V(A)=V (это означает, что множество видимых из А вершин совпадает со всем террайном), то А называется навигационным множеством. Навигационное множество называется навигационным базисом, если при удалении из А любого элемента оставшееся подмножество точек уже не является навигационным.
Нетрудно видеть, что навигационное множество есть аналог доминирующего множества для конечного графа, а навигационный базис - аналог независимого доминирующего множества. Соответствующие термины для террайна подчеркивают тот факт, что ориентиры на местности должны образовывать навигационное множество для того, чтобы привязка по этим ориентирам была всюду определена.
Навигационное множество называется навигационным множеством k-го порядка, если для любой точки x |A(x)|?k
Для стандартного террайна множество вершин Р является навигационным множеством по крайней мере четвертого порядка. Пусть nmin(V) и nmax(V) соответствуют минимальной и максимальной возможным размерностям (числу элементов) для навигационного базиса. Очевидно, что эти два числа могут быть различны (см. рис.1).
Рисунок 1
Указанные числа называются минимальным и максимальным навигационными числами террайна.
Похожие статьи
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
В большинстве реальных больших систем не обойтись без учета "состояний природы" -- воздействий Стохастического типа, случайных величин или случайных...
-
Неопределенность - это фундаментальное свойство природы, а еще более (и точнее) - свойство, характеризующее неточность, незамкнутость, неокончательность,...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
В настоящее время Российская Федерация входит в состав ВТО, в связи с чем, для устойчивого развития, для надежности, для стойкости [1, 2] появляется...
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Модель "вход - выход" для нестационарной системы управления можно представить в следующем виде [2] . Где коэффициенты матриц возмущения и ограничены...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Рассмотрим взвешенный предфрактальный граф, порожденный затравкой и K процессоров, где. Параллельный алгоритм выделения дольного графа основан на...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Любое частное решения уравнения (1) на координатной плоскости х0у изображено в виде графика функции у=у (х, с) (с=const). В теории дифференциальных...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Расчет верхней и нижней границы надежности схемы методом минимальных путей и сечений Как видно из схемы, она не является последовательно-параллельной,...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
-
1. Предпосылки метода наименьших квадратов. 2. Проблема мультиколлинеарности. 3. Гомоскедатичность и гетероскедатичность. Линейные регрессионные модели с...
-
Свойства операции умножения матриц - Методы решения системы линейных уравнений
1)Умножение матриц не коммутативно, т. е. АВ ВА даже если определены оба произведения. Однако, если для каких - либо матриц соотношение АВ=ВА...
-
Классификация по типу задач. - Виды моделей
Описательные (дескриптивные) модели (к ним часто приводят, постановки задач типа. А) предназначены для описания изучаемого процесса, объяснения...
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Основные понятия сетевых и графовых моделей Объектом исследования является сеть, состоящая из узлов и линий связи. Предполагается, что в сети имеется два...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Счетные и несчетные множества - Методы решения системы линейных уравнений
Пусть, например, А и В Ї некоторые множества. Тогда их возможные взаимоотношения можно рассмотреть в виде таблицы: Диаграмма Венна Диаграмма Венна...
-
Функции и ее свойства - Методы решения системы линейных уравнений
В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...
-
Из перечисленного обзора типов ММ, составляющих предмет ИСО, можно выделить следующие особенности ММ ИСО [3]. - Системный подход, заставляющий...
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
Пример решения задачи симплекс-методом, Условие задачи - Математические методы и модели в экономике
Рассмотрим алгоритм симплексного метода на примере решения задачи планирования товарооборота предприятия торговли. Требуется определить оптимальную...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
-
Тема, с которой мы сегодня ознакомимся это "Применение матриц при решении экономических задач." Рассмотрим как с помощью матриц можно решать...
-
Условия существования гамильтонова цикла - Гамильтоновы циклы
В отличие от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
При написании программ численного интегрирования желательно, чтобы для любой функции распределение узлов являлось оптимальным или близким к нему. Однако...
-
Розробка математичного забезпечення інформаційної системи Характеристика моделей і методів рішення економічної задачі Фінансовий аналіз здійснюється за...
Классификационная схема характеристик сложности задачи выбора пути в условиях неопределенности - Модели и методы решения проблемы выбора в условиях неопределенности