singlepost

кто-нить знает алгоритм? << На главную или назад  

всем привет.
кто-нибудь знает алгоритм решения задачи о наименьшем покрытии?
В принципе он разбирается в книжке Кристофидиса, но мне там один момент непонятен…

12 ответов в теме “кто-нить знает алгоритм?”

  1. 12
    Овак Мяса ответил:

    ок, тогда непонятно следующее:

    1) мы добавляем в B Skl. Зачем, если мы определили, что он не подходит в конечный ответ?
    2) где мы хоть что-то удаляем из B? (иначе бессмысленна проверка B = Ø)
    3) всё же не понятно когда алгоритм заканчивает свою работу?

    а так общий принцип уже вроде начинаю понимать потихоньку…

    вот книжка Кристофидиса, где рассмотрен этот алгоритм (только без опечаток) //scan-elib.narod.ru/kristofides.rar

    да я тоже пытаюсь нормальное описание найти…в английской литературе в основном описан именно алгоритм для формулировки в виде линейного программирования, либо всякие приближенные алгоритмы…а этот чё-то найти пока не могу ((((

  2. 11
    Евгений Князев ответил:

    Как я понимаю:
    1. правильно, из В` удаляем Sn` и помещаем его в В (это и есть –"отсеяли сгоряча". Т.е. гипотеза о том, что данное множество может входить в ответ не подтвердилась).
    2. да, делаем "шаг назад".

    сам хочу уже найти нормальное описание, тоже, но другими словами :)

  3. 10
    Овак Мяса ответил:

    потихоньку начинает доходить до тормознутых мозгов, но еще несколько вопросов, если несложно:

    "удалить последнее множество, скажем, Snl" – откуда удалить, из B' или B(если из B, то тогда вообще всё непонятно)?
    "положить р = l" – мы возвращаемся в тот блок, откуда удалили столбец, чтоб посмотреть следующий столбец этого блока?
    что означает "Snl отсеяли сгоряча"?

  4. 9
    Евгений Князев ответил:

    "4) В не может привести к лучшему решению. Если B = Ø (т. е. блок 1 исчерпан), то алгоритм заканчивает работу и оптимальным решением является B′. В противном случае удалить последнее множество, скажем, Snl добавить его в В, положить р = I, поставить метку над множеством Sk+1l, удалить предшествующую метку в блоке I и перейти к шагу 3.

    А что тут не понятно?
    Просто сделан "откат" к предыдущему состоянию системы. Выдвигается предположение, что Snl отсеяли "сгоряча", и оно может ещё пригодиться. Перемещается указатель в начало кучи. И гипотеза опять перепроверяется, но уже с добавленной вершиной (или свойством).

  5. 8
    Евгений Князев ответил:

    а вообще, это действительно, вершинное NP-полное покрытие с ограничением на веса вершин.

  6. 7
    Овак Мяса ответил:

    нет, это не вершинное покрытие…в книжке Гэри Джонсона эта задача (точнее не эта, а задача распознавания свойств) названа МИНИМАЛЬНОЕ ПОКРЫТИЕ(она тоже НП-полна). Но мне нужен именно алгоритм нахождения этих столбцов(вершин), а не сложность алгоритма.

  7. 6
    Жека Кирпичев ответил:

    А, так это вершинное покрытие! Оно же NP-полно.

  8. 5
    Овак Мяса ответил:

    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) Максим Шестаков Золотарёв:
    честно говоря особо и не вникал конкретно что не так с симплекс-методом(просмотрел вскольз), вроде в этом проблема и есть. Но, к сожалению, данный алгоритм мне нужен для того, чтобы в дальнейшем поместить его в учебнике по дискретной математике для студентов второго курса, а к этому времени они не проходили раздел линейного программирования (((( Но всё равно спасибо, что указал как решить проблему, для себя обязательно посмотрю.

  9. 4
    Евгений Князев ответил:

    У Д.Кнута этот метод рассматривался.

    А просил я формулировку по одной простой причине — метод один, а названий несколько. Или реализация медода в каком-либо статистическом, математическом или ином пакете/классе.

    Для начала, предложу не изобретать велосипед, а поглядеть доки MathLABa (например) на предмет подходящего. А уже к этому подключиться из языка программирования.

    Нашел вполне грамотное описание данной задачи + примеры + алгоритм:
    //rain.ifmo.ru/cat/view.php/theory/graph-colori...

  10. 3
    Максим Золотарёв ответил:

    Если проблема в применении симплекс-метода только в дробных решениях – то для борьбы с ними применяется метод ветвей и границ.

    Поищи в инете
    "Метод ветвей и границ решения задач целочисленного линейного программирования"
    "Метод Лэнг и Дойг"

  11. 2
    Овак Мяса ответил:

    эту задачу можно сформулировать как задачу линейного программирования. Но симплекс метод – решения не даст (по крайней мере в его первоначальном виде), ибо он может дать вещественные решения, что недопустимо в данной задаче…вообщем-то мне это и не нужно, есть более простые алгоритмы для ее решения.

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

  12. 1
    Евгений Князев ответил:

    Для тех кто в танке: что такое "покрытие". Может эту задачу можно свести к задаче линейного (нелинейного) программирования?

    з.ы. книжку некоего Кристо….в глаза не видел, так что учимся задавать вопросы.

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.