|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 26 Jul 2002 09:22:26
To : Alexander Shmidt
Subject : Типы NP-полных задач
--------------------------------------------------------------------------------
25 Jul 02 09:16, you wrote to me:
AS> Именно _зачач_ - да, сколько угодно придумать можно, но именно типов,
AS> АФАИК - 7 (по крайней мере так пишут на всех сайтах всевозможных ВУЗов
AS> в разделах планов учебы).
Что значит типов ?
Те ЗАДАЧИ, с которых все началось (3-SAT, VERTEX COVER и т.д) и которые
по причине их относительной простоты изучают в ВУЗах никак не являются
ТИПАМИ NP-полных задач. Вообще не слышал ни слова о какой-либо
классификации в этой области.
Список NP-полных задач получается очень просто. Сначала была одна известная
NP-полная задача, потом была доказана, что существует редукция другой
задачи к этой первой и NP-полных задач стало две. Список задач пополняется
путем доказательства редукции твоей задачи к любой задаче из списка.
SS>> An Annotated List of Selected NP-complete Problems
SS>> Там перечисленно 88 проблем, вот первая десятка:
AS> Чувствую, придется все перечитать. :(
Это я еще скромный сайтик выбрал. Есть списки длинной в тысячу проблем
и более.
AS>>> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)
SS>> Это самостоятельный первоапрельский прикол.
AS> В каком смысле?
В том самом смысле, что статья, в которой "сапер" называется сабжем
была написана к 1 апреля. Между прочим в этой эхе этот вопрос уже
несколько раз обсуждался.
AS> Вот, хоть убей, переписку в мыле не помню :)
Тогда извини, наверно это был не ты :)
SS>> Между прочим я русским языком тебе в нетмыле объяснял, что
SS>> "сапер" в общем виде задача не разрешимая. Существует несколько
SS>> раскладов, при которых просто невозможно определить где мина из
SS>> известных данных. Остается только наугад, а значит задача решения не
SS>> имеет.
AS> Тут перебор ведется так: в месте, где неределенно - мина может стоять,
AS> а может и не стоять, ставится фиктивная мина и анализируется, возможен
AS> ли такой расклад (возможно придется ставить еще фиктивные мины и если
AS> все они не могут стоять на своих местах - это одна из причин, почему
AS> эта не может стоять на поставленном нами месте; тут, очевидно, можем
AS> падать в такую зверскую рекурсию, что дай нам боже дожить до такой
AS> техники, чтоб это правильно посчитать). Если получилось, что мина
AS> стоять на этом месте ну никак не может - открываем поле. И так
AS> далее...
И так далее, пока не придем к положению, с которого не знаем куда
продолжать. Сейчас опять начнется спор, а где-то через месяц найдется
кто-то, кому не лень сесть и построить пример, не имеющий решения.
То есть как ни анализируй ТОЧHО опеределить местонахождение мины не
удастьсь. Hапример известно, что осталась только одна мина и есть 2
клетки кандидата на ее местонахождение. Что будешь делать ?
AS> ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова пути можно
AS> свести к ЗК(ака - наименьший гамильтонов цикл)? Идеи есть, но они
AS> сыроваты...
А IMHO если можно, то уже даавно свели. Посмотри в списках.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
