|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 27 Jul 2002 11:38:04
To : Stanislav Shwartsman
Subject : Типы NP-полных задач
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый Stanislav! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Stanislav Shwartsman и Alexander Shmidt! Что за "Типы NP-полных
задач", а где же яйца?!
AS>> Именно _зачач_ - да, сколько угодно придумать можно, но именно
AS>> типов, АФАИК - 7 (по крайней мере так пишут на всех сайтах
AS>> всевозможных ВУЗов в разделах планов учебы).
SS> Что значит типов ?
SS> Те ЗАДАЧИ, с которых все началось (3-SAT, VERTEX COVER и т.д) и
Хотя бы эти опиши, если не трудно.
Кстати, VERTEX COVER - это, случайно, не "выпуклая оболочка"?
SS> которые по причине их относительной простоты изучают в ВУЗах никак не
SS> являются ТИПАМИ NP-полных задач. Вообще не слышал ни слова о
SS> какой-либо классификации в этой области.
Hичего возразить не могу. Просто, в свое время, искал инфу по 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> несколько раз обсуждался.
Помню, было такое. Hо я с этой задачей на заочной олимпиаде встречался и ее
специфичность показалось довольно интересной.
SS>>> Между прочим я русским языком тебе в нетмыле объяснял, что
SS>>> "сапер" в общем виде задача не разрешимая. Существует несколько
SS>>> раскладов, при которых просто невозможно определить где мина из
SS>>> известных данных. Остается только наугад, а значит задача
SS>>> решения не имеет.
AS>> Тут перебор ведется так: в месте, где неределенно - мина может
AS>> стоять, а может и не стоять, ставится фиктивная мина и
AS>> анализируется, возможен ли такой расклад (возможно придется
AS>> ставить еще фиктивные мины и если все они не могут стоять на
AS>> своих местах - это одна из причин, почему эта не может стоять на
AS>> поставленном нами месте; тут, очевидно, можем падать в такую
AS>> зверскую рекурсию, что дай нам боже дожить до такой техники, чтоб
AS>> это правильно посчитать). Если получилось, что мина стоять на
AS>> этом месте ну никак не может - открываем поле. И так далее...
SS> И так далее, пока не придем к положению, с которого не знаем куда
SS> продолжать. Сейчас опять начнется спор, а где-то через месяц
SS> найдется кто-то, кому не лень сесть и построить пример, не имеющий
SS> решения.
Да че там придумывать - в "сапера", что ли, не играли? :)
SS> То есть как ни анализируй ТОЧHО опеределить местонахождение мины не
SS> удастьсь. Hапример известно, что осталась только одна мина и есть 2
SS> клетки кандидата на ее местонахождение. Что будешь делать ?
Я ж тебе говорю: речь ведется о случае, когда начальное положение задано так,
что заведемо имеет аналитическое решение.
То есть, предложеный тобой случай противоречит условию и нами не
рассматривается.
Т.ч. была задача, и писали люди алгоритмы ее решения, и проходили решения по
тестам. И придумывали друг другу контрпримеры, на которых у одних алгоритм
срабатывал, а у других - комп медитировал над заданием часами.
(И я там был, и решенье носил, не все тесты прошло да в зачет не попало :) )
AS>> ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова пути
AS>> можно свести к ЗК(ака - наименьший гамильтонов цикл)? Идеи есть,
AS>> но они сыроваты...
SS> А IMHO если можно, то уже даавно свели. Посмотри в списках.
Спасибо, обязательно гляну (один препод интересовался ссылкой, где было бы
определено, что задача о нахождении наименьшего гамильтонова цикла - NP-полная).
Good bye, mister Shwartsman _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Относись к себе так, как хочешь, чтоб относились к тебе (c) XAR
--- Что за омлет, а где ВинАмп?
* Origin: Масяня - девочка, живущая в сети. (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
