Проблем с покритието на Vertex
В момента няма алгоритми, които да са полиномиални във времето за точното решаване на NP-трудни задачи. Освен това теоретиците на сложността са склонни към варианта, че такива алгоритми не съществуват. Въпреки това, NP-трудните проблеми са често срещани в живота. Един от начините за справяне с NP-трудни проблеми на практика е използването на приблизителни алгоритми.
Помислете за най-известния приблизителен алгоритъм за решаване напроблема с покритието на върха.
Формулиране на проблема.
Покритието на върха е наборSот върхове на графика, така че всеки ръб на графиката има поне един край вS.
Проблемът е да се избере минималното (по отношение на броя на върховете) покритие на върховете в неориентиран граф.
Нека изградим прост алгоритъм за решаване на този проблем, който допуска не повече от две грешки. Това означава, че ако има оптимално решение — набор от върхове T, то полученото от нас решение S удовлетворява неравенствотоS =S.
Малко история
Известният труд на Ричард Карп „Редуцируемост сред комбинаторните проблеми“, наречен Node Cover, разглежда съответния проблем за разрешаване на Vertex Cover и доказва неговата NP-пълнота. Алгоритъмът, който разгледахме, е разработен независимо от Фаника Гаврил и Михалис Янакакис през 1974 г. Най-добрата известна към момента оценка на приблизителния алгоритъм за проблема с покритието на върха принадлежи на Джордж Каракостас. Оценката е доказана в по-добро съотношение на приближение за проблема с покритието на върха.
Заключение.
Hardcore conf в C++. Каним само професионалисти.
Чете сега
Упълномощаване чрез Network Policy Server (NPS) за MikroTik
Ново приложение за решаване на проблема P vs. НП
Microsoft NPS MAB библиотеканаправи го сам
Коментари 27
алексейгригорев: Да, разбира се, че ще го направя. mrShadow: Ще изясня малко.
NP-трудна (NP-трудна, NP-трудна) задача е задача, незабавно получавайки отговори, на която бихме могли да решим всяка задача от класа NP за полиномиално време. Или, което е същото, можем да решим някакъв NP-пълен проблем. Неофициално това означава, че един NP-труден проблем не е по-лесен от всички проблеми от класа NP. Например, ако NP-труден проблем може да бъде решен за полиномиално време, тогава ще се окаже, че някакъв NP-пълен проблем също може да бъде решен за полиномиално време, тоест P=NP.
NP-пълна (NP-пълна) задача е NP-трудна задача, която сама по себе си също принадлежи към класа NP. Класът NP съдържа проблеми с решението. Това са въпроси, които имат да/не отговор. Например NP (и NP-пълни) проблеми включват следната версия на проблема с покритието на върховете: „Има ли граф покритие на върхове с кардиналност най-много k?“ Това е въпрос с да/не. Съществуват и проблеми с оптимизирането на NP. Това са NP-проблеми, при които се изисква да се намери най-доброто решение. Това вече не са въпроси с да/не. Следователно те не принадлежат към клас NP. Но много от тях са NP-твърди. Например NP-hard е задачата от темата: "Намерете минималното покритие на върха".
Знаейки как да решите NP-труден проблем (например проблем от тема), можете бързо да решите NP-пълен проблем (например проблемът за съществуването на покривен граф в