Задача о покрытии методом ветвей и границ

@ALEXXSASHA · Регистрация: 22.03.2016

Студворк — интернет-сервис помощи студентам

В общем мучился, мучился, так ничего и не вышло...В институте дали задание: реализовать задачу о покрытии методом ветвей и границ на C#. Может кто-нибудь решал когда-то такую задачу или страстно обожает программирование и методы оптимизации и не знает чем заняться сегодня вечером

. Буду очень рад помощи. Описание метода:
Задача о покрытии является достаточно сложной комбинаторной задачей и на ЭВМ она чаще всего решается в два этапа. На предварительном этапе выясняется, имеет ли вообще исходная задача решение, и если оно существует, то определяется приближенное решение. Здесь же могут быть найдены элементы покрывающего множества (столбцы), включаемые в оптимальное решение, что позволяет упростить исходную задачу.
1. Постановка задачи

В матричной форме задача о покрытии формулируется следующим образом. Дана матрица A(N,M) с элементами из множества {0,1}. При этом считают, что номера строк образуют покрываемое множество, а номера столбцов - покрывающее. Требуется найти подматрицу матрицы A, которая содержит N строк (среди которых нет нулевых) и состоит из минимально возможного числа столбцов. К подобной формулировке могут быть сведены многие оптимизационные задачи управления.
2.Упрощение задачи

1)Если в какой-либо строке отсутствует единица, то этот элемент не может быть покрыт, задача не имеет решения.

2)Если в строке присутствует только одна единица, то соответствующий столбец обязательно включают в решение, он исключается из перебора задачи вместе с элементами множества, которое он покрывает.

3)Пусть есть строки: первая – подмножество второй. Тогда исключается более мощная строка.

4) Имеем два столбца: один – подмножество другого. Исключаем столбец с наименьшим количеством единиц.

3. Нахождение приближенного решения

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

- на первом шаге выделяется столбец, содержащий наибольшее число единиц (если таких несколько, то берется любой из них), и в матрице вычеркиваются (считаются покрытыми) все строки, содержащие единицу в выделенном столбце;

- на k-м шаге выполняются те же действия над матрицей, полученной (в результате вычеркивания строк) на предыдущем шаге.

Этот процесс заканчивается, если на очередном шаге все строки рассматриваемой матрицы оказались вычеркнутыми. Подматрица, составленная из тех столбцов исходной матрицы A, которые выделялись в процессе выполнения алгоритма, и является искомой подматрицей.

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

4. Oпределение оптимального решения

Полученное на предыдущем этапе приближенное решение передается алгоритму минимизации. Целью этого этапа является дальнейшее уменьшение (если это возможно) числа столбцов подматрицы.

Для определения оптимального решения, как правило, используется метод ветвей и границ.

Метод ветвей и границ при решении задачи о наименьшем покрытии:

Исходными данными для применения алгоритма является матрица, представляющая собой приближенное решение задачи о наименьшем покрытии с вычеркнутыми столбцами, включенными в оптимальное решение, и строками, которые они покрывают.

Нахождение оптимального решения задачи о наименьшем покрытии в табличной форме состоит из двух основных повторяющихся этапов.

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

В ходе выполнения первого этапа над столбцами, включенными в решение, ставят индексы, а снизу эти столбцы помечают знаком *.

Строки, содержащие единицу в столбцах, имеющих индекс и метку, считаются покрытыми.

В процессе проверки текущего решения на оптимальность индексы и метки со столбцов снимаются, после чего соответствующие строки считаются непокрытыми. Текущее решение является оптимальным, если число столбцов, входящих в него, меньше числа столбцов, включенных в предыдущее решение.

Алгоритм ветвей и границ для решения задачи о наименьшем покрытии в табличной форме состоит из следующих шагов.

1. Среди столбцов, не имеющих индекса, находится столбец, обладающий максимальной мощностью (мощностью столбца называют число единиц в нем, расположенных в непокрытых строках). Над ним указывается индекс, значение которого равно, например, числу обращений к п.1, а снизу он помечается знаком *. Покрываемые им строки отмечаются справа знаком +.

2. Находится оценка нижней границы количества столбцов L1 текущего решения как сумма числа столбцов, имеющих метку *, и числа столбцов, необходимых для покрытия непокрытых строк. Последнее определяется как минимальное число столбцов, не имеющих индекса, суммарная мощность которых больше или равна числу непокрытых строк (если мощность оказывается меньшей, то оценка нижней границы считается равной общему числу столбцов матрицы покрытий).

3. Проверяется, если число столбцов L1 текущего решения больше или равно числу столбцов L0 предыдущего решения, то переходят к п. 4, иначе, если не все строки покрыты, возвращаются к п.1. (Первоначально L0 приравнивают числу столбцов в матрице покрытий.) Если же L1<L0 и все строки покрыты, то формирование очередного допустимого решения закончено. В этом случае запоминают номера и число помеченных столбцов и переходят к проверке решения на оптимальность.

4. Проверяется, помечен ли столбец, включенный в решение последним. Если помечен, то метка с него снимается (соответствующие строки считаются непокрытыми) и переходят к п.2. Если же столбец, включенный в решение последним, не помечен, то с него снимается индекс.

5. Проверяется наличие столбцов с индексами. Если таких нет, то исследуемое решение оптимально, иначе возвращаются к п.4.

Здесь еще приведена блок-схема алгоритма:

@ALEXXSASHA · 12.12.2016, 15:05 **[ТС]**

Получается, что когда матрицу ввожу в консоли вручную результат 1, 5. А если задаю ее в коде, результат 1, 4. Как такое может быть?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
namespace SetCoverProblem
{
    class Program
    {
        static void Main(string[] args)
        {
 
          int[,] matrix = new int[8, 5] {
 
       { 1,0,0,1,1},
       { 0,0,1,1,1},
       { 1,0,1,1,0 },
        { 0,1,1,0,1 },
        { 0,1,0,0,1 },
       { 1,0,0,1,0 },
        { 0,0,0,1,1 },
        { 1,1,0,0,0 }};
            //var matrix = EnterMatrix();
            var solution = ProblemSolver.GetSolution(matrix);
            PrintSolution(solution);
        }
 
        private static void PrintSolution(List<int> solution)
        {
            Console.Write("Best solution is: ");
            Console.WriteLine(solution == null ? "<none>" : string.Join(", ", solution.Select(x => x + 1)));
            Console.ReadKey();
        }
 
        /*private static int[,] EnterMatrix()
        {
            Console.Write("Enter width: ");
            int width = int.Parse(Console.ReadLine() ?? "");
            Console.Write("Enter height: ");
            int height = int.Parse(Console.ReadLine() ?? "");
            Console.WriteLine($"Enter {height}x{width} maxtrix:");
            var matrix = new int[width, height];
            for (int y = 0; y < height; y++)
            {
                string line = Console.ReadLine() ?? "";
                int x = 0;
                foreach (var match in Regex.Matches(line, @"[01]").Cast<Match>())
                    matrix[x++, y] = int.Parse(match.Value);
            }
            return matrix;
        }
    }*/
}

@TopLayer · 12.12.2016, 15:15

ALEXXSASHA, у меня в реализации подразумевается, что первая размерность матрицы - это столбцы.
Если из кода задаёте, добавляйте

C#
1
matrix = matrix.Transpose();

@veronaka · 12.12.2016, 16:03

Здравствуйте, мне тоже нужна такая задача со стоимостями. Никто не исправлял код TopLayer? Стоимости к алгоритму не добавляли?

@TopLayer · 13.12.2016, 11:03

Запилил стоимости. Если найдёте ошибки, сообщайте.

@ALEXXSASHA · 13.12.2016, 18:13 **[ТС]**

Работает верно. Проверял на трех примерах.

Добавлено через 6 минут
Я правильно понимаю, вот пункты, которые изменились с добавлением стоимостей?
1)

Сообщение от TopLayer

на этапе упрощения матрицы. Если один столбец является подмножеством другого мы можем его удалить только если его стоимость не превосходит стоимости столбца-супермножества.

2) На этапах приближенного и оптимального значения

Сообщение от TopLayer

за текущую ценность столбца взять кол-во строк, которые он дополнительно покроет делённое на стоимость столбца. Такой выбор следующего столбца можно делать как в приближённом решении так и в основном алгоритме.

@TopLayer · 13.12.2016, 18:16

ALEXXSASHA, ну в принципе да. Еще оценка нижней границы в оптимальном алгоритме изменилась.

@ALEXXSASHA · 13.12.2016, 18:20 **[ТС]**

TopLayer, а каким образом она расчитывается здесь?

@TopLayer · 13.12.2016, 18:57

Выбирается столбец, у которого удельная цена покрытия одной строки минимальна. Эта цена умножается на количество непокрытых строк. Ну и добавляется стоимость текущего частичного решения. (Кстати код поправил, обновите)

@ALEXXSASHA · 17.12.2016, 17:34 **[ТС]**

Алгоритм рабочий. На нескольких примерах проверенный, но к большому сожалению преподаватель сказал применять другой. Тоже метод ветвей и границ, но отличается от того, что в первом посте. Ниже еще документ приложу, так как здесь формулы не отображаются.

Алгоритм включает выполнение следующих этапов.
Этап 1. Конструируется начальное множество G0 всех вариантов покрытия вершин графа. Максимальное количество вариантов решений не превышает значения 2n. Для вычисления нижней оценки множества выполняются следующие шаги.
Шаг 1.1. Для каждой і-й строки рассчитывается коэффициент , равный суммарному числу ребер‚ которые могут покрыть і-ю вершину графа
Шаг 1.2. Производится упорядочивание строк матрицы в порядке возрастания коэффициента
Шаг 1.3. Реализуется процедура определения цены покрытия
Вычисление цены покрытия базируется на следующем правиле:
из цены j-го столбца , который покрывает i-ю отроку, вычитается суммарная
цена покрытия строк с номерами , которые предшествуют строке
с номером s и покрываются j-м столбцом, a в качестве цены покрытия is –й строки выбирается минимальная цена столбца, покрывающего is-ю строку.
Шаг 1.4. Окончательно, нижняя оценка определяется как сумма цен покрытия строк матрицы

Этап 2. Производится покрытие строки.
Шаг 2.1. Исходное множество делится на у(1) подмножеств . Количество подмножеств равно числу столбцов, которые могут покрывать первую по порядку строку . Подмножество G(1.1) включает переменную x(j(1)) =1 ‚ где - номер первого по порядку столбца, который может покрывать i(1)-ю строку, , а подмножество G(1.2) включает переменную x(j(2)) ==1, где - номер второго по порядку столбца, который может покрывать i(1) -ю строку. Подмножество G(1.y(1)) включает переменную x(j(y(1))) ==1 ‚ где - номер последнего по порядку столбца, который может покрывать i(1)-ю строку
Шаг 2.2. Для каждого подмножества находится нижняя оценка , которая представляет собой сумму двух частных оценок a1 и a2 .
Первая частная оценка a1 , находится из условия, что произведено
покрытие i(i)-й строки, j(t)-м столбцом

Вторая частная оценка представляет прогноз суммарной стоимости покрытия оставшихся строк. Для ее вычисления необходимо:
определить множество U строк, которые могут покрываться j(t)-м столбцом‚
выполнить преобразования в матрице , предполагающие вычеркивание 1(1)строки , покрытие которой производится на втором этапе, а также вычеркивание j(t)-го столбца и строк, номера которых включены в множество U.
Для каждой строки преобразованной матрицы найти цену покрытия.
найти вторую частную оценку как сумму цен покрытия строк матрицы

Этап 3. В качестве конкурирующих рассматриваются вершины и из них выбирается перспективная вершина, имеющая минимальную нижнюю оценку.
Производится переход к выполнению следующей итерации‚ на которой
производится покрытие первой по порядку строки новой матрицы. Множество делится на у(2) подмножеств . Количество подмножеств равно числу столбцов в матрице , которые могут покрывать первую строку матрицы . Тогда подмножество включает две переменные x(j(t)) =1, x(j(1)) =1=1, т.е.

Нижняя оценка , подмножества равна сумме двух частных оценок a1, a2, где a1 - суммарная стоимость столбцов, включенных в покрытие, a2- прогноз суммарной стоимости покрытия строк матрицы.
Строится следующая матрица-потомок.
В качестве конкурирующих рассматриваются как вновь образованные
вершины, так и вершины, отброшенные на предыдущей итерации. Процесс ветвления продолжается до тех пор, пока не произойдет вырождение матрицы , т.е. будет выполнено покрытие всех строк походной матрицы A. При выполнении этого условия значение критерия сумма[от j=1 до n] (c(j)*x(j))->min совпадает с нижней оценкой.

@ALEXXSASHA · 17.12.2016, 18:50 **[ТС]**

TopLayer,

@TopLayer · 17.12.2016, 19:51

ALEXXSASHA, этот алгоритм совсем другой - придётся писать решение практически с нуля. К сожалению у меня нет желания тратить на это своё время.

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .

@ALEXXSASHA 1 / 1 / 1 Регистрация: 22.03.2016 Сообщений: 43

	Задача о покрытии методом ветвей и границ 06.12.2016, 20:29. Показов 10769. Ответов 30 Метки нет (Все метки) В общем мучился, мучился, так ничего и не вышло...В институте дали задание: реализовать задачу о покрытии методом ветвей и границ на C#. Может кто-нибудь решал когда-то такую задачу или страстно обожает программирование и методы оптимизации и не знает чем заняться сегодня вечером. Буду очень рад помощи. Описание метода: Задача о покрытии является достаточно сложной комбинаторной задачей и на ЭВМ она чаще всего решается в два этапа. На предварительном этапе выясняется, имеет ли вообще исходная задача решение, и если оно существует, то определяется приближенное решение. Здесь же могут быть найдены элементы покрывающего множества (столбцы), включаемые в оптимальное решение, что позволяет упростить исходную задачу. 1. Постановка задачи В матричной форме задача о покрытии формулируется следующим образом. Дана матрица A(N,M) с элементами из множества {0,1}. При этом считают, что номера строк образуют покрываемое множество, а номера столбцов - покрывающее. Требуется найти подматрицу матрицы A, которая содержит N строк (среди которых нет нулевых) и состоит из минимально возможного числа столбцов. К подобной формулировке могут быть сведены многие оптимизационные задачи управления. 2.Упрощение задачи 1)Если в какой-либо строке отсутствует единица, то этот элемент не может быть покрыт, задача не имеет решения. 2)Если в строке присутствует только одна единица, то соответствующий столбец обязательно включают в решение, он исключается из перебора задачи вместе с элементами множества, которое он покрывает. 3)Пусть есть строки: первая – подмножество второй. Тогда исключается более мощная строка. 4) Имеем два столбца: один – подмножество другого. Исключаем столбец с наименьшим количеством единиц. 3. Нахождение приближенного решения Задача о покрытии имеет решение, если в исходной матрице нет нулевых строк. Приближенным решением задачи о покрытии является подматрица матрицы A без нулевых строк с числом столбцов, близким к минимально возможному. Для нахождения приближенного решения, как правило, используется градиентный метод, который состоит в пошаговом выделении столбцов (включении в приближенное решение) результирующей матрицы: - на первом шаге выделяется столбец, содержащий наибольшее число единиц (если таких несколько, то берется любой из них), и в матрице вычеркиваются (считаются покрытыми) все строки, содержащие единицу в выделенном столбце; - на k-м шаге выполняются те же действия над матрицей, полученной (в результате вычеркивания строк) на предыдущем шаге. Этот процесс заканчивается, если на очередном шаге все строки рассматриваемой матрицы оказались вычеркнутыми. Подматрица, составленная из тех столбцов исходной матрицы A, которые выделялись в процессе выполнения алгоритма, и является искомой подматрицей. После получения приближенного решения выясняется, можно ли некоторые из столбцов включить в оптимальное решение. Это осуществляется по следующему правилу: если в какой-либо строке имеется всего один единичный элемент, то содержащий его столбец должен быть включен в оптимальное решение. При этом из подматрицы, передаваемой на оптимизацию, вычеркиваются эти столбцы и покрываемые ими элементы. 4. Oпределение оптимального решения Полученное на предыдущем этапе приближенное решение передается алгоритму минимизации. Целью этого этапа является дальнейшее уменьшение (если это возможно) числа столбцов подматрицы. Для определения оптимального решения, как правило, используется метод ветвей и границ. Метод ветвей и границ при решении задачи о наименьшем покрытии: Исходными данными для применения алгоритма является матрица, представляющая собой приближенное решение задачи о наименьшем покрытии с вычеркнутыми столбцами, включенными в оптимальное решение, и строками, которые они покрывают. Нахождение оптимального решения задачи о наименьшем покрытии в табличной форме состоит из двух основных повторяющихся этапов. На первом этапе находят одно из допустимых решений, а на втором оно проверяется на оптимальность. Если текущее решение не оптимально, то возвращаются на первый этап, где формируют новое допустимое решение, иначе алгоритм заканчивает работу. В ходе выполнения первого этапа над столбцами, включенными в решение, ставят индексы, а снизу эти столбцы помечают знаком . Строки, содержащие единицу в столбцах, имеющих индекс и метку, считаются покрытыми. В процессе проверки текущего решения на оптимальность индексы и метки со столбцов снимаются, после чего соответствующие строки считаются непокрытыми. Текущее решение является оптимальным, если число столбцов, входящих в него, меньше числа столбцов, включенных в предыдущее решение. Алгоритм ветвей и границ для решения задачи о наименьшем покрытии в табличной форме состоит из следующих шагов. 1. Среди столбцов, не имеющих индекса, находится столбец, обладающий максимальной мощностью (мощностью столбца называют число единиц в нем, расположенных в непокрытых строках). Над ним указывается индекс, значение которого равно, например, числу обращений к п.1, а снизу он помечается знаком . Покрываемые им строки отмечаются справа знаком +. 2. Находится оценка нижней границы количества столбцов L1 текущего решения как сумма числа столбцов, имеющих метку *, и числа столбцов, необходимых для покрытия непокрытых строк. Последнее определяется как минимальное число столбцов, не имеющих индекса, суммарная мощность которых больше или равна числу непокрытых строк (если мощность оказывается меньшей, то оценка нижней границы считается равной общему числу столбцов матрицы покрытий). 3. Проверяется, если число столбцов L1 текущего решения больше или равно числу столбцов L0 предыдущего решения, то переходят к п. 4, иначе, если не все строки покрыты, возвращаются к п.1. (Первоначально L0 приравнивают числу столбцов в матрице покрытий.) Если же L1<L0 и все строки покрыты, то формирование очередного допустимого решения закончено. В этом случае запоминают номера и число помеченных столбцов и переходят к проверке решения на оптимальность. 4. Проверяется, помечен ли столбец, включенный в решение последним. Если помечен, то метка с него снимается (соответствующие строки считаются непокрытыми) и переходят к п.2. Если же столбец, включенный в решение последним, не помечен, то с него снимается индекс. 5. Проверяется наличие столбцов с индексами. Если таких нет, то исследуемое решение оптимально, иначе возвращаются к п.4. Здесь еще приведена блок-схема алгоритма: 0

@veronaka 0 / 0 / 0 Регистрация: 12.12.2016 Сообщений: 1
	12.12.2016, 16:03
	Здравствуйте, мне тоже нужна такая задача со стоимостями. Никто не исправлял код TopLayer? Стоимости к алгоритму не добавляли? 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	13.12.2016, 11:03
	Запилил стоимости. Если найдёте ошибки, сообщайте. 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	13.12.2016, 18:16
	ALEXXSASHA, ну в принципе да. Еще оценка нижней границы в оптимальном алгоритме изменилась. 0

@ALEXXSASHA 1 / 1 / 1 Регистрация: 22.03.2016 Сообщений: 43
	13.12.2016, 18:20 [ТС]
	TopLayer, а каким образом она расчитывается здесь? 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	13.12.2016, 18:57
	Выбирается столбец, у которого удельная цена покрытия одной строки минимальна. Эта цена умножается на количество непокрытых строк. Ну и добавляется стоимость текущего частичного решения. (Кстати код поправил, обновите) 0

@ALEXXSASHA 1 / 1 / 1 Регистрация: 22.03.2016 Сообщений: 43
	17.12.2016, 18:50 [ТС]
	TopLayer, 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	17.12.2016, 19:51
	ALEXXSASHA, этот алгоритм совсем другой - придётся писать решение практически с нуля. К сожалению у меня нет желания тратить на это своё время. 0