Войти
В теории графов и комбинаторной оптимизации замыкание ориентированного графа представляет собой набор вершин с нет исходящих ребер. То есть граф не должен иметь ребер, которые начинаются внутри замыкания и заканчиваются вне замыкания. Задача замыкания - это задача нахождения замыкания с максимальным или минимальным весом в ориентированном графе, взвешенном по вершинам. Это может быть решено за полиномиальное время с использованием сведения к задаче максимального расхода. Его можно использовать для моделирования различных прикладных задач по выбору оптимального подмножества задач для выполнения с зависимостями между парами задач, один из примеров - разработка открытых карьеров.
Замыкание с максимальным весом данного графа G совпадает с дополнением к замыканию с минимальным весом на транспонировать граф из G, так что две задачи эквивалентны по вычислительной сложности. Если две вершины графа принадлежат одной и той же компоненте сильной связности, они должны вести себя так же, как друг друга по отношению ко всем замыканиям: замыкание не может содержать одну вершину, не содержащую другую. По этой причине входной граф для задачи замыкания может быть заменен его сгущением, в котором каждая сильно связная компонента заменяется одной вершиной. Конденсация всегда представляет собой направленный ациклический граф.
Снижение от закрытия до максимального потока Как показал Пикард (1976), замыкание с максимальным весом может быть полученный из G решением задачи о максимальном потоке на графе H, построенном из G путем добавления к нему двух дополнительных вершин s и t. Для каждой вершины v с положительным весом в G расширенный граф H содержит ребро из s в v с емкостью, равной весу v, а для каждой вершины v с отрицательным весом в G расширенный граф H содержит ребро из v к t, пропускная способность которого равна отрицанию веса v. Всем ребрам в G задана бесконечная пропускная способность в H.
A минимальный разрез, отделяющий s от t в этом графе, не может иметь ребер G, проходящих в графе прямое направление поперек пропила: пропил с такой кромкой имел бы бесконечную пропускную способность и не был бы минимальным. Следовательно, множество вершин на той же стороне разреза, что и s, автоматически образует замыкание C. Вместимость разреза равна весу всех вершин с положительным весом минус вес вершин в C, который минимизируется, когда вес C максимизируется. Согласно теореме о максимальном потоке и минимальном разрезе минимальный разрез и полученное из него оптимальное замыкание могут быть найдены путем решения задачи максимального потока.
Также изучались альтернативные алгоритмы для задачи максимального замыкания, не вычисляющие потоки. Их время работы аналогично времени работы самых быстрых из известных алгоритмов потока.
Горный карьер можно моделировать как набор блоков материала который может быть удален путем майнинга после удаления всех блоков непосредственно над ним. Блок имеет общую стоимость, равную стоимости полезных ископаемых, которые могут быть извлечены из него, за вычетом затрат на извлечение и добычу; в некоторых случаях блок не имеет значения извлечения, но его все же необходимо удалить, чтобы достичь других блоков, что дает ему отрицательное значение. Можно определить ациклическую сеть, вершинами которой являются блоки шахты, с ребром от каждого блока к блокам над ним, которые должны быть удалены раньше него. Вес каждой вершины в этой сети - это общая стоимость ее блока, и наиболее прибыльный план майнинга может быть определен путем нахождения максимального веса закрытия и последующего формирования топологического упорядочивания блоков в этой сети. закрытие.
В военных операциях важные цели, такие как командные центры, часто защищены уровнями систем защиты, которые, в свою очередь, могут быть защищены другими системами. Чтобы достичь цели, необходимо снять все ее защиты, превратив ее во вторичную цель. Каждой цели необходимо выделить определенное количество ресурсов для успешной атаки. Оптимальный набор целей для атаки, позволяющий получить максимальную отдачу от затраченных ресурсов, можно смоделировать как проблему закрытия.
Проблема планирования системы доставки грузов может моделироваться сетью, в которой вершины представляют города, а (неориентированные) ребра представляют потенциальные маршруты доставки грузов между парами городов. Каждый маршрут может принести определенную прибыль, но его можно использовать только в том случае, если грузовые депо построены на обоих его концах с определенной стоимостью. Проблема проектирования сети, которая максимизирует разницу между прибылью и затратами, может быть решена как проблема замыкания путем разделения каждого неориентированного ребра на два направленных ребра, оба направленных наружу от точки подразделения. Вес каждой точки подразделения - положительное число, прибыль соответствующего маршрута, а вес каждой исходной вершины графа - отрицательное число, стоимость строительства депо в этом городе. Вместе с открытой разработкой это было одно из первых мотивирующих приложений для изучения проблемы закрытия; первоначально он был изучен в 1970 году в двух независимых статьях, опубликованных в том же номере того же журнала JMW Rhys и Мишель Балински.
Сидни (1975) и Лоулер ( 1978) описывают применение проблемы закрытия к версии планирования работы цеха, в которой каждому дается набор задач, которые должны быть запланированы для выполнения, по одной за раз. С каждой задачей связано два числа: вес или приоритет и время обработки, то есть время, необходимое для выполнения этой задачи. Кроме того, у задач есть ограничения приоритета: одни задачи должны выполняться раньше других. Эти ограничения предшествования могут быть описаны направленным ациклическим графом G, в котором переход от одной задачи к другой указывает, что первая задача должна быть выполнена раньше, чем вторая. Цель состоит в том, чтобы выбрать порядок, соответствующий этим ограничениям (топологический порядок G), который минимизирует общее взвешенное время выполнения задач.
Хотя (как показывает Лоулер) это Задача планирования является NP-полной в общем, Сидни описывает метод декомпозиции, который может помочь решить проблему, сведя ее к нескольким более мелким задачам того же типа. В частности, если S является подмножеством задач, которое (среди всех подмножеств) имеет максимально возможное отношение его общего веса к общему времени обработки, и, кроме того, S является минимальным среди всех наборов с таким же соотношением, тогда существует оптимальный график, в котором все задачи в S выполняются перед всеми другими задачами. Пока S не является полным набором задач, это разделение задач разделяет проблему планирования на две меньшие задачи: одну из планирования S и одну из оставшихся задач. Хотя S является замыканием (для графа с перевернутыми ребрами из G), проблема поиска S не совсем проблема замыкания с максимальным весом, потому что значение S является отношением, а не суммой весов. Тем не менее, Лоулер показывает, что S можно найти за полиномиальное время с помощью алгоритма бинарного поиска , в котором каждый шаг поиска использует экземпляр задачи закрытия в качестве подпрограммы.
