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