|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 25 Jul 2002 09:16:33
To : Stanislav Shwartsman
Subject : Типы NP-полных задач
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый Stanislav! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Stanislav Shwartsman и Alexander Shmidt! Что за "Типы NP-полных
задач", а где же яйца?!
AS>> Кто знает про сабж? Сколько их и какие они.
AS>> По поводу кол-ва, их по-моему семь. С тем, что они, собственно,
AS>> представляют - сложнее. Помню только задачу коммивояжера, задачу
AS>> об оптимальном раскрое...
SS> Между прочим я тебе про это уже отвечал. Если спрашиваешь, так хоть
SS> потрудись ответы читать.
Или у меня провалы в памяти, или я слишком быстро карбонки перелистываю...
В любом случае извиняюсь: а я-то уж думал, никто в тот раз не захотел отвечать
мне. :)
Тогда тебе отвечу сейчас:
SS> =================================================== Msg : 176 of 384
SS> Snt Loc Scn From : Stanislav Shwartsman 2:400/520
SS> 12 Jul 02 11:00:28 To : Alexander Shmidt Subj : Типы NP-полных
SS> ======================================================================
SS> 10 Jul 02 20:49, you wrote to All:
AS>> Hасколько я слышал, есть всего семь общих сабжей. Одни из них:
AS>> задача коммивояжера и поиск наименьшего гамильтонова пути (или
AS>> она к ЗК сводится?). Какие еще есть типы?
SS> NP-полных задач есть несколько сотен. Смотри на
SS> http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
Именно _зачач_ - да, сколько угодно придумать можно, но именно типов, АФАИК - 7
(по крайней мере так пишут на всех сайтах всевозможных ВУЗов в разделах планов
учебы).
SS> An Annotated List of Selected NP-complete Problems
SS> Там перечисленно 88 проблем, вот первая десятка:
Чувствую, придется все перечитать. :(
AS>> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)
SS> Это самостоятельный первоапрельский прикол.
В каком смысле?
AS>> ЗЫ: Кста, "сапер" относится к отдельным типам или он сводится к
AS>> какому-нибудь из существующих? :)
SS> Ты тормоз или притворяешься ?
Вот, хоть убей, переписку в мыле не помню :)
SS> Между прочим я русским языком тебе в нетмыле объяснял, что "сапер"
SS> в общем виде задача не разрешимая. Существует несколько раскладов,
SS> при которых просто невозможно определить где мина из известных
SS> данных. Остается только наугад, а значит задача решения не имеет.
Имеется в виду, что в исходных данных гарантируется, что задача имеет
аналитическое решение (несколько полей уже должно быть открыто, само собой).
Тут перебор ведется так: в месте, где неределенно - мина может стоять, а может и
не стоять, ставится фиктивная мина и анализируется, возможен ли такой расклад
(возможно придется ставить еще фиктивные мины и если все они не могут стоять на
своих местах - это одна из причин, почему эта не может стоять на поставленном
нами месте; тут, очевидно, можем падать в такую зверскую рекурсию, что дай нам
боже дожить до такой техники, чтоб это правильно посчитать). Если получилось,
что мина стоять на этом месте ну никак не может - открываем поле.
И так далее...
ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова пути можно свести к
ЗК(ака - наименьший гамильтонов цикл)? Идеи есть, но они сыроваты...
Good bye, mister Shwartsman _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Ешь ананасы, рябчиков жуй - сегодня ведь твой день рожденья, буржуй!
--- Что за омлет, а где ВинАмп?
* Origin: ...когда ты любишь парней - это "gay" (с) ~Сплин (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
