4551
правка
Задача присваивания: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 58: | Строка 58: | ||
Более эффективная реализация | Более эффективная реализация | ||
Определим провис ребра следующим образом: | |||
slack(x; y) = l(x) + l(y) - w(x; y) : Тогда | |||
Я = min slack(x; y): | |||
x2S;y2T | |||
Интуитивно кажется, что вычисление Я требует O(n2) времени. Для каждой вершины y 2 T отметим ребро с минимальным провисом, т.е. | |||
slack[y] = min slack(x; y): | |||
x2S | |||
Вычисление slack[y] для всех y 2 T требует O(n2) времени в начале этапа. По мере продвижения по данному этапу все значения провисов легко обновляются за время O(n), поскольку все они изменяются на одну и ту же величину (метки вершин из S уменьшаются равномерным образом). При перемещении вершины u из S в S необходимо перевычислить провисы вершин в T, что требует O(n) времени. Однако перемещать вершину из S в S можно не более n раз. | |||
Таким образом, каждый этап может быть реализован за время O(n2). Поскольку имеется n этапов, общее время выполнения составляет O(n3). Для разреженных графов есть способ реализации алгоритма с временем выполнения O(n(m + n log n)) с использованием min потоков минимальной стоимости [ ], где m – количество ребер. | |||
== Применение == | |||
Паросочетание в двудольных графах имеет множество областей применения – например, при планировании заданий единичной длины с целочисленными значениями времени запуска и предельного срока окончания, даже в присутствии штрафных санкций, зависящих от времени. | |||
== Открытые вопросы == | |||
Необходимо разработать алгоритм с линейным или близким к линейному временем выполнения. | |||
== Литература == | |||
Некоторые книги, посвященные комбинаторной оптимизации, включают описания алгоритмов поиска паросочетания во взвешенных двудольных графах (см. [2, 5]). Также информацию об этом можно найти в статье Габова [3]. | |||
1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993) | |||
2. Cook, W., Cunningham, W., Pulleyblank,W., Schrijver,A.: Combinatorial Optimization. Wiley, New York (1998) | |||
3. Gabow, H.: Data structures for weighted matching and nearest common ancestors with linking. In: Symp. on Discrete Algorithms, 1990, pp. 434-443 | |||
4. Kuhn, H.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2,83-97 (1955) | |||
5. Lawler, E.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston (1976) | |||
6. Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5, 32-38 (1957) | |||
