Расширения

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

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

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

На более общем уровне будет разумно спросить: а является ли остовное дерево правильным решением для подобных задач планирования сетей? Дерево обладает тем свойством, что уничтожение любого ребра ведет к потере связности; это озна- чает, что дерево не обеспечивает защиты от сбоев. Вместо минимальной стоимости можно выбрать критерий жизнеспособности — например, искать связную сеть

с минимальной стоимостью, которая останется связной после удаления одного любого ребра.

Задачи, к которым ведут все эти расширения, существенно превосходят задачу нахождения минимального остовного дерева по вычислительной сложности. Тем не менее ввиду их практической ценности велись исследования по поиску хоро- ших эвристик в этих областях.

4.6.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Расширения:

  1. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  2. Расширение графического метода
  3. Самовоспитание как "расширение" сознания
  4. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  5. 3.12.2. Техника расширенного восприятия
  6. Расширение внутреннего кругозора
  7. 7.2.2. Расширение полноты ответа
  8. 7.2.2. Расширение полноты ответа
  9. Метод расширения сознания
  10. 2. Расширение круга наследников по закону в российском наследственном праве