Задачи распознавания и экстремальные комбинаторные задачи
Понятие вычислительной сложности алгоритма, полиномиально разрешимые и NP-трудные задачи, основная гипотеза теории сложности вычислений.
ЗадачТР, как правило, являются задачами комбинаторной оптимизации (экстремальными комбинаторными задачами). Задачи комбинаторной оптимизации — задачи выбора и/или расположения элемента (ов) из некоторого конечного, множества в соответствии с заданными правилами с целью минимизировать (максимизировать) некоторую целевую функцию.
В комбинаторной оптимизации задачи условно делятся на:
· полиномиально разрешимые (относительно простые);
· NP-трудные (соответственно, сложные).
Если для некоторой новой задачи не удается построить "быстрый" алгоритм решения, то пытаются определить, не является ли эта задача NP-трудной. Если это подтверждается, то (в предположении P ≠ NP), "быстрый" алгоритм для данной задачи построить не удастся.
Большинство задач ТР являются NP-трудными т.е. алгоритмы их решения, реализованные на современных компьютерах могут требовать неприемлемо большое время для решения практических задач "большой" размерности.
Размерность задачи комбинаторной оптимизации обычно равна мощности множества, элементы которого необходимо выбрать или упорядочить.
* * *
Элементарная операция (при реализации алгоритма на ЭВМ) - сложение, умножение, сравнение двух чисел, запись либо считывание числа, расположенного по известному адресу и т. п.
|
|
|
Вычислительная (временная) сложность алгоритма - количество элементарных операций, необходимое для его реализации.
Пример задачи получается при замене всех имеющихся в общей формулировке задачи параметров их конкретными значениями. Поскольку для двух примеров задачи с одной и той же размерностью время работы алгоритма (количество операций) может быть разным, вводят также понятие
Трудоемкость алгоритма (T(n)) - функция верхней границы (sup()) времени работы (количества элементарных операций) алгоритма для всех примеров размерности n. Рассматривается наибольший порядок данной функции.
* * *
Схема кодирования сопоставляет цепочку символов каждому примеру задачи.
Оценка вычислительной (временной) сложности алгоритма решения задачи - функция от длины записи входной информации задачи, т.е. она непосредственно зависит от выбранной схемы кодирования.
Схема кодирования является разумной, если она удовлетворяет следующим неформальным условиям.
· (а) Код примера задачи должен быть компактным и не содержать необязательную информацию или символы.
· (б) Числа, из примера задачи должны, быть представлены в двоичной, либо какой-нибудь иной системе счисления с основанием, отличным от единицы.
|
|
|
· (в) Схема, кодирования должна, обладать свойством декодируемости, т.е. для каждого параметра задачи должен существовать эффективный алгоритм, способный выделить код этого параметра из кода любого примера задачи.
· (г) Схема кодирования должна обеспечивать однородность при кодировании различных примеров одной и той же задачи. Однородность означает, что схема кодирования должна обеспечивать для любых двух различных примеров задачи получение кодов, "близких" по длине. Данное условие предполагает, что код примера задачи должен содержать лишь ту информацию, которую содержит общая формулировка задачи, дополненная, конкретными значениями параметров задачи.
* * *
Для любого примера I некоторой задачи введем в рассмотрение функции:
· Length[I] - длина кода (кол-во символов) данных примера I при использовании разумной схемы кодирования
· Max[I] - величина наибольшего числового параметра в I, при отсутствии в задаче чисел Max[I] = 1
Полиномиальныйалгоритм – алгоритм решения задачи, вычислительная (временная) сложность которого не превосходит (т.е. порядок трудоемкости равен) некоторого полинома от функции Length[I] для любого примера I задачи.
|
|
|
Поскольку для представления целого числа a в бинарной (двоичной) кодировке необходимо log2a бит (ячеек памяти), а для кодирования n целых чисел, самое большое из которых равно a необходимо n log2a бит
то для примеров задач размерности n, как правило, длина кода составляет F(n)* log2a, (например, nlog2a) бит. Соответственно, при оценке трудоемкости алгоритмов принимают во внимание не длину кода, а только размерности примера n.
Кроме того, поскольку тяжело задать функцию Т(n) точно, рассматривают только ее наибольший порядок.
Например, если трудоемкость некоторого алгоритма T(n) = 2n3 + 7n2 + 10, то говорят, что алгоритм имеет трудоемкость порядка O(n3) операций (или для краткости “трудоемкость алгоритма O(n3)”, что означает, что количество операций алгоритма не более, чем С* n3, где С – константа).
Иными словами
Полиномиальныйалгоритм – алгоритм, трудоемкость которого T(n) = O(nd) , где d – целое положительное число.
Полиномиально разрешимая задача – задача, для решения которой существует полиномиальный алгоритм.
Класс Pобразуют всеполиномиально разрешимые задачи (распознавания).
Полиномиальные алгоритмы принято считать эффективными, поскольку полиномиальная функция при больших значениях аргумента (Length[I]) растет не так быстро как экспоненциальная.
|
|
|
* * *
Псевдополиномиальный алгоритм – алгоритм решения задачи, вычислительная сложность которого не превосходит (т.е. порядок трудоемкости равен) некоторый полином от функций: Length[I] и Max[I], - для любого I.
Иными словами
Псевдополиномиальныйалгоритм – алгоритм, трудоемкость которого зависит от числового параметра примера A, например, T(n) = O(An).
Псевдополиномиально-разрешимая задача – задача, для решения которой существует псевдополиномиальный алгоритм.
* * *
Задачи распознавания и экстремальные комбинаторные задачи.
Задача распознавания (свойств объектов) - некоторый общий вопрос, предполагающий ответ "да", если рассматриваемый в этом вопросе объект обладает свойствами, описанными в формулировке вопроса.
Объект и его свойства описываются с помощью некоторых параметров, конкретные значения которых в общей формулировке вопроса отсутствуют. Параметрами могут быть множества, графы, числа, функции и т.п.
Задачам комбинаторной оптимизации (экстремальным комбинаторным задачам) можно сопоставить соответствующие задачи распознавания следующим образом:
Определить, существует ли такой элемент x' в заданном множестве X, что F(x') ≤ y (либо F(x') ≥ y в случае задачи максимизации) для данного действительного числа y.
Очевидно, если x* решение задачи минимизации, то элемент x' сX такой, что F(x') ≤y, существует тогда и только тогда, когда F(x*) ≤ y. Таким образом, экстремальная задача не проще соответствующей задачи распознавания.
* * *
Если задача сформулирована в форме вопроса, на который можно дать односложный ответ «Да» или «Нет», это не ограничивает класс вопросов. Например, говоря о задаче поиска минимума, мы формулируем вопрос «Есть ли в рассматриваемом множестве элементы, доставляющие функции значение меньшее или равное y?».
Меняя y в последнем вопросе и последовательно отвечая на него несколько раз, мы можем получить однозначный ответ. например, если для y = 5 был ответ «Нет», а для y = 6 ответ уже «Да», то, очевидно, что минимальное значение функции равно 6.
* * *
Дата добавления: 2018-02-28; просмотров: 633; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!