LINEBURG


<< Пред. стр.

страница 5
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

которые нельзя определить в терминах обычных алгебраических выражений.


6.1.2 ПРИМЕРЫ NP - ПОЛНЫХ ЗАДАЧ
Задача 1. Расписание для мультипроцессорной системы.
38
Задано конечное множество A заданий, которые необходимо
выполнить в мультипроцессорной системе, состоящей из m процессоров.
Мультипроцессорная система - это система, в которой имеется несколько
независимых процессоров, на каждом из которых задача решается
независимо от загрузки остальных процессоров.
Для каждой задачи a?A известна длительность t(a) ?N ее решения.
Задано время T, в течение которого необходимо решить все задачи
множества A.
Вопрос: Можно ли так распределить задачи по процессорам, чтобы при
параллельном решении этих задач общее время решения всей совокупности
задач не превышало заданное T?
Задача 2. Минимальный набор тестов.
Задано конечное множество A возможных диагнозов заболевания.
Известно, что некоторые заболевания имеют частично совпадающие
симптомы, поэтому задан набор C=<C1,C2,…,Cn>; Ci?A, представляющий
двоичные тесты. Имеется некоторое натуральное число m, ограничивающее
число тестов, которые должен пройти один больной.
Вопрос: существует ли такое множество тестов C длины m, что для
любой пары ai, aj возможных диагнозов из A имеется некоторый тест,
различающий ai и aj, т.е. тест c?C равен 1 только для определенного
диагноза.
Задача 3. Сельский почтальон.
Задан граф G=(V,E), L(e) - длина каждого ребра и положительное
целое число K. Существует ли в G простой цикл, сумма длин ребер
которого не меньше K?
Задача 4. Упаковка в контейнеры.
Задано конечное множество U={u1, u2, ..., um} предметов, для каждого
из которых задано натуральное число s(ui) - линейный размер предмета ui.
Даны также положительное целое число B - вместимость контейнера и число
K - количество контейнеров.
Вопрос: Существует ли такое разбиение множества U на K
непересекающихся подмножеств U1, U2,...,UK, что сумма размеров предметов
из каждого подмножества Ui не превосходит B?
Задача 6. Составление кроссворда.
Заданы конечное множество слов W и матрица A из нулей и единиц
размером n*n. Вопрос: Можно ли составить кроссворд из слов множества W,
чтобы слова вписывались в клетки матрицы A, заполненные нулями?

Существует достаточно много методов ограниченного перебора
(оптимизация решения задачи в процессе решения), которые помогают
решить как классические задачи, так и реально поставленные задачи.
Надо заметить, что о решении любой задачи нельзя сказать, что оно
единственно с точки зрения применения какого-либо алгоритма, т.к.
39
реализация разных алгоритмов может быть одинаковой с точки зрения их
временной трудоемкости. Решение переборных задач часто рассматривается
с точки зрения теории графов, содержащей очень много методов
оптимизации.


6.2 ПЕРЕБОР ВАРИАНТОВ
Задача о коммивояжере.
Имеется N городов, расстояния между которыми заданы.
Коммивояжеру необходимо выйти из какого-либо города, посетить
остальные N-1 городов точно по одному разу и вернуться в исходный город.
Маршрут коммивояжера должен быть минимальной длины (стоимости).
Задача относится к NP- полным, но даже при простом переборе не
обязательно просматривать все варианты.
РЕШЕНИЕ. На каждом шаге будем проверять все возможные
следующие города (так сделаем для каждого первого города).

Программная реализация:
const max=100; var w:array[1..max,1..max]of integer; {Матрица
смежности} c{количество пройденных},n{количество городов},i,j:integer;
min{минимальная сумма},l{текущая}:longint;
t,r:array[1..max]of byte; {матрицы ответа}
is:array[1..max]of boolean; {были-ли мы в городе?}

procedure run; {основная процедура}
var i:byte;
begin
if c=n then {дошли?}
begin
if w[t[c],t[1]]<>-1 then {Если можем вернуться…}
if (min=-1)or(l+w[t[c],t[1]]<min) then {меньше…}
begin
min:=l+w[t[c],t[1]];
r:=t;
end;
exit;
end;
if (l>min)and(min<>-1) then exit; {слишком много-выходим}
for i:=1 to n do {по всем новым городам}
if is[i] then {если не были…}
if w[t[c],i]<>-1 then {…и можем добраться - входим}
begin
inc(l,w[t[c],i]);
is[i]:=false;
inc(c);
40
t[c]:=i;
run;
dec(c);
is[i]:=true;
dec(l,w[t[c],i]);
end;
end;

begin
assign(input,'input.txt');
reset(input);
readln(n); {Читаем данные}
for i:=1 to n do
begin
for j:=1 to n do
read(w[i,j]);
readln;
end;
close(input);
fillchar(t,sizeof(t),0);
fillchar(r,sizeof(r),0);
fillchar(is,sizeof(is),true);
min:=-1; {Не нашли пока}
l:=0;
c:=1;
for i:=1 to n do {по всем первым городам}
begin
t[1]:=i;
is[1]:=false;
run;
end;
assign(output,'output.txt');
rewrite(output);
writeln(min);
if min<>-1 then {нашли?}
begin
for i:=1 to n do
write(r[i],' ');
write(r[1]);
end;
close(output);
end.
41
6.3 ПЕРЕБОР С ВОЗВРАТОМ
Данный метод рассмотрим на примере классической задачи о
лабиринте: Дано клеточное поле, часть клеток занята препятствиями.
Необходимо попасть из некоторой заданной клетки в другую заданную
клетку путем последовательного перемещения по клеткам.
Классический перебор осуществляется по правилам, предложенным в
1891 году Э.Люка в "Математических досугах":
• в каждой клетке выбирается еще не исследованный путь;
• если из исследуемой в данный момент клетки нет путей, то
возвращаемся на один шаг назад (в предыдущую клетку) и
пытаемся выбрать другой путь.

Предлагаем написать самостоятельно!


6.4 ПЕРЕБОР С ОТСЕЧЕНИЕМ ВЕТВЕЙ И СКЛЕИВАНИЕМ
ВЕТВЕЙ
Рассмотрим задачу: на шахматной доске N*N требуется расставить N
ферзей таким образом, чтобы ни один ферзь не атаковал другой.
Все возможные расстановки ферзей СNN*N (для N=8 это около 4.4*104)
возможностей. Анализируя игру ферзя, можно заметить, что по условию
задачи каждый столбец может содержать не более одного ферзя, что дает N в
степени N расстановок (для N=8 это 1.7*107).

Никакие два ферзя нельзя поставить в одну строку, а поэтому, чтобы
вектор (A1,A2,...,AN) был решением, он должен быть перестановкой
элементов (1,2,...,N), что дает только N! (при N=8.4*104) возможностей.
Никакие два ферзя не могут находиться на одной диагонали, что еще
сокращает число возможностей (для N=8 в дереве остается 2056 узлов). Итак,
с помощью наблюдений можно исключить из рассмотрения большое число
расстановок N ферзей на доске размером N*N.
Идея слияния ветвей состоит в том, чтобы избежать выполнения одной
и той же работы: если решения для двух или более диапазонов данных
совпадают, то можно исследовать только одно из них. В задаче о ферзях
можно использовать склеивание, заметив, что если А1>N/2, то найденное
решение можно отразить и получить решение, для которого А1<=N/2, т.е. для
случаев А1=2 и А1=N-1 решения совпадают.

Программная реализация:
const n=4; var a:array[1..2*n,1..2*n]of byte; {Матрица-степень "битости"
клетки}
t:integer; {Количество поставленных ферзей}
vect:array[1..2*n]of byte; {Сама расстановка}
count:longint; {Их количество}
42
procedure correct(x,y,t:integer);
{Корректирует степени "битости" всех клеток}
{Т=1 - добавляет ферзя, Т=-1 - удаляет}
var i,j:integer;
begin
for i:=1 to 2*n do
for j:=1 to 2*n do
if (i=x) then inc(a[i,j],t) else {Вертикаль}
if (j=y) then inc(a[i,j],t) else {Горизонталь}
if (x-i)=(y-j) then inc(a[i,j],t) else {Одна диагональ}
if (x-i)=(j-y) then inc(a[i,j],t); {Другая диагональ}
end;

procedure print;
{Выводит расстановку и изоморфную ей - симметричную относительно
вертикали}
var i,j:integer;
begin
inc(count,2);
writeln('Расстановка № ',count-1,':');
write(' ');
for i:=1 to 2*n do
write(' ',chr(ord('a')+i-1));
writeln;
for i:=1 to 2*n do
begin
write(i:2);
for j:=1 to 2*n do
if vect[i]=j then write(' Ф') else
if odd(i+j) then write(' ') else write('--');
writeln;
end;
writeln;
writeln('Расстановка № ',count,':');
write(' ');
for i:=1 to 2*n do
write(' ',chr(ord('a')+i-1));
writeln;
for i:=1 to 2*n do
begin
write(i:2);
for j:=1 to 2*n do
if vect[i]=2*n+1-j then write(' Ф') else
if odd(i+j) then write(' ') else write('--');
writeln;
43
end;
writeln;
end;

procedure run;
var i:byte;
begin
if t=2*n then {Расставили всех}
begin
print;
exit;
end;
inc(t); {Добавляем}
for i:=1 to 2*n do
if a[t,i]=0 then {Если не бьётся...}
begin
vect[t]:=i;
correct(t,i,+1); {Корректировка}
run;
correct(t,i,-1); {Корректировка}
end;
dec(t); {Убираем ферзя}
end;

begin
assign(output,'output.txt');
rewrite(output);
fillchar(a,sizeof(a),0);
t:=1;
count:=0;
for vect[1]:=1 to n do {Первый ферзь-от 1 до 4, остальные в
симметричных}
begin
correct(1,vect[1],+1);
run;
correct(1,vect[1],-1);
end;
writeln('Всего: ',count,' расстановки');
close(output);
end.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ
1. Найти все способы расстановки ферзей на шахматной доске N*N.
(Для доски 8*8 - ответ 92.)
44
2. Задача о шахматном коне. Составить программу подсчета числа
способов обхода конем доски. (Общее число способов разметки доски 8*8
равно 64! - без сокращения перебора по логике очередного хода коня).
3. Составить таблицу из числа способов обхода конем шахматной
доски для небольших значений N и M. Определить, при каких значениях
начинается т.н. "зависание" ПК.
4. ПРО ЛЯГУШКУ. С одного берега болота на другой, между
которыми на различном расстоянии друг от друга расположены камни,
пытается перепрыгнуть лягушка. Расстояние между камнями оценивается
количеством единиц первоначальной скорости лягушки (Первоначальная
скорость =1). Составить программу движения лягушки по камням (с
минимальным количеством прыжков и/или минимальной длиной пути (эти
варианты могут и совпадать)), если, находясь на камне (или на берегу), она
может свою скорость:
A) оставить прежней;
B) уменьшить на единицу;
C) увеличить на единицу.
Лягушка может двигаться как вперед, так и назад. Составить тесты для
отсутствия решения.


6.5 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
(т.н. Табличный метод)
6.5.1 АЛГОРИТМ ДИНАМИЧЕСКОГО ПРОГРАМИРОВАНИЯ
Динамическое программирование - метод оптимизации,
приспособленный к задачам, в которых требуется построить решение с
максимизацией или минимизацией, т.е. оптимальным значением некоторого
параметра.
Его алгоритм можно сформулировать так:
1. Выделить и описать подзадачи, через решение которых будет
выражаться искомое решение;
2. Выписать рекуррентные соотношения (уравнения), связывающие
оптимальные значения параметра для всех подзадач;
3. Вычислить оптимальное значение параметра для всех подзадач;
4. Построить само оптимальное решение.
В задачах на подсчет количеств допустимых вариантов пункт 4 не
нужен.
Автор Д.П. Беллман так сформулировал принцип оптимальности:
каково бы ни было начальное состояние на любом шаге и решение,
выбранное на этом шаге, последующие решения должны выбираться
оптимальными относительно состояния, к которому придет система в конце
данного шага.
45
Использование этого принципа гарантирует, что решение, выбранное
на любом шаге, является не локально лучшим, а лучшим с точки зрения
задачи в целом.
Данный метод усовершенствует решение задач, решаемых, например,
с помощью рекурсий или перебора вариантов.


6.5.2 УСЛОВИЯ ПРИМЕНЕНИЯ ДИНАМИЧЕСКОГО
ПРОГРАММИРОВАНИ:
1. Оптимальное решение задачи выражается через оптимальное
решение задач меньшей размерности, представимых в виде подзадач
(подпрограмм). Улучшая решение подзадач, тем самым, улучшается решение
общей задачи;
2. Небольшое число подзадач, что позволяет хранить решения каждой
подзадачи в таблице. Уменьшение числа подзадач происходит из-за
многократного их повторения (т.н. перекрывающиеся подзадачи).
3. Дискретность (неделимость) величин, рассматриваемых в задаче.
4. Один из главных критериев, когда принцип ДП дает эффект
уменьшения временной сложности: если в процессе решения необходимо
многократно перебирать одни и те же варианты (за счет увелечения
емкостной сложности уменьшается временная сложность).


6.5.3 РЕАЛИЗАЦИЯ АЛГОРИТМА ДП

6.5.3.1 СВЕДЕНИЕ ЗАДАЧИ К ПОДЗАДАЧАМ
Одним из основных способов решения задач является их сведение к
решению такого набора подзадач, чтобы, исходя из решений подзадач, было
возможно получить решение исходной задачи. При этом для решения
исходной задачи может потребоваться решение одной или нескольких
подзадач.

ПРИМЕР.
Рассмотрим задачу нахождения суммы N элементов таблицы A.
Пусть функция S(N) соответствует решению нашей исходной задачи.
Эта функция имеет один аргумент N - количество суммируемых элементов
таблицы A. Понятно, что для поиска суммы N элементов достаточно знать
сумму первых N-1 элементов и значение N-го элемента. Поэтому решение
исходной задачи можно записать в виде соотношения S(N) = S(N - 1) + a[N].
Следует отметить, что это соотношение справедливо для любого
количества элементов N>1.
Это соотношение можно переписать в виде S(i) = S(i - 1) + a[i] при i>1,
S(0) = 0.
46
Последовательное применение первого соотношения при i = 1, 2, ..., N
и используется при вычислении суммы N элементов, при этом вычисление
функции производится от меньших значений аргументов к большим.

S[0]: = 0;
for i:= 1 to N do
S[i]: = S[i - 1] + a[i];

6.5.3.2 ПОНЯТИЕ РЕКУРРЕНТНОГО СООТНОШЕНИЯ

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

ПРИМЕР.
Вычислить сумму S=1+1/x+1/x2+...+1/xN при x, не равном 0. Можно
записать следующее соотношение:
S(i) = S(i - 1) + a(i), i>1, где a(i) = 1/xi, S(0) = 1.
Возникла новая задача - найти способ вычисления a(i). Для этого
можно воспользоваться тем же приемом - попытаться вычислить a(i) через
значение a(i - 1). Соотношение между значениями a(i) и a(i - 1) имеет
следующий вид:
a(i) = a(i - 1)/x, i>1, a(0) = 1
Поставленную задачу можно решить следующим образом.
S[0]: = 1;
a[0]: = 1;
for i:=1 to N do
begin
a[i]: = a[i - 1]/x;
S[i]: = S[i - 1] + a[i]
end;

<< Пред. стр.

страница 5
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign