Модели и методы решения проблемы выбора в условиях неопределенности — страница 10

  • Просмотров 3765
  • Скачиваний 551
  • Размер файла 206
    Кб

показателю — своей сложности, как по сущности, так и по сложности практической реализации даже при “повальном” использовании компьютерных программ. К примеру, есть утверждения о преимуществах метода главных компонент — дескать, этот метод точнее расчета нагрузок на факторы.                                               4.Классификационная схема характеристик сложности

задачи выбора пути в условиях неопределённости Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности задачи выбора пути в условиях неопределенности. Для исследования задачи выбора эффективного алгоритма маршрутизации о априорно известному графу использовались следующие десять характеристик сложности задачи [1]:   1. Время

построения пути. 2. Длина построенного пути. 3. Число ребер пути. 4. Число отброшенных ребер вдоль пути. 5. Размер фронта волны поиска (массива открытых вершин) на заключительной итерации. 6. Размер тела волны поиска (массив закрытых вершин) на заключительной итерации. 7. Число итераций. 8. Число элементов в волне на момент завершения поиска (сумма пятой и шестой характеристик). 9. Целенаправленность (число ребер в пути, деленное на

восьмую характеристику, не считая начальной вершины). 10. Максимальная длина фронта волны поиска (массива открытых вершин). Для характеристики сложности всего графа могут использоваться гистограммы указанных выше характеристик для выбранного тестового набора задач (в которые могут входить и все возможные задачи на данном графе). Численные эксперименты показали, что для алгоритмов выбора пути по априорно известному графу

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

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