Задача

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

Формально мы рассматриваем двудольный граф G = (V, E), множество узлов которого, как обычно, разбито на подмножества V = I U Y так, что один конец каждого ребра e E принадлежит I, а другой конец принадлежит Y. Кроме того, с каждым ребром e связана неотрицательная стоимость c Для паросочетания M стоимостью паросочетания называется общая стоимость всех ребер, входящих

в M, то есть Задача нахождения идеального паросочетания

с минимальной стоимостью предполагает, что 11 | = | Y | = n, и целью является поиск идеального паросочетания с минимальной стоимостью.

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

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ