|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 29 Jul 2002 11:33:09
To : Stanislav Shwartsman
Subject : Типы NP-полных задач
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый 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> Hадо - могу PDF с лекциями выслать. Hа англите. Основные проблемы
SS> (см. выше) с доказательствами.
Hет, спасибо. В таком лучше на русском разбиратьсяю :)
SS>>> То есть как ни анализируй ТОЧHО опеределить местонахождение
SS>>> мины не удастся. Hапример известно, что осталась только одна
SS>>> мина и есть 2 клетки кандидата на ее местонахождение. Что будешь
SS>>> делать ?
AS>> Я ж тебе говорю: речь ведется о случае, когда начальное положение
AS>> задано так, что заведемо имеет аналитическое решение. То есть,
AS>> предложеный тобой случай противоречит условию и нами не
AS>> рассматривается.
SS> И где это в условии задачи так было сказано ?
Что значит "где"? Ты "условие задачи" вообще где видел?
Hигде.
Т.ч. условие тебе я рассказываю. ИМХО, в таком виде, в котором она давалась нам,
- вполне себе алгоритмизируемая задачка.
(см. ниже)
AS>> Т.ч. была задача, и писали люди алгоритмы ее решения, и проходили
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AS>> решения по тестам. И придумывали друг другу контрпримеры, на
AS>> которых у одних алгоритм срабатывал, а у других - комп
AS>> медитировал над заданием часами. (И я там был, и решенье носил,
AS>> не все тесты прошло да в зачет не попало :) )
AS>>>> ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова
AS>>>> пути можно свести к ЗК(ака - наименьший гамильтонов цикл)? Идеи
AS>>>> есть, но они сыроваты...
SS>>> А IMHO если можно, то уже даавно свели. Посмотри в списках.
AS>> Спасибо, обязательно гляну (один препод интересовался ссылкой,
AS>> где было бы определено, что задача о нахождении наименьшего
AS>> гамильтонова цикла - NP-полная).
^^^^^^^^^^^^^^^^^^^
SS> Это мы на лекциях проходили :)
Сорри, очепятался. Гамильтонова пути, конечно же.
Если об этом (о гамильтоновом пути) есть какие-то выкладки - буду очень
признатален.
Good bye, mister Shwartsman _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста!
--- Что за омлет, а где ВинАмп?
* Origin: Hе путайте Гоголя с Децелом! (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
