всем привет.
кто-нибудь знает алгоритм решения задачи о наименьшем покрытии?
В принципе он разбирается в книжке Кристофидиса, но мне там один момент непонятен…
всем привет.
кто-нибудь знает алгоритм решения задачи о наименьшем покрытии?
В принципе он разбирается в книжке Кристофидиса, но мне там один момент непонятен…
Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.
9 марта 2008 в 14:05
ок, тогда непонятно следующее:
1) мы добавляем в B Skl. Зачем, если мы определили, что он не подходит в конечный ответ?
2) где мы хоть что-то удаляем из B? (иначе бессмысленна проверка B = Ø)
3) всё же не понятно когда алгоритм заканчивает свою работу?
а так общий принцип уже вроде начинаю понимать потихоньку…
вот книжка Кристофидиса, где рассмотрен этот алгоритм (только без опечаток) //scan-elib.narod.ru/kristofides.rar
да я тоже пытаюсь нормальное описание найти…в английской литературе в основном описан именно алгоритм для формулировки в виде линейного программирования, либо всякие приближенные алгоритмы…а этот чё-то найти пока не могу ((((
9 марта 2008 в 14:01
Как я понимаю:
1. правильно, из В` удаляем Sn` и помещаем его в В (это и есть –"отсеяли сгоряча". Т.е. гипотеза о том, что данное множество может входить в ответ не подтвердилась).
2. да, делаем "шаг назад".
сам хочу уже найти нормальное описание, тоже, но другими словами
8 марта 2008 в 23:02
потихоньку начинает доходить до тормознутых мозгов, но еще несколько вопросов, если несложно:
"удалить последнее множество, скажем, Snl" – откуда удалить, из B' или B(если из B, то тогда вообще всё непонятно)?
"положить р = l" – мы возвращаемся в тот блок, откуда удалили столбец, чтоб посмотреть следующий столбец этого блока?
что означает "Snl отсеяли сгоряча"?
8 марта 2008 в 22:05
"4) В не может привести к лучшему решению. Если B = Ø (т. е. блок 1 исчерпан), то алгоритм заканчивает работу и оптимальным решением является B′. В противном случае удалить последнее множество, скажем, Snl добавить его в В, положить р = I, поставить метку над множеством Sk+1l, удалить предшествующую метку в блоке I и перейти к шагу 3.
А что тут не понятно?
Просто сделан "откат" к предыдущему состоянию системы. Выдвигается предположение, что Snl отсеяли "сгоряча", и оно может ещё пригодиться. Перемещается указатель в начало кучи. И гипотеза опять перепроверяется, но уже с добавленной вершиной (или свойством).
8 марта 2008 в 22:05
а вообще, это действительно, вершинное NP-полное покрытие с ограничением на веса вершин.
8 марта 2008 в 22:03
нет, это не вершинное покрытие…в книжке Гэри Джонсона эта задача (точнее не эта, а задача распознавания свойств) названа МИНИМАЛЬНОЕ ПОКРЫТИЕ(она тоже НП-полна). Но мне нужен именно алгоритм нахождения этих столбцов(вершин), а не сложность алгоритма.
8 марта 2008 в 22:02
А, так это вершинное покрытие! Оно же NP-полно.
8 марта 2008 в 22:01
2Евгений Diogen Князев:
ок. ты меня убдил насчет формулировок…привожу наиболее популярные формулировки:
1)Даны множество R = { r_1,…, r_m } и семейство I = { S_1,…,S_N} множеств S_j принадлежит R для любого j . Любое подсемейство I’ = { S_j1, S_j2 ,…,S_jk}, подсемейство семейства I, такое, чтоих объединение равно R, называется покрытием множества R. Каждому подмножествуS_j принадлежащего I поставлена в соответствие (положительная) стоимость c_j .Найти покрытие множества R, имеющее наименьшую стоимость, причем стоимость семейства I’определяется как сумма по всем c_ji .
2)Дана булева матрица T: array [1…M, 1…M] of 0…1. Каждому столбцу прописан вес. Найти такое множество столбцов минимальной стоимости, чтобы любая строка содержала единицу хотя бы в одном из выбранных столбцов.
3)Пусть дан граф, в котором каждой вершине сопоставлена некоторая цена.
Требуется найти доминирующее множество вершин этого графа с наименьшей суммарной ценой.
Насчет доков матлабов даже не подумал, спасибо, обязательно посмотрю. Мне это запрограммировать не нужно…просто алгоритм понять и всё.
А насчет "//rain.ifmo.ru/cat/view.php/theory/graph-colori" ты прав, это та самая задача, которая нужна. Но там всё слово в слово скопировано из Кристофидиса (к тому же с очепятками), но в этом алгоритме я не могу понять шаг номер 4:
"4) В не может привести к лучшему решению. Если B = Ø (т. е. блок 1 исчерпан), то алгоритм заканчивает работу и оптимальным решением является B′. В противном случае удалить последнее множество, скажем, Snl добавить его в В, положить р = I, поставить метку над множеством Sk+1l, удалить предшествующую метку в блоке I и перейти к шагу 3. "
В любом случае огромное спасибо, что пытаешься помочь!!
2) Максим Шестаков Золотарёв:
честно говоря особо и не вникал конкретно что не так с симплекс-методом(просмотрел вскольз), вроде в этом проблема и есть. Но, к сожалению, данный алгоритм мне нужен для того, чтобы в дальнейшем поместить его в учебнике по дискретной математике для студентов второго курса, а к этому времени они не проходили раздел линейного программирования (((( Но всё равно спасибо, что указал как решить проблему, для себя обязательно посмотрю.
8 марта 2008 в 21:04
У Д.Кнута этот метод рассматривался.
А просил я формулировку по одной простой причине — метод один, а названий несколько. Или реализация медода в каком-либо статистическом, математическом или ином пакете/классе.
Для начала, предложу не изобретать велосипед, а поглядеть доки MathLABa (например) на предмет подходящего. А уже к этому подключиться из языка программирования.
Нашел вполне грамотное описание данной задачи + примеры + алгоритм:
//rain.ifmo.ru/cat/view.php/theory/graph-colori...
8 марта 2008 в 21:01
Если проблема в применении симплекс-метода только в дробных решениях – то для борьбы с ними применяется метод ветвей и границ.
Поищи в инете
"Метод ветвей и границ решения задач целочисленного линейного программирования"
"Метод Лэнг и Дойг"
8 марта 2008 в 20:05
эту задачу можно сформулировать как задачу линейного программирования. Но симплекс метод – решения не даст (по крайней мере в его первоначальном виде), ибо он может дать вещественные решения, что недопустимо в данной задаче…вообщем-то мне это и не нужно, есть более простые алгоритмы для ее решения.
А точную формулировку задачи я не дал по простой причине: я понимаю, что щас мало кто будет с нуля придумывать алгоритм для ее решения (да и не надо, над этой задачей уже думали умные дядьки), я просто хочу узнать слышали ли народ про эту задачу, и если да, то тогда и начну задавать конкретные вопросы.
8 марта 2008 в 19:03
Для тех кто в танке: что такое "покрытие". Может эту задачу можно свести к задаче линейного (нелинейного) программирования?
з.ы. книжку некоего Кристо….в глаза не видел, так что учимся задавать вопросы.