|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 24 Jul 2002 22:05:33
To : Alexander Shmidt
Subject : Типы NP-полных задач
--------------------------------------------------------------------------------
23 Jul 02 08:06, you wrote to All:
AS> Кто знает про сабж? Сколько их и какие они.
AS> По поводу кол-ва, их по-моему семь. С тем, что они, собственно,
AS> представляют - сложнее. Помню только задачу коммивояжера, задачу об
AS> оптимальном раскрое...
Между прочим я тебе про это уже отвечал. Если спрашиваешь, так хоть
потрудись ответы читать.
=== Cut ===
= RU.ALGORITHMS (2:400/520) ===================================================
Msg : 176 of 384 Snt Loc Scn
From : Stanislav Shwartsman 2:400/520 12 Jul 02 11:00:28## To : Alexander Shmidt
Subj : Типы NP-полных задач
===============================================================================
Hello Alexander!
10 Jul 02 20:49, you wrote to All:
AS> Hасколько я слышал, есть всего семь общих сабжей. Одни из них: задача
AS> коммивояжера и поиск наименьшего гамильтонова пути (или она к ЗК
AS> сводится?). Какие еще есть типы?
NP-полных задач есть несколько сотен. Смотри на
http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
An Annotated List of Selected NP-complete Problems
Там перечисленно 88 проблем, вот первая десятка:
-------------------------------------------------------------------------------
Number: 1
Name: 3-Satisfiability (3-SAT) [LO2] 2
Input: A set of m clauses - C1 ,C2,...,Cm - over a set of n Boolean valued
variables Xn=< x1,x2,...,xn>, such that each clause depends on exactly three
distinct variables from Xn. A clause being a Boolean expression of the form
yi+yj+yk where each y is of the form x or -x (i.e. negation of x) with x being
some variable in Xn. For example if n=4 and m=3 a possible instance could be
the (set of) Boolean expressions: C1=(x1+(-x2)+(-x3)); C2=(x2+x3+(-x4));
C3=((-x1)+x3+x4);
Question: Can each variable xi of Xn be assigned a Boolean value alphai in such
a way that every clause evaluates to the Boolean result true under the
assignment < xi:=alphai:1<=i<=n>?
In the example instance, the assignment < x1:=true;x2:=false;x3:=true;
x4:=false> is such that each of the three clauses takes the value true.
Comments: For reasons that will become clearer at the end of the course, this
problem had to be Number 1. Some relevant material concerning this problem
might be found in the special issue (Volume 81, 1996) of the journal Artificial
Intelligence that is available in the Library.
[skip]
AS> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)
Это самостоятельный первоапрельский прикол.
[skip]
=== Cut ===
AS> ЗЫ: Кста, "сапер" относится к отдельным типам или он сводится к
AS> какому-нибудь из существующих? :)
Ты тормоз или притворяешься ?
Между прочим я русским языком тебе в нетмыле объяснял, что "сапер"
в общем виде задача не разрешимая. Существует несколько раскладов,
при которых просто невозможно определить где мина из известных данных.
Остается только наугад, а значит задача решения не имеет.
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-полных задач 
