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

Курсовая работа

по дисциплине «Алгоритмы с оценками»

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

Содержание

Введение

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-разбиении, которая заключается в следующем. Имеется множество

каждому элементу которого поставлено в соответствие натуральное число (вес) е,, причем

Существует ли такое разбиение мужества .V⁰ на трехэлементные подмножества N°, N*.....N° такие, что

для всех ;

Отметим, что условие

является существенным. Оно означает, что сумма весов любых четырех (и более) элементов будет больше, чем Е. а любых двух элементов - меньше, чем Е. Подчеркнем также то, что задача о разбиении - исторически первая задача, для которой установлена W-полнота в сильном смысле.

Чтобы обеспечить псевдополиномиальное сведение задачи с 3-раэбнении к некоторой задаче распознавания, необходимо преобразовать входную информацию задачи о 3-разбиении во входную информацию некоторой ее индивидуальной задачи распознавания. Число выполняемых при этом действий должно полиномиально зависеть от длины входа задачи о 3 разбиении, представленного в унарной системе счисления, другими словами, от величины

Иногда удается установить обычную полиномиальную сводимость. В этом случае число действий но преобразованию входной информации полиномиально зависит от или даже от n₀. Построенная в результате преобразования входа задачи о З разбиении –индивидуальная задача распознавания должна иметь ответ тогда и только тогда, когда такой же ответ имеет задача о 3 разбиений.

1.1 Обслуживание требований без задержек

Установим NP трудность в сильном смысле

В этой задаче условие означает что требование I не обслуживается прибором LПри такой интерпретации нулевых длительностей оптимальное расписание без задержек необязательно принадлежит классу перестановленных расписаний .

Другими — словами, задачи

и

в данном случае не эквивалентны. Напомним, что задачи и эквивалентны, если все либо среди f._t имеются равные нулю и запись

означает, что длительность. Справедлива

Теорема 1.1. Задача

является NPтрудной в сильном смысле, если условие

означает, что требование iприбором Lне обслуживается.

Доказательство. Сформулируем соответствующую задачу распознавания: определить, существует ли расписание s°, при котором

для заданного числа у. Покажем, что к этой задаче сводится задача о 3-разбиении. Для преобразования входной информации задачи о 3-раэбиении во входную информацию индивидуальной задачи распознавания необходимо значения

и у выразить через

Положим

и разобьем множество N на две группы: и-требования, обозначаемые U_ij

и v-требовання, обозначаемые

Положим

, и зададим / . Покажем, что в построенной задаче расписание S°, при котором существует тогда и только тогда, когда имеет решение задача о 3-разбиеиии. имеет решение задача о 3 разбиений.

1. Пусть задача о 3-разбиении имеет решение и

найденные трехэлементные подмножества элементов множества N⁰. Через

обозначим произвольную перестановку u-требований с номерами из множества . Прибор 1 функционирует без простоев во временном интервале ], а прибор 2 - в интервале [0; у]. При этом прибор 1 в интервале обслуживает требование . Прибор 2 в интервале обслуживает требование v₀, а в каждом из интервалов - последовательность требований Требование обслуживается прибором 2 в интервале

2. Пусть существует расписание s°. Так как

и прибор 2 функционирует в интервале [0; у] без простоев.

Рис.(1.1)

Прибор 1 завершает обслуживание всех требований не раньше момента времени у - Е. С учетом того, что задержки запрещены, последним требованием, которое обслуживает прибор 2, будет некоторое v-требование, а прибор 1 должен функционировать без простоев в интервале

. Поскольку требования , не отличаются друг от друга по длительностям обслуживания, не нарушая общности можно считать, что они обслуживаются прибором I в порядке возрастания их номеров. Отсюда сразу следует, что требования , обслуживаются при расписании s°так же, как и при расписании, представленном на рис. 1.1. Требование v_c обслуживается прибором 2 в интервале , так как это единственный незанятый подинтервал длины 2Е интервала Требования щ должны обслуживаться прибором 2 в интервалах . Обозначая через множество номеров и-требований, обслуживаемых прибором 2 в интервале , получаем решение задача о 3-разбиении. Тем самым за

действий задача о 3-раз-биении сведена к задаче о существовании расписания S°. Теорема доказана.