Типы NP-полных задач

From

Alexander Shmidt (2:464/34.74)

To

Stanislav Shwartsman

Date

2002-07-25T09:16:33Z

Area

RU.ALGORITHMS

      ><  ┼  ><  ┼  ><   Хау, бледнолицый  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>> Насколько я слышал, есть всего семь общих сабжей. Одни из них:
 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)