Труднорешаемые задачи Последовательный анализ вариантов (стр. 2 из 4)
Теорема 2. Задача
является NP-трудной в сильном смысле.Теорема 3. Задача
является NP-трудной в сильном смысле.Доказательство. Сформулируем соответствующую задачу распознавания. В обслуживающую систему, состоящую из двух приборов А и В, в момент времени d=0 поступает частично упорядоченное множество требований
N{1,2...., л}.. Каждая компонента связности графа редукции отношения -, заданного на N, является цепью. Длительность выполнения каждой операции равна единице. Требуется определить, существует ли расписание S°, при котором
для заданного значения у.Построим псевдополнномиальное сведение задачи о 3-разбиении к сформулированной задаче распознавания.
Положим:
, где 
На множестве N заладим отношение -, полагай / - Iтогда и только тогда, когда 
. Очевидно, каждая компонента связности графа редукции этого отношения представляет собой цепь.
Пусть процесс обслуживания каждого требования 
состоит в выполнении единственной операции. Для требований из множества N1положим L1= (В) при
. Для каждого 
, положим 
Для требования из множества
- линейно –упорядоченное и число его элементов равно 
, то при любом расписаний с общим временем обслуживания требований, равным у, требования множества N3n+1 должны обслуживаться непрерывно одно за другим начиная с момента времени d= 0. На рис. 2 представлен фрагмент расписания обслуживания требований множества при котором общее время обслуживания требований равно у. Это расписание является периодическим с периодом 
Рис(1.2)
Таким образом, обслуживание требований множества
при любом расписании с общим временем обслуживания требований, равным у, может быть осуществлено только в тех единичных интервалах, которые определяются последовательностью 
Покажем, что расписание S0можно построить тогда и только тогда, когда имеет решение задача о 3-раэбиении. Пусть существует разбиение множества № на n0 трехэлементных подмножеств
таких, что 
при j=1,0. Тогда, обслуживая множество требований 
интервале 
, в соответствии с отношением получаем расписание с общим временем обслуживания требований, равным у.Пусть существует расписание S°, при котором
.Так как суммарная длительность обслуживания всех требований прибором А (прибором В) равна у, то при расписании Sкак прибор А, так и прибор В в интервале [0; у] не простаивает. По условию обслуживание каждого требования 
для которого 
Учитывая, что в построенном при доказательстве теоремы 3 примере процесс обслуживания каждого требования
состоит из единственной операции, можно сделать вывод о том, что и задача 
является NP-трудной в сильном смысле.2. Алгоритм
Этап 1. Построить бесконтурный граф
в результате выполнения следующего шага не более чем q - 1 раз. Первоначально положить 
Пусть после выполнения
шагов получен смешанный граф 
, у которого l вершин отмечено и существует неотмеченная вершина i, в которую не заходит ни одна дуга, исходящая из неотмеченной вершины. (Если такой вершины нет, то в графе (Q,U) содержится контур. Конец.)Шаг 1 + 1. Отметить вершину i и в случае, если в графе G(1) есть ребра, инцидентные этой вершине, то заменить их исходящими из нее дугами. Полученный в результате граф обозначить G(J+1) = (Q,U(l+1), V(l+1)). Если V(l+1) =
, то бесконтурный граф построен: 
. В противном случае выполнить этот шаг, заменив l на l + 1.Этап 2. В соответствии с алгоритмом 3.1 построить которое допустимо относительно ориентированного графа
и смешанного графа G. Конец.Нетрудно убедиться в корректности описанного алгоритма, что и завершает доказательство теоремы .
Очевидно, трудоемкость этапа 1 алгоритма не превосходит
и, следовательно, общая трудоемкость построения активного расписания, допустимого относительно смешанного графа G, не превосходит 
Если для каждого графа G(1) в алгоритме рассматривать все возможные варианты выбора вершины i, то получим все множество P(G) = {G1 G2, ..., G} бесконтурных графов, порождаемых смешанным графом G. Следовательно, все множество допустимых относительно G активных расписаний можно построить за
элементарных действий.Пример 1. В условиях примера 3.1 (см. рис. 1) воспользуемся алгоритмом 2 для построения допустимого относительно С = (Q, V, V) расписания.
На этапе 1 алгоритма строим бесконтурный ориентированный граф из множества P{G). Положим G0= G и выберем на шаг 1 вершину 1, в которую не заходит ни одна дуга. Отметим вершину 1 и заменим дугами инцидентные ей ребра. Получим смешанный граф
На шаге 2 аналогичные преобразования проделаем для вершины 3, на шаге 3 — для вершины 4, на шаге 4 - для вершины 2, на шаге 5 - для вершины 9. Полученный в результате граф
представлен на рис1 в виде сетевого графика. 
Рис (2.1)
На этапе 2 воспользуемся алгоритмом 1 для построения активного расписания, допустимого относительно ориентированного графа
. Сначала сформируем списки потомков и списки предшественников каждой вершины 
, затем распределим вершины графа 
по рангам 
наконец, по формуле 1 вычислим значения 
для всех вершин 
последовательно в порядке неубывания рангов вершин. Полученные значения 
указаны около соответствующих вершин сетевого графика.