Re: Типы NP-полных задач
- From
- Vokin Andrei ()
- To
- Alexander Shmidt
- Date
- 2002-07-28T22:57:52Z
- Area
- RU.ALGORITHMS
From: "Vokin Andrei" <vok@sbor.ru>
Нет VERTEX COVER - это задача о вершинном покрытии. т.е. поиск в
неориентированном графе G<V,E> минимального подмножества вершин V1 такого,
для любого ребра из E хотя бы один из его концов содержится в V1.
- ---
Vokin Andrei e-mail : vok@sbor.ru
"Alexander Shmidt" <Alexander.Shmidt@p74.f34.n464.z2.fidonet.org>
сообщил/сообщила в новостях следующее:
news:1027771094@p74.f34.n464.z2.FIDOnet.ftn...
>
> >< ┼ >< ┼ >< Хау, бледнолицый Stanislav! >< ┼ >< ┼ ><
> (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
>
> Эй, уважаемые Stanislav Shwartsman и Alexander Shmidt! Что за "Типы
NP-полных
> задач", а где же яйца?!
>
> AS>> Именно _зачач_ - да, сколько угодно придумать можно, но именно
> AS>> типов, АФАИК - 7 (по крайней мере так пишут на всех сайтах
> AS>> всевозможных ВУЗов в разделах планов учебы).
> SS> Что значит типов ?
> SS> Те ЗАДАЧИ, с которых все началось (3-SAT, VERTEX COVER и т.д) и
> Хотя бы эти опиши, если не трудно.
>
> Кстати, VERTEX COVER - это, случайно, не "выпуклая оболочка"?
>
> SS> которые по причине их относительной простоты изучают в ВУЗах никак не
> SS> являются ТИПАМИ NP-полных задач. Вообще не слышал ни слова о
> SS> какой-либо классификации в этой области.
> Ничего возразить не могу. Просто, в свое время, искал инфу по NP-полным
задачам
> и все время натыкался на текст учебного плана какого-нибудь ВУЗа, где была
> строчка: "7 основных типов NP-полных задач". Стало интересно, что за...
>
> SS> Список NP-полных задач получается очень просто. Сначала была одна
> SS> известная NP-полная задача, потом была доказана, что существует
> SS> редукция другой задачи к этой первой и NP-полных задач стало две.
> SS> Список задач пополняется путем доказательства редукции твоей задачи к
> SS> любой задаче из списка.
> Печально. Хотелось бы, чтобы хоть как-то были описаны основные группы
подобных
> между собой задач, а то лопатить тысячу примеров...
>
> SS>>> An Annotated List of Selected NP-complete Problems
> SS>>> Там перечисленно 88 проблем, вот первая десятка:
> AS>> Чувствую, придется все перечитать. :(
> SS> Это я еще скромный сайтик выбрал. Есть списки длинной в тысячу
> SS> проблем и более.
> Во-во.
>
> AS>>>> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)
> SS>>> Это самостоятельный первоапрельский прикол.
> AS>> В каком смысле?
> SS> В том самом смысле, что статья, в которой "сапер" называется сабжем
> SS> была написана к 1 апреля. Между прочим в этой эхе этот вопрос уже
> SS> несколько раз обсуждался.
> Помню, было такое. Но я с этой задачей на заочной олимпиаде встречался и
ее
> специфичность показалось довольно интересной.
>
> SS>>> Между прочим я русским языком тебе в нетмыле объяснял, что
> SS>>> "сапер" в общем виде задача не разрешимая. Существует несколько
> SS>>> раскладов, при которых просто невозможно определить где мина из
> SS>>> известных данных. Остается только наугад, а значит задача
> SS>>> решения не имеет.
> AS>> Тут перебор ведется так: в месте, где неределенно - мина может
> AS>> стоять, а может и не стоять, ставится фиктивная мина и
> AS>> анализируется, возможен ли такой расклад (возможно придется
> AS>> ставить еще фиктивные мины и если все они не могут стоять на
> AS>> своих местах - это одна из причин, почему эта не может стоять на
> AS>> поставленном нами месте; тут, очевидно, можем падать в такую
> AS>> зверскую рекурсию, что дай нам боже дожить до такой техники, чтоб
> AS>> это правильно посчитать). Если получилось, что мина стоять на
> AS>> этом месте ну никак не может - открываем поле. И так далее...
> SS> И так далее, пока не придем к положению, с которого не знаем куда
> SS> продолжать. Сейчас опять начнется спор, а где-то через месяц
> SS> найдется кто-то, кому не лень сесть и построить пример, не имеющий
> SS> решения.
> Да че там придумывать - в "сапера", что ли, не играли? :)
>
> SS> То есть как ни анализируй ТОЧНО опеределить местонахождение мины не
> SS> удастьсь. Например известно, что осталась только одна мина и есть 2
> SS> клетки кандидата на ее местонахождение. Что будешь делать ?
> Я ж тебе говорю: речь ведется о случае, когда начальное положение задано
так,
> что заведемо имеет аналитическое решение.
> То есть, предложеный тобой случай противоречит условию и нами не
> рассматривается.
>
> Т.ч. была задача, и писали люди алгоритмы ее решения, и проходили решения
по
> тестам. И придумывали друг другу контрпримеры, на которых у одних алгоритм
> срабатывал, а у других - комп медитировал над заданием часами.
> (И я там был, и решенье носил, не все тесты прошло да в зачет не попало
:) )
>
> AS>> ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова пути
> AS>> можно свести к ЗК(ака - наименьший гамильтонов цикл)? Идеи есть,
> AS>> но они сыроваты...
> SS> А IMHO если можно, то уже даавно свели. Посмотри в списках.
> Спасибо, обязательно гляну (один препод интересовался ссылкой, где было бы
> определено, что задача о нахождении наименьшего гамильтонова цикла -
> NP-полная).
>
> Good bye, mister Shwartsman _
> /_| _ _ _/
> Smith, ( | (/ (- /) / Smith...
> _/
> ... Относись к себе так, как хочешь, чтоб относились к тебе (c) XAR
--- ifmail v.2.15dev5
* Origin: Dune Ltd, Sosnovy Bor, The Russian Federation. ISP. (2:5020/400)