15.Алгоритм нахождения минимального остовного дерева.

В графе с нагруженными дугами можно выделить минимальное остовное дерево как остовное дерево с минимальным суммарным значением нагруженных величин.

шаг 0: С0 = O, неС0=N

шаг 1: выбираем любой i узел из множества неС0, переносим в множество С1.

С1={1}, С1=N-{i}; k=2

шаг k:неCk-1выберем узел j*, который соединен самой короткой дугой с множеством узлов: Ск-1.

Ск = Ск-1 + {j*}; неСк = неСк-1 - {j*}; если неСк!= O, то k=k+1 (повтор осн шаг k )

<< | >>
Источник: Шпаргалка по предмету Теория принятия решений. 2017
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 15.Алгоритм нахождения минимального остовного дерева.:

  1. 13.Алгоритм нахождения минимального остовного дерева.
  2. Алгоритм Краскала нахождения минимального остовного дерева.
  3. Остовное дерево. Цикломатическое число графа.
  4. 28. Графы. Маршруты в графах. Задание графов матрицами (смежности, инцидентности, весов). Алгоритмы поиска минимальных маршрутов в графах: алгоритм фронта волны, алгоритм Форда Беллмана, алгоритм Дейкстры.
  5. в) Алгоритм нахождения кратчайших расстояний от выделенной вершины до всех остальных вер­шин графа (алгоритм Дейкстры).
  6. 34. Нахождение решения с минимальным информационным риском
  7. №43 Алгоритм нахождение наименьшего пути.
  8. 23. Алгоритмы поиска в деревьях.
  9. 35. Нахождение решения с минимальными инф.-тех. потерями
  10. Алгоритм нахождения кратчайшего пути
  11. Синтаксическое дерево и алгоритм его обхода “снизу-вверх”.
  12. 17. Метод «дерева решений» (ДР).Алгоритм.
  13. Синтаксическое дерево и алгоритм его обхода “сверху-вниз”.
  14. Алгоритм Форда нахождения максимального потока на сети.
  15. 14 Алгоритм Дейкстры нахождения кратчайшего пути.
  16. 15 Алгоритм Флойда нахождения кратчайшего пути
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -