Труднорешаемые задачи. Последовательный анализ вариантов

Содержание
Введение
1. Задачи, NP-трудные в сильном смысле
1.1. Обслуживание требований без задержек
2.Алгоритм
2.1 Последовательный анализ вариантов
3. Псевдополиномиальное сведение задач и NP-трудные в сильном смысле задачи
4.Использование NP-трудных задач
Заключение
Библиографический список

Введение
Большинство задач, интересных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы решения. То есть время работы алгоритма на входе длины n составляет не более O(nk) для некоторой константы k (не зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классический пример такой задачи — «проблема остановки» (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» — время его работы не есть O(nk) ни для какого фиксированного числа k.
Если мы хотим провести пусть грубую, но формальную границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы рассмотрим, руководствуясь [1], класс задач, называемых NP-полными. Для этих задач не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом «P = NP». Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.
1. Задачи, NP-трудные в сильном смысле
Приводятся примеры доказательств NP-трудности в сильном смысле ряда задач теории расписаний. Техника доказательства результатов такого рода во многом напоминает приемы которые использовались при установлении NP трудности (в обычном смысле) экстремальных задач теории расписаний. Для доказательства NP-трудности в сильном смысле тон или иной экстремальной задачи будем доказывать №" трудность в сильном смысле соответствующей задачи распознавания. Для этого достаточно показать, что к ней сводится некоторая известная NP –полная в сильном смысле задача. В качестве такой задачи в данном параграфе выбрана задача о 3-разбиении, которая заключается в следующем. Имеется множество каждому элементу которого поставлено в соответствие натуральное число (вес) е,, причем
Существует ли такое разбиение мужества .V0 на трехэлементные подмножества N °, N * .....N° такие, что для всех ;
Отметим, что условие является существенным. Оно означает, что сумма весов любых четырех (и более) элементов будет больше, чем Е. а любых двух элементов - меньше, чем Е. Подчеркнем также то, что задача о разбиении - исторически первая задача, для которой установлена W-полнота в сильном смысле.
Чтобы обеспечить псевдополиномиальное сведение задачи с 3-раэбнении к некоторой задаче распознавания, необходимо преобразовать входную информацию задачи о 3-разбиении во входную информацию некоторой ее индивидуальной задачи распознавания. Число выполняемых при этом действий должно полиномиально зависеть от длины входа задачи о 3 разбиении, представленного в унарной системе счисления, другими словами, от величины Иногда удается установить обычную полиномиальную сводимость. В этом случае число действий но преобразованию входной информации полиномиально зависит от или даже от n0 . Построенная в результате преобразования входа задачи о З разбиении –индивидуальная задача распознавания должна иметь ответ тогда и только тогда, когда такой же ответ имеет задача о 3 разбиений.
1.1 Обслуживание требований без задержек
Установим NP трудность в сильном смысле В этой задаче условие означает что требование I не обслуживается прибором LПри такой интерпретации нулевых длительностей оптимальное расписание без задержек необязательно принадлежит классу перестановленных расписаний .
Другими — словами, задачи и в данном случае не эквивалентны. Напомним, что задачи и эквивалентны, если все либо среди f.t имеются равные нулю и запись означает, что длительность. Справедлива
Теорема 1.1. Задача является NPтрудной в сильном смысле, если условие означает, что требование i прибором L не обслуживается.
Доказательство. Сформулируем соответствующую задачу распознавания: определить, существует ли расписание s °, при котором для заданного числа у. Покажем, что к этой задаче сводится задача о 3-разбиении. Для преобразования входной информации задачи о 3-раэбиении во входную информацию индивидуальной задачи распознавания необходимо значения и у выразить через
Положим и разобьем множество N на две группы: и-требования, обозначаемые Uij и v-требовання, обозначаемые
Положим , и зададим / . Покажем, что в построенной задаче расписание S ° , при котором существует тогда и только тогда, когда имеет решение задача о 3-разбиеиии. имеет решение задача о 3 разбиений.
1. Пусть задача о 3-разбиении имеет решение и найденные трехэлементные подмножества элементов множества N 0 . Через обозначим произвольную перестановку u-требований с номерами из множества . Прибор 1 функционирует без простоев во временном интервале ], а прибор 2 - в интервале [0; у]. При этом прибор 1 в интервале обслуживает требование . Прибор 2 в интервале обслуживает требование v 0 , а в каждом из интервалов - последовательность требований Требование обслуживается прибором 2 в интервале
2. Пусть существует расписание s ° . Так как и прибор 2 функционирует в интервале [0; у] без простоев.

Рис.(1.1)
Прибор 1 завершает обслуживание всех требований не раньше момента времени у - Е. С учетом того, что задержки запрещены, последним требованием, которое обслуживает прибор 2, будет некоторое v-требование, а прибор 1 должен функционировать без простоев в интервале . Поскольку требования , не отличаются друг от друга по длительностям обслуживания, не нарушая общности можно считать, что они обслуживаются прибором I в порядке возрастания их номеров. Отсюда сразу следует, что требования, обслуживаются при расписании s ° так же, как и при расписании, представленном на рис. 1.1. Требование vc обслуживается прибором 2 в интервале , так как это единственный незанятый подинтервал длины 2Е интервала Требования щ должны обслуживаться прибором 2 в интервалах . Обозначая через множество номеров и-требований, обслуживаемых прибором 2 в интервале , получаем решение задача о 3-разбиении. Тем самым за действий задача о 3-раз-биении сведена к задаче о существовании расписания S °. Теорема доказана.
Теорема 2 . Задача является NP-трудной в сильном смысле.
Теорема 3. Задача является NP-трудной в сильном смысле.
Доказательство. Сформулируем соответствующую задачу распознавания. В обслуживающую систему, состоящую из двух приборов А и В, в момент времени d =0 поступает частично упорядоченное множество требований
N {1,2...., л}. . Каждая компонента связности графа редукции отношения -, заданного на N , является цепью. Длительность выполнения каждой операции равна единице. Требуется определить, существует ли расписание S ° , при котором для заданного значения у .
Построим псевдополнномиальное сведение задачи о 3-разбиении к сформулированной задаче распознавания.
Положим: , где
На множестве N заладим отношение -, полагай / - I тогда и только тогда, когда . Очевидно, каждая компонента связности графа редукции этого отношения представляет собой цепь.
Пусть процесс обслуживания каждого требования состоит в выполнении единственной операции. Для требований из множества N 1 положим L 1 = (В) при . Для каждого , положим
Для требования из множества - линейно –упорядоченное и число его элементов равно , то при любом расписаний с общим временем обслуживания требований, равным у, требования множества N3 n +1 должны обслуживаться непрерывно одно за другим начиная с момента времени d = 0. На рис. 2 представлен фрагмент расписания обслуживания требований множества при котором общее время обслуживания требований равно у. Это расписание является периодическим с периодом
Рис(1.2)
Таким образом, обслуживание требований множества при любом расписании с общим временем обслуживания требований, равным у, может быть осуществлено только в тех единичных интервалах, которые определяются последовательностью
Покажем, что расписание S 0 можно построить тогда и только тогда, когда имеет решение задача о 3-раэбиении. Пусть существует разбиение множества № на n0 трехэлементных подмножеств таких, что при j=1,0. Тогда, обслуживая множество требований интервале , в соответствии с отношением получаем расписание с общим временем обслуживания требований, равным у .
Пусть существует расписание S ° , при котором .Так как суммарная длительность обслуживания всех требований прибором А (прибором В) равна у , то при расписании S как прибор А, так и прибор В в интервале [0; у] не простаивает. По условию обслуживание каждого требования для которого
Учитывая, что в построенном при доказательстве теоремы 3 примере процесс обслуживания каждого требования состоит из единственной операции, можно сделать вывод о том, что и задача является NP-трудной в сильном смысле.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию