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

В общем мучился, мучился, так ничего и не вышло...В институте дали задание: реализовать задачу о покрытии методом ветвей и границ на 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

Сообщение от ALEXXSASHA Если же столбец, включенный в решение последним, не помечен, то с него снимается индекс.

Это на какой стадии алгоритма у нас может появиться непомеченый индексированный столбец?

0

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

0

Ну что, если у кого-нибудь мысли как это реализовать?

0

Кажется начал въезжать. Индексация используется, чтобы убрать рекурсию. Вот что понял (как мне кажется):
1) Если столбец не имеет индекса и метки - то относительно его присутствия в решении мы ничего не знаем. (Изначально так со всеми столбцами)
2) Если столбец имеет индекс и метку - означает, что сейчас мы ищем решения в которых этот столбец обязательно присутствует.
3) Если столбец имеет индекс, но не имеет метки - означает, что сейчас мы ищем решения в которых этот столбец обязательно отсутствует.
4) Не может быть так, чтобы у столбца была метка и не было индекса.

0

Добавлено через 38 секунд
TopLayer, Воооот, это проясняет что-то. А еще в данном описании это никак не фигурирует, но вообще у каждого столбца имеется стоимость. Задается массивом. В данном случае считается, что стоимости всех столбцов равны между собой. А вот если они различаются, то нужно выбирать в качестве оптимального такое сочетание столбцов, чтобы сумма их стоимостей ->min Хорошо, если получится так, что существует только один вариант покрытия, а вот если их несколько? Тогда и нужно проверять по стоимостям. В каком моменте это условие должно проверятся?

0

Сообщение от ALEXXSASHA А еще в данном описании это никак не фигурирует, но вообще у каждого столбца имеется стоимость. Задается массивом.

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

Сообщение от ALEXXSASHA а вот если их несколько?

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

0

Т. е. Делать задачу без упрощений, начиная с поиска приближенного значения?

Добавлено через 4 минуты

Сообщение от TopLayer то это упрощение некорректно

А почему же некорректно? Есть еще другой алгоритм, он изначально подразуменвает стоимость. И упрощение там такое же есть.
Постановка задачи

ЗНП своим названием обязана следующей теоретико-множественной интерпретации. Даны множество R = {r1, …, rM} и семейство I = {S1, …, SN} множеств Sj ⊂ R. Любое подсемейство I′ = {Sj1, Sj2, …, Sjk} семейства I, такое, что

∪i = 1…k Si = R (12)
называется покрытием множества R, а множества Sji называются покрывающими множествами. Если вместе с соотношением (12) I′ удовлетворяет условию

Sjh ∩ Sjl = Ø, ∀h, l ∈ {1, …, k} (13)
т. е. множества Sji {i = 1, …, k} попарно не пересекаются, то называется разбиением множества R.

Если каждому Sj ∈ I поставлена в соответствие положительная стоимость cj, то ЗНП формулируется так: найти покрытие множества R, имеющее наименьшую стоимость, причем стоимость семейства I′ = {Sj1, …, Sjk} определяется как ∑i = 1k cji. Аналогично формулируется и задача о наименьшем разбиении (ЗНР).

Упрощение задачи

Вследствие особой природы ЗНП часто удается сделать при ее исследовании определенные, хорошо известные заранее выводы и упрощения. Например:

если для некоторого элемента ri из R справедливы соотно шения ri ∉ Sj ∀ j = 1, …, N, то ri покрыть нельзя и, следова тельно, задача не имеет решения;
если ∃ri ∈ R такое, что ri ∈ Sk и ri ∉ Sj, то Sk должно присутствовать во всех решениях и задачу можно свести к меньшей, положив R = R − {ri} и I = I − {Sk}
пусть Vi = {j | ri, ∈ Sj}; тогда если ∃p, q ∈ {1, …, M} такие, что Vp ⊆ Vq, то rq можно удалить из R, поскольку любое множество, которое покрывает rp, должно также покрывать rq, т. е. rp доминирует над rq;
если для некоторого семейства множеств I′ ⊂ I справедливы соотношения ∪Sj∈I′Sj ⊇ Sk и ∑Sj∈I′ cj ≤ Sk для любых Sk ∈ I − I′, то Sk может быть вычеркнуто из I поскольку ∪Sj∈I′Sj доминирует над Sk.
Предположим, что все эти упрощения выполнены (если они возможны) и что исходная ЗНП уже переформулирована в соответствующей неприводимой форме.

Алгоритм решения ЗНР, использующий дерево поиска

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

Простые методы решения ЗНР, использующие дерево поиска, были предложены Пирсом, Гарфинкелем и Немхаузеро.

Сущность этих методов такова. Вначале строятся "блоки" столбцов, по одному на каждый элемент rk из R, т. е. всего М блоков, k-й блок состоит из таких множеств семейства I (представленных столбцами), в которых содержится элемент ri, но отсутствуют элементы с меньшими индексами — r1, …, rk−1. Следовательно, каждое множество (столбец) появляется точно в одном определенном блоке и совокупность блоков может быть представлена в виде таблицы. В конкретных задачах некоторые из блоков могут отсутствовать.


В процессе работы алгоритма блоки отыскиваются последовательно и формирование k-гo блока начинается после того, как каждый элемент ri 1 ≤ i ≤ k − 1, будет покрыт частным решением. Таким образом, если какое-то множество в блоке k содержит элементы с индексами, меньшими k, то оно должно быть отброшено (на этом этапе) в соответствии с требованием неперекрываемости. Множества в пределах каждого блока размещаются в порядке возрастания их стоимостей и перенумеровываются так, что Sk теперь уже обозначает множество, соответствующее j-му столбцу таблицы.

Текущее "наилучшее" решение B′ сo стоимостью z′ известно на любом этапе поиска (B′ обозначает семейство соответствующих покрывающих множеств). Если В и z — соответствующие семейство и стоимость на данной стадий поиска, а Е — множество, представляющее те элементы (т. е. строки) ri, которые покрываются множествами из В, то одна из простых алгоритмов, использующих дерево поиска, можно вписать следующим образом.

Построить исходную таблицу и начать с частного решения: B = Ø, E = Ø, z = 0, z′ = ∞.
Найти р = min[i |ri ∉ E]. Над блоком р поставить метку (над его первым множеством, которое, как следует из построения таблицы, имеет наименьшую стоимость).
Начиная с отмеченной позиции в блоке р, перебирать его множества Sjp скажем, в порядке возрастания индекса j.
(i) Если найдено множество Sjp, такое, что Sjp ∩ E = Ø и z + cjp < z′ (где cjp — стоимость множества Sjp), то перейти к шагу 5.
В не может привести к лучшему решению. Если B = Ø (т. е. блок 1 исчерпан), то алгоритм заканчивает работу и оптимальным решением является B′. В противном случае удалить последнее множество, скажем, Snl добавить его в В, положить р = I, поставить метку над множеством Sk+1l, удалить предшествующую метку в блоке I и перейти к шагу 3.
Обновить данные: B = B ∪ {Sjp}, E = E ∪ Sjp, z = z + cjp. Если найдено лучшее решение Е = R, то положить B′ = B, z′ = z и перейти к шагу 4. Иначе перейти к шагу 2.
Если поиск оканчивается с исчерпыванием блока 1 (см. шаг 4), то целесообразно переставить блоки в порядке возрастания числа столбцов (множеств) в каждом блоке. Это может быть осуществлено (перед построением исходной таблицы) перенумерацией элементов (строк) r1 … rM в порядке увеличения числа множеств из S, содержащих соответствующие элементы.

0

Сообщение от ALEXXSASHA А почему же не корректно?

Некорректен только этот пункт:

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

0

ALEXXSASHA, я написал решение этой задачи, без учёта стоимости столбцов. Код тут:
https://github.com/UnresolvedE... verProblem

0

Спасибо вам большое Алгоритм есть! Буду пытаться добавить стоимость и надо это переделать на Findows Forms будет.

Добавлено через 17 часов 7 минут
TopLayer, Получается, что стоимость нужно учитывать уже на этапе нахождения приближенного решения

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

Т.е если таких столбцов несколько, то будет выделяться не любой из них, а тот, у которого стоимость меньше?

0

Сообщение от ALEXXSASHA Получается, что стоимость нужно учитывать уже на этапе нахождения приближенного решения

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

Сообщение от ALEXXSASHA Т.е если таких столбцов несколько, то будет выделяться не любой из них, а тот, у которого стоимость меньше?

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

0

Т.е получается, что столбцы все-таки надо удалять при упрощении, только условие его удаления немного меняется? С этого :

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

На это:

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

А то я изначально понял, что 4й пункт упрощения совсем не нужен

0

ALEXXSASHA, да, этот пункт просто изменится.

0

Сейчас проверял программу на примере:


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

результат был 1, 4

Хотя, ни 1 ни 2 столбец не покрывают 5 строку

Добавлено через 9 минут
Вопрос снят. Здесь нумерация с нуля, я так понимаю

Добавлено через 7 минут
Хотя все-таки вопрос актуален. 1, 4 не покрывают строку 3

1

ALEXXSASHA, был неверный алгоритм восстановления первоначальных индексов. Поправил.

0

Все равно в данном случае результат 1, 4 А должен быть либо 2, 4 либо 1, 5

0

ALEXXSASHA, версия на github выдаёт 1, 5. Обновите.

0

Может я конечно туплю, но результат все же 1, 4. Несколько раз перепроверял (обновлял и скачивал).

0

ALEXXSASHA, заново скачал проект с github и запустил. Результат 1, 5. Думайте, что не так сделали.

0