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

From

Alexander Shmidt (2:464/34.74)

To

Stanislav Shwartsman

Date

2002-07-29T11:33:09Z

Area

RU.ALGORITHMS

      ><  ┼  ><  ┼  ><   Хау, бледнолицый  Stanislav!   ><  ┼  ><  ┼  ><
    (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)

 Эй, уважаемые Stanislav Shwartsman и Alexander Shmidt! Что за "Типы NP-полных задач", а где же яйца?!

 AS>> Кстати, VERTEX COVER - это, случайно, не "выпуклая оболочка"?
 SS>  Выпуклая оболочка это тривильный алгоритм, выполнимый за время
 SS> n*log(n), где кол-во точек-вершин. Этот алгоритм в любом ВУЗе проходят
 SS> на вычислительной геометрии.
Знаю, потому и удивился.

 SS>  Самые известные, базовые проблемы (которые мы в ВУЗе изучали):
 SS>  1. Circuit-SAT
 SS>     Given a boolean combination circuit composed of AND-OR-NOT gates,
 SS>     is satifable ?
 SS>  2. Boolean Formula Satisfiability (CNF-SAT, 3-CNF-SAT)
 SS>  3. Clique
 SS>  4. Vertex Cover
 SS>  5. Set Cover
 SS>  6. Hamilton Cycle
 SS>  7. Travelling Salesman Problem
 SS>  Дерево редукции:
 SS>7 ->> 6 -------> 2 -> 1
 SS>5 -> 4 ->> 3 /
Дык, 7=6. Или нет?

 SS>  Надо - могу PDF с лекциями выслать. На англите. Основные проблемы
 SS>  (см. выше) с доказательствами.
Нет, спасибо. В таком лучше на русском разбиратьсяю :)

 SS>>> То есть как ни анализируй ТОЧНО опеределить местонахождение
 SS>>> мины не удастся. Например известно, что осталась только одна
 SS>>> мина и есть 2 клетки кандидата на ее местонахождение. Что будешь
 SS>>> делать ?
 AS>> Я ж тебе говорю: речь ведется о случае, когда начальное положение
 AS>> задано так, что заведемо имеет аналитическое решение. То есть,
 AS>> предложеный тобой случай противоречит условию и нами не
 AS>> рассматривается.
 SS>  И где это в условии задачи так было сказано ?
Что значит "где"? Ты "условие задачи" вообще где видел?
Нигде.
Т.ч. условие тебе я рассказываю. ИМХО, в таком виде, в котором она давалась нам, - вполне себе алгоритмизируемая задачка.
(см. ниже)

 AS>> Т.ч. была задача, и писали люди алгоритмы ее решения, и проходили
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 AS>> решения по тестам. И придумывали друг другу контрпримеры, на
 AS>> которых у одних алгоритм срабатывал, а у других - комп
 AS>> медитировал над заданием часами. (И я там был, и решенье носил,
 AS>> не все тесты прошло да в зачет не попало :) )


 AS>>>> ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова
 AS>>>> пути можно свести к ЗК(ака - наименьший гамильтонов цикл)? Идеи
 AS>>>> есть, но они сыроваты...
 SS>>> А IMHO если можно, то уже даавно свели. Посмотри в списках.
 AS>> Спасибо, обязательно гляну (один препод интересовался ссылкой,
 AS>> где было бы определено, что задача о нахождении наименьшего
 AS>> гамильтонова цикла - NP-полная).
      ^^^^^^^^^^^^^^^^^^^
 SS>  Это мы на лекциях проходили :)
Сорри, очепятался. Гамильтонова пути, конечно же.
Если об этом (о гамильтоновом пути) есть какие-то выкладки - буду очень признатален.

Good bye, mister Shwartsman                     _
                                               /_|  _  _    _/
                                     Smith,   (  | (/ (- /) /   Smith...
                                                  _/
... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста!
--- Что за омлет, а где ВинАмп?
 * Origin: Не путайте Гоголя с Децелом! (2:464/34.74)