Метод "ветвей и границ"

ssd80

Hi, All!
Кто знаком с методом "ветвей и границ"? Может, кто расскажет, в чем он состоит или где про него почитать?
Это так называемый метод оптимального покрытия. Алгоритм Петрика из той же области.
Мне надо из некоторого количества элементов-классов выбрать по определенному условию минимально возможное количество.

shpanenoc

Метод ветвей и границ - общий способ организации полного перебора. Для каждой конкретной задачи подбирается своя процедура ветвления и оценочная функция, так что я думаю, надо искать реализацию метода для данной задачи.
Вики: http://ru.wikipedia.org/wiki/%CC%E5%F2%EE%E4_%E2%E5%F2%E2%E5...

ssd80

Мда... слишком уж это обще; примерно ясна идея и так... А вот реализация :(
У меня есть набор классов, в каждом из которых есть определенное количество элементов, от 1 до 5 в среднем. Всего таких элементов допустим n, классов k. Элементы в классах повторяются, в различных сочетаниях. Мне надо выбрать минимальное количество классов так, чтобы в итоге все элементы были представлены в финальном наборе классов.

svetik5623190

Прям все-все обязательно? В противном случае можно было бы попробовать использовать методы, дающие ответ с некоторой долей вероятности. Это должно быть быстрее, чем ПОЛНЫЙ перебор.

ssd80

Угу :( Условие полноты должно быть соблюдено. Потом еще получившийся класс (вариантов может быть несколько; в моем случае из оригинальных 42 классов я выбрал руками навскидку 17, мне надо бы поменьше, чтобы в 4 бита уложиться.) надо на условие замкнутости проверить, т.е. еще не факт что получившийся вариант подойдет :(
Вот пример:
_______|_0_|_1_|_2_|_3_|_4_|_5_|
(0,2,4,5)|_1_|___|_1_|___|_1_|_1_|
(0,3,4,5)|_1_|___|___|_1_|_1_|_1_|
(1,3,4,5)|___|_1_|___|_1_|_1_|_1_|
в таком представлении задачу можно сформулировать так:
В таблице слева записаны классы, сверху - все элементы классов. Если данный элемент входит в класс, на пересечении ставится "1" или что угодно. Нужно выбрать минимальное количество строк так, чтобы в каждом столбце хотя бы одна единица была. В данном случае это первая и третья строки.

seregaohota

Может быть прокатит что-то типа алгоритма Эйлера о нахождении пути обхода конём шахматной доски, когда конём ходят на ту клетку с которой меньше путей отхода.
Такой вариант перебора фактически.
n = 0 - количество уже выбранных множеств.
1. Выбираешь доступный элемент, который принадлежит к минимальному количеству классов, если это 0 - то построить не удалось. Иначе n=n+1 и переход к 2.
2. Выкинуть из множнества все уже покрытые элементы.
3. Если элементов больше нет - печать решения. (И откатка к пункту 1 с выкидыванием последнего, если хочешь все решения). Если есть - перейти к пункту 1.

ssd80

Хм, похоже. Задача о коммивояжере тоже из этой оперы; только вот никак не соображу, как приложить к моей задаче;
"Выбираешь доступный элемент, который принадлежит к минимальному количеству классов" т.е., который принадлежит к как можно меньшему кол-ву классов? Надо попробовать; возможно, найду еще какие-либо дополнительные ограничения, которые уменьшат перебор.

ETrohkina

Мы реализовали подобные деревья для поиска хороших предикторов в скоринге.
Могу дать контакт автора (в приват).

seregaohota

Второй вариант - использовать жадный алгоритм, на 1 шаге выбирается подмножество, содержащее максимальное число элементов.
Вот здесь почитай Методы решения труднорешаемых задач
Пример 3. Задача о покрытии множествами
PS Это NP-полные задачи с кучей локальных минимумов энергии. Самый продвинутый алгоритм IMHO в этой области - метод имитации отжига, он более или менее глобальный минимум находит. Но он тебе вряд ли тут нужен, да и сложный он, фиктивная температура вводится и идея как в кристаллической решётке при остывании металла из расплава - если подождать и температуру медленно снижать и дать возможность атомам с некоторой вероятностью пропорциональной температуре разбежаться по узлам решётки - то получим глобальный минимум, иначе как при быстром остывании - получаем аморфное стекло не в глобальном, а в локальном минимуме. Хотя металлические стёкла в бритвах используются, но тебе они без надобности тут :) Насколько знаю IBM им провода по печатным платам уж лет 10 раскидывает.

ssd80

Всем спасибо, реализовал простым перебором, по времени оказалось терпимо.
Потом, когда буду решать задачу бОльшего объема, еще поуточняю ;)
Оставить комментарий
Имя или ник:
Комментарий: