ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vokin Andrei                         2:5020/400     28 Jul 2002  22:57:52
 To : Alexander Shmidt
 Subject : Re: Типы NP-полных задач
 -------------------------------------------------------------------------------- 
 

 Hет 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> какой-либо классификации в этой области.
 > 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
 --- ifmail v.2.15dev5
  * Origin: Dune Ltd, Sosnovy Bor, The Russian Federation. ISP. (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор