Проблема закрытия - Closure problem

В теория графов и комбинаторная оптимизация, а закрытие из ориентированный граф это набор вершин C, такие, что никакие края не выходят C. В проблема закрытия является задачей поиска замыкания с максимальным или минимальным весом в ориентированном графе, взвешенном по вершинам.[1][2]Ее можно решить за полиномиальное время, используя редукцию к проблема максимального расхода. Его можно использовать для моделирования различных прикладных задач по выбору оптимального подмножества задач для выполнения с зависимостями между парами задач, один из примеров приведен в открытый карьер.

Алгоритмы

Конденсация

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

Снижение до максимального расхода

Снижение от закрытия до максимального потока

В качестве Пикард (1976) показал,[2][3]закрытие максимального веса может быть получено из грамм решив проблема максимального расхода на графике ЧАС построен из грамм добавив к нему две дополнительные вершины s и т. Для каждой вершины v с положительным весом в грамм, расширенный граф ЧАС содержит край из s к v вместимостью равной весу v, а для каждой вершины v с отрицательным весом в грамм, расширенный граф ЧАС содержит край из v к т чья вместимость - это отрицание веса v. Все края в грамм даны бесконечные емкости в ЧАС.[1]

А минимальный разрез разделение s из т в этом графе не может быть ребер из грамм проходящий в прямом направлении поперек пропила: пропил с такой кромкой имел бы бесконечную пропускную способность и не был бы минимальным. Следовательно, множество вершин на той же стороне разреза, что и s автоматически образует закрытие C. Емкость разреза равна весу всех вершин с положительным весом минус вес вершин в C, которая минимизируется, когда вес C максимально. Посредством теорема о максимальном потоке и минимальном отсечении, минимальный разрез и полученное из него оптимальное закрытие могут быть найдены путем решения задачи максимального потока.[1]

Альтернативные алгоритмы

Также были изучены альтернативные алгоритмы задачи максимального замыкания, не вычисляющие потоки.[4][5][6] Их время работы похоже на время работы самых быстрых известных алгоритмов потока.[4]

Приложения

Открытая разработка

Разрез карьера можно смоделировать как набор блоков материала, которые могут быть удалены путем его добычи после того, как все блоки непосредственно над ним будут удалены. Блок имеет общую стоимость, равную стоимости полезных ископаемых, которые могут быть извлечены из него, за вычетом затрат на извлечение и добычу; в некоторых случаях блок не имеет значения извлечения, но его все же необходимо удалить, чтобы достичь других блоков, что дает ему отрицательное значение. Можно определить ациклическую сеть, имеющую в качестве вершин блоки шахты, с ребром от каждого блока до блоки над ним, которые необходимо удалить раньше. Вес каждой вершины в этой сети - это общая стоимость ее блока, и наиболее прибыльный план майнинга можно определить, найдя максимальное закрытие по весу, а затем сформировав топологический порядок блоков в этом закрытии.[1][5][7]

Военная цель

В ходе военных операций важные цели, такие как командные центры, часто защищены уровнями систем защиты, которые, в свою очередь, могут быть защищены другими системами. Чтобы достичь цели, необходимо снять все ее защиты, превратив ее во вторичную цель. Каждой цели необходимо выделить определенное количество ресурсов для успешной атаки. Оптимальный набор целей для атаки, чтобы получить максимальную отдачу от затраченных ресурсов, можно смоделировать как проблему закрытия.[1][8]

Проектирование транспортной сети

Проблема планирования системы доставки грузов может быть смоделирована сетью, в которой вершины представляют города, а (ненаправленные) ребра представляют потенциальные маршруты доставки грузов между парами городов. Каждый маршрут может принести определенную прибыль, но его можно использовать только в том случае, если грузовые депо построены на обоих его концах с определенной стоимостью. Проблема проектирования сети, которая максимизирует разницу между прибылью и затратами, может быть решена как проблема замыкания путем разделения каждого неориентированного ребра на два направленных ребра, оба направленных наружу от точки подразделения. Вес каждой точки подразделения - положительное число, прибыль соответствующего маршрута, а вес каждой исходной вершины графа - отрицательное число, стоимость строительства депо в этом городе.[1][9] Вместе с открытой разработкой это было одно из первых мотивирующих приложений для изучения проблемы закрытия; первоначально он был изучен в 1970 году в двух независимых статьях, опубликованных в одном номере того же журнала Дж. М. У. Рисом и Мишель Балински.[9][10][11]

Планирование работы

Сидни (1975) и Лоулер (1978) описать приложение проблемы закрытия к версии планирование работы цеха в котором каждому дается набор задач, которые необходимо запланировать для выполнения, по одной за раз. С каждой задачей связано два числа: вес или приоритет и время обработки, то есть время, необходимое для выполнения этой задачи. Кроме того, у задач есть ограничения приоритета: одни задачи должны выполняться раньше других. Эти ограничения предшествования можно описать ориентированным ациклическим графом грамм в котором переход от одной задачи к другой указывает, что первая задача должна быть выполнена раньше, чем вторая. Цель состоит в том, чтобы выбрать порядок, соответствующий этим ограничениям ( топологический порядок из грамм), который минимизирует общее взвешенное время выполнения задач.[12][13]

Хотя (как показывает Лоулер) эта проблема планирования НП-полный В общем, Сидни описывает метод декомпозиции, который может помочь решить проблему, сведя ее к нескольким более мелким задачам того же типа. В частности, если S представляет собой подмножество задач, которое (среди всех подмножеств) имеет максимально возможное отношение общего веса к общему времени обработки, и, кроме того, S минимально среди всех множеств с одинаковым соотношением, то существует оптимальное расписание, в котором все задачи из S выполняются перед всеми другими задачами. Так долго как S не весь набор задач, это разделение задач разбивает задачу планирования на две меньшие задачи, одна из которых S и одно из планирования оставшихся задач.[12] Несмотря на то что S является замыканием (для графа с обращенными ребрами из грамм) проблема поиска S не совсем проблема закрытия максимального веса, потому что значение S это соотношение, а не сумма весов. Тем не менее Лоулер показывает, что S можно найти за полиномиальное время с помощью бинарный поиск алгоритм, в котором каждый шаг поиска использует экземпляр проблемы закрытия в качестве подпрограммы.[13]

Рекомендации

  1. ^ а б c d е ж Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993), «19.2 Максимальное замыкание графика по весу», Сетевые потоки, Englewood Cliffs, NJ: Prentice Hall Inc., стр. 719–724, ISBN  0-13-617549-X, МИСТЕР  1205775.
  2. ^ а б Кук, Уильям Дж.; Каннингем, Уильям Х .; Pulleyblank, Уильям Р.; Шрайвер, Александр (2011), «Оптимальное замыкание в орграф», Комбинаторная оптимизация, Ряд Уайли по дискретной математике и оптимизации, 33, John Wiley & Sons, стр. 49–50, ISBN  9781118031391.
  3. ^ Пикар, Жан-Клод (1976), "Максимальное замыкание графа и приложения к комбинаторным задачам", Наука управления, 22 (11): 1268–1272, Дои:10.1287 / mnsc.22.11.1268, МИСТЕР  0403596.
  4. ^ а б Хохбаум, Дорит С. (2001), «Новый-старый алгоритм для минимального сокращения и максимального потока в графах замыкания», Сети, 37 (4): 171–193, Дои:10.1002 / нетто.1012, МИСТЕР  1837196.
  5. ^ а б Lerchs, H .; Гроссманн, И. Ф. (1965), "Оптимальная конструкция карьеров", Труды Канадского горно-металлургического института, 68: 17–24. Как цитирует Хохбаум (2001).
  6. ^ Фааланд, Брюс; Ким, Кисеог; Шмитт, Том (1990), "Новый алгоритм вычисления максимального замыкания графа", Наука управления, 36 (3): 315–331, Дои:10.1287 / mnsc.36.3.315.
  7. ^ Джонсон, Т. Б. (1968), Оптимальное планирование добычи в карьере, Технический отчет, Калифорнийский университет, Беркли, Калифорния. Как цитирует Ахуджа, Маньянти и Орлин (1993).
  8. ^ Орлин, Д. (1987), "Оптимальное размещение оружия против многоуровневой защиты", Ежеквартально по военно-морской логистике, 34 (5): 605–617, Дои:10.1002 / 1520-6750 (198710) 34: 5 <605 :: aid-nav3220340502> 3.0.co; 2-л. Как цитирует Ахуджа, Маньянти и Орлин (1993).
  9. ^ а б Хохбаум, Дорит (2004), «Статья к 50-летию: выбор, предоставление, общие фиксированные затраты, максимальное закрытие и последствия для алгоритмических методов сегодня», Наука управления, 50 (6): 709–723, Дои:10.1287 / mnsc.1040.0242.
  10. ^ Рис, Дж. М. У. (1970), "Проблема выбора общих фиксированных затрат и сетевых потоков", Наука управления, 17 (3): 200–207, Дои:10.1287 / mnsc.17.3.200.
  11. ^ Балински, М.Л. (1970), «О проблеме отбора», Наука управления, 17 (3): 230–231, Дои:10.1287 / mnsc.17.3.230.
  12. ^ а б Сидни, Джеффри Б. (1975), "Алгоритмы декомпозиции для последовательного выполнения на одной машине с отношениями предшествования и отложенными затратами", Исследование операций, 23 (2): 283–298, Дои:10.1287 / opre.23.2.283.
  13. ^ а б Лоулер, Э. (1978), «Последовательность заданий для минимизации общего взвешенного времени выполнения с учетом ограничений приоритета», Анна. Дискретная математика., Анналы дискретной математики, 2: 75–90, Дои:10.1016 / S0167-5060 (08) 70323-6, ISBN  9780720410433, МИСТЕР  0495156.