Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 14

Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр

стр.: 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16

Полный текст лекций можно скачать здесь

---

Function TStek.GetTop; {возврат значения Top}

begin

GetTop:=Top;

end;

Procedure TStek.ShowNext(var I: integer);

{стек выводится от вершины к началу}

Begin

Write(List[I],' ');

I:=I-1;

End;

Procedure TStek.Show(Ind: integer);

{ наследуется объектом TOcher, выдача массива List в разном порядке,}

{ благодаря виртуальности TStek.ShowNext и TOcher.ShowNext }

Var

J: integer;

Begin

For J:=1 to Top do

ShowNext(Ind);

WriteLn

End;

Constructor TOcher.Init;

Begin

Top:=0;

End;

Procedure TOcher.Udal;

Var

J: integer;

Begin

if Top=0 then WriteLn('Список пуст, удалять нечего !')

else

begin

For J:=1 to Top-1 do List[J]:=List[J+1];

Top:=Top-1

end

End;

Procedure TOcher.ShowNext(var I: integer);

{очередь выводится от начала к концу}

Begin

Write(List[I],' ');

I:=I+1; { в этом отличие от Stek.ShowNext }

End;

Begin { начало основной програмы }

Stek.Init; {обязательно для инициализации виртуальных методов}

Ocher.Init;

ClrScr;

B1:=True;

While B1 do

begin

WriteLn(' Выберите режим:');

WriteLn('1-работа со стеком');

WriteLn('2-работа с очередью');

WriteLn('3-конец работы');

ReadLn(M);

case M of

1: begin

B2:=True;

While B2 do

begin

WriteLn(' Выберите режим работы со стеком:');

WriteLn('1-добавление в стек');

WriteLn('2-удаление из стека');

WriteLn('3-вывод на экран');

WriteLn('4-возврат в главное меню');

ReadLn(N);

case N of

1: begin {добавление в стек}

Write('Введите новый элемент(целое число): ');

ReadLn(K);

Stek.Dopoln(K)

end;

2: Stek.Udal;

3: begin

K:=Stek.GetTop;

if K>0 then Stek.Show(K)

else WriteLn('Список пуст !')

end;

4: B2:=false

end

end

end;

2: begin

B2:=true;

While B2 do

begin

WriteLn(' Выберите режим работы с очередью:');

WriteLn('1-добавление в очередь');

WriteLn('2-удаление из очереди');

WriteLn('3-вывод на экран');

WriteLn('4-возврат в главное меню');

ReadLn(N);

case N of

1: begin

Write('Введите новый элемент(целое число): ');

ReadLn(K);

Ocher.Dopoln(K)

end;

2: Ocher.Udal;

3: begin

K:=Ocher.GetTop; {для проверки непустоты очереди}

if K>0 then Ocher.Show(1) {наследуется Tstek.Show}

else WriteLn('Список пуст !')

{по виртуальности ShowNext вывод в другом порядке}

end;

4: B2:=false

end

end

end;

3: B1:=false

end

end

End.

{ Другой вариант (раннее связывание):

1) снять описатель Virtual в заголовках процедуры ShowNext

в объектах TStek и TOcher;

2) повторить объявление и код процедуры Show в объекте TOcher

}

Таковы общие принципы ООП. Не рассмотрены некоторые детали реализации ООП. Например, как и любые типы данных в Паскале, объекты можно размещать в динамической памяти с помощью процедуры New. Объект может включать секцию описания скрытых полей и методов, которые "не видны” программисту, если этот объект получен в рамках TPU-модуля. Более полная концепция ООП реализована в языке С++.

8. Алгоритмы перебора вариантов

8.1. Поиск с возвратом

Идею поиска с возвратом легче всего понять на примере следующей задачи прохода через лабиринт.

На клетчатой бумаге имеется прямоугольник. Заданы отрезки прямых, отделяющие клетки друг от друга и определяющие лабиринт. Требуется из начальной клетки попасть в конечную за некоторое число ходов. Ход состоит в перемещении из текущей клетки в соседнюю слева, справа, сверху либо снизу в пределах прямоугольника без пересечения отрезков прямых.

Например, в этом лабиринте требуется попасть их левого нижнего угла в правый верхний. Один из способов прохода через лабиринт – двигаться из начальной клетки в соответствии с двумя правилами:

1. В каждой клетке выбирать еще не исследованный путь.

2. Если из текущей клетки нет неисследованных путей, то нужно вернуться назад на ту клетку, из которой пришли в текущую.

Первое правило говорит о том, как расширить исследуемый путь, если это возможно, а второе правило – о том, как выходить из тупика.

В этом и состоит сущность поиска с возвратом: продолжать расширение исследуемого решения до тех пор, пока это возможно, и когда решение нельзя расширить, возвращаться по нему и пытаться сделать другой выбор на самом близком шаге, где имеется такая возможность. Если нужно найти все решения, то после нахождения очередного из них также производится возврат.

В общем случае решение задачи состоит из вектора (a₁, a₂, … ) конечной, но не определенной длины, удовлетворяющего некоторым ограничениям. Каждое a_i является элеменом конечного линейно упорядоченного множества A_i. При полном переборе должны рассматриваться элементы множества A₁* A₂ * …*A_i для i = 1,2,…Здесь символ ‘*’ обозначает декартовое произведение множеств.

В качестве исходного частичного решения выбирается пустой вектор ( ) и на основе имеющихся ограничений выясняется, какие элементы из A₁ являются кандидатами в a₁; обозначим это подмножество через S₁. В качестве a₁ выбирается первый элемент множества S₁. В результате получается частичное решение (a₁). Далее в соответствии с ограничениями и выбранным элементом a₁ выбирается элемент a₂ из множества S₂ и т. д. Если на шаге k частичное решение (a₁, a₂, …, a_k-1) не представляет возможностей для выбора элемента a_k, то выбирается новый элемент a_k-1. Если a_k-1 выбрать нельзя, возвращаемся еще дальше и выбирается новый элемент a_k-2 и т. д.

Этот процесс удобно описать с помощью дерева.(.....)

Обход дерева в порядке сверху вниз соответствует схеме поиска с возвратом.

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

Другим распространенным примером для алгоритма поиска с возвратом является задача о восьми ферзях. Требуется раставить на шахматной доске 8 ферзей так, чтобы они не атаковали один другого. Иными словами они должны стоять на разных горизонталях, вертикалях и диагоналях.

В каждой строке должен находиться ровно один ферзь, поэтому решение можно представить вектором (a₁, a₂, …, a₈), в котором a_i – номер столбца ферзя из строки с номером i. Более того, в каждом столбце должен быть в точности один ферзь, поэтому a_i ≠ a_j при i ≠ j. Наконец, поскольку ферзи не должны атаковать друг друга по диагонали, то ‌ a_i - a_j ‌ ≠ ‌ i-j ‌, если i ≠ j.

Указанные ограничения существенно снижают размерность задачи. Существуют 8⁸ вариантов расположения ферзей по одному в каждой строке, 8!=40320 вариантов с учетом того, что ферзи должны быть в разных столбцах, и всего 2096 вариантов, учитывая дополнительно их расположение на разных диагоналях.

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

Типичной задачей поиска с возвратом является поиск путей между двумя вершинами на графе в глубину. Как и в задаче с лабиринтом, можно отсекать бесперспективные для дальнейшего исследования вершины.

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

8.2. Метод ветвей и границ

Метод ветвей и границ является специальным типом поиска с возвратом. Ограничения основываются на предположении, что каждое решение связано с определенной стоимостью. Для применения метода ветвей и границ стоимость должна быть определена для частичных решений. Кроме того для всех частичных решений (a₁, a₂, …, a_k-1) и для всех расширений (a₁, a₂, …, a_k) должно выполняться

F (a₁, a₂, …, a_k-1) ≤ F (a₁, a₂, …, a_k),

где F – функция стоимости. Когда стоимость обладает этим свойством, то при нахождении решения с наименьшей стоимостью можно отбросить частичное решение (a₁, a₂, …, a_k), если его стоимость больше или равна стоимости ранее найденных решений. В большинстве случаев функция стоимости неотрицательна и даже удовлетворяет более сильному требованию

F (a₁, a₂, …, a_k) = F (a₁, a₂, …, a_k-1) + С(a_k),

где С(a_k) ≥ 0 – функция, определенная для всех a_k.

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

8.3. Игровые деревья. Принцип минимакса

Существенно другой разновидностью метода ветвей и границ является метод, встречающийся при построении деревьев игр.

Рассмотрим детерминированую игру, в которой игроки делают ходы поочередно. Детерминированность игры определяется следующими моментами:

1. Определена исходная позиция (в картах или домино это не так).

2. Оба игрока имеют полную информацию о текущей позиции (снова в картах или домино это не выполняется).

3. Ходы делаются в пределах правил, но по желанию игроков (в нардах и других играх с костями это не так).

Примерами детерминированных игр являются шашки, шахматы, крестики-нолики.

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

Оценка может быть статической и динамической, которая учитывает возможные ответы противника. Динамическая оценка более точная. Например, можно взять незащищенного ферзя, а в ответ получить мат в два хода.

Возможное течение игры можно представить деревом. Корнем дерева является исходная или текущая позиция. Сыновьям корня соответствуют позиции, получающиеся после сделанного хода. Каждая из таких позиций порождает новое множество позиций, получающихся после ответа противника и т. д. Листьям дерева соответствуют конечные позиции (в шахматах мат, пат, теоретически ничейные позиции и т. п.). Листья располагаются на разных уровнях дерева.

Назовем игроков ПЛЮС и МИНУС. Выбор хода каждого игрока соответствует выбору одного из сыновей вершины, которая описывает текущую позицию. В дереве игры уровни вершин, в которых выбираются ходы игроков ПЛЮС и МИНУС, чередуются. Рассмотрим простейший способ построения оценочной функции позиций с точки зрения одного из игроков, например, игрока ПЛЮС.

Присвоим листьям, соответствующим выигрышным позициям, оценку +1, ничейным 0, проигрышным -1. Пусть некоторая вершина дерева A, сыновями которой являются только листья, соответствует ходу игрока ПЛЮС. Очевидно, он должен выбрать одного из сыновей с масимальным значением оценки, поэтому примем это максимальное значение в качестве оценки вершины A. Отцовская для A вершина B соответствует ходу игрока МИНУС. Поскольку оценки в листьях устанавливались для игрока ПЛЮС, игрок МИНУС должен наоборот выбирать сына с минимальной оценкой, предполагая, что его противник сделает лучший ход, то есть оценкой вершины B станет минимум оценок сыновей. В этом и состоит принцип минимакса. Он получен в предположении, что каждый игрок стремится к наивысшему результату при условии наилучших ходов противника.

Таким образом, корень дерева получит оценку +1, 0 или –1, что предопределяет результат игры. На практике все обстоит сложнее. В большинстве игр дерево настолько велико, что не поддается подобным расчетам. Например, в шахматах белые могут сделать 20 вариантов первого хода, на каждый из которых может быть 20 вариантов ответа противника, то есть после полного первого хода может получиться 400 различных позиций. Приходится дерево игры строить не до конечных позиций, а в листьях прибегать к статической оценке. С каждым сделанным ходом дерево достраивается вниз. Чем глубже строится дерево игры и чем точнее статические оценки, тем сильнее игрок, будь то человек или программа. Шахматист применяет неявные статические оценки, используя теорию, интуицию, пристрастие к определенным позициям, антипатии противника по отношению к некоторым позициям и т. п.