|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 28 Jul 2002 22:20:49
To : Alexander Shmidt
Subject : Типы NP-полных задач
--------------------------------------------------------------------------------
27 Jul 02 11:38, you wrote to me:
AS>>> Именно _зачач_ - да, сколько угодно придумать можно, но именно
AS>>> типов, АФАИК - 7 (по крайней мере так пишут на всех сайтах
AS>>> всевозможных ВУЗов в разделах планов учебы).
SS>> Что значит типов ?
SS>> Те ЗАДАЧИ, с которых все началось (3-SAT, VERTEX COVER и т.д) и
AS> Хотя бы эти опиши, если не трудно.
AS> Кстати, VERTEX COVER - это, случайно, не "выпуклая оболочка"?
Выпуклая оболочка это тривильный алгоритм, выполнимый за время n*log(n),
где кол-во точек-вершин. Этот алгоритм в любом ВУЗе проходят на
вычислительной геометрии.
SS>> которые по причине их относительной простоты изучают в ВУЗах
SS>> никак не являются ТИПАМИ NP-полных задач. Вообще не слышал ни
SS>> слова о какой-либо классификации в этой области.
AS> Hичего возразить не могу. Просто, в свое время, искал инфу по
AS> NP-полным задачам и все время натыкался на текст учебного плана
AS> какого-нибудь ВУЗа, где была строчка: "7 основных типов NP-полных
AS> задач". Стало интересно, что за...
Самые известные, базовые проблемы (которые мы в ВУЗе изучали):
1. Circuit-SAT
Given a boolean combination circuit composed of AND-OR-NOT gates,
is satifable ?
2. Boolean Formula Satisfiability (CNF-SAT, 3-CNF-SAT)
3. Clique
4. Vertex Cover
5. Set Cover
6. Hamilton Cycle
7. Travelling Salesman Problem
Дерево редукции:
7 -> 6 -------> 2 -> 1
5 -> 4 -> 3 /
Hадо - могу PDF с лекциями выслать. Hа англите. Основные проблемы
(см. выше) с доказательствами.
SS>> Список NP-полных задач получается очень просто. Сначала была
SS>> одна известная NP-полная задача, потом была доказана, что
SS>> существует редукция другой задачи к этой первой и NP-полных задач
SS>> стало две. Список задач пополняется путем доказательства редукции
SS>> твоей задачи к любой задаче из списка.
AS> Печально. Хотелось бы, чтобы хоть как-то были описаны основные группы
AS> подобных между собой задач, а то лопатить тысячу примеров...
IMHO не существует основных групп ...
SS>>>> An Annotated List of Selected NP-complete Problems
SS>>>> Там перечисленно 88 проблем, вот первая десятка:
AS>>> Чувствую, придется все перечитать. :(
SS>> Это я еще скромный сайтик выбрал. Есть списки длинной в тысячу
SS>> проблем и более.
AS> Во-во.
SS>> То есть как ни анализируй ТОЧHО опеределить местонахождение мины
SS>> не удастся. Hапример известно, что осталась только одна мина и
SS>> есть 2 клетки кандидата на ее местонахождение. Что будешь делать ?
AS> Я ж тебе говорю: речь ведется о случае, когда начальное положение
AS> задано так, что заведемо имеет аналитическое решение. То есть,
AS> предложеный тобой случай противоречит условию и нами не
AS> рассматривается.
И где это в условии задачи так было сказано ?
И вообще - нефиг спорить, у нас и других проблем хватает !
AS> Т.ч. была задача, и писали люди алгоритмы ее решения, и проходили
AS> решения по тестам. И придумывали друг другу контрпримеры, на которых у
AS> одних алгоритм срабатывал, а у других - комп медитировал над заданием
AS> часами. (И я там был, и решенье носил, не все тесты прошло да в зачет
AS> не попало :) )
AS>>> ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова пути
AS>>> можно свести к ЗК(ака - наименьший гамильтонов цикл)? Идеи есть,
AS>>> но они сыроваты...
SS>> А IMHO если можно, то уже даавно свели. Посмотри в списках.
AS> Спасибо, обязательно гляну (один препод интересовался ссылкой, где
AS> было бы определено, что задача о нахождении наименьшего гамильтонова
AS> цикла - NP-полная).
Это мы на лекциях проходили :)
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Типы NP-полных задач 