По вопросам приобретения обращаться

• Название: По вопросам приобретения обращаться
• Дата: 06.12.2019
• Размер: 5.46 Mb.
• Имя файла: Programmirovanie_v_algoritmakh.pdf
• Тип: Документы; #98984
• страница: 6 из 26

Часть текста из основной программы имеет вид:
For
N+2 Do
For j:=-l
M+2 Do
"барьерные"
тем самым исключая лишние
операторы If, утяжеляющие текст
*}
For
N Do
' For
M Do A[i,j] : =0
t:=0;
For
To N Do
For j : =1 To M Do
(i,j ,1) ;

Перебор и методы его сокращения
способов обхода конем доски
N,'*'
- ' ,t) ;
Если попытаться составить таблицу из числа способов обхо- да конем шахматной доски для значений N и М, то окажется,
что быстродействия вашего компьютера не хватит для решения этой задачи (а вы им так гордились!). Изменим решение задачи о шахматном коне так, чтобы находился только один вариант обхода конем доски. Применим обход доски, основанный на правиле Варнсдорфа выбора очередного хода (предложено более
150 лет тому назад). Суть последнего в том, что при обходе шахматной доски коня следует ставить на поле, из которого он может сделать минимальное количество перемещений на еще не занятые поля, если таких полей несколько, можно выбирать любое из них. В этом случае в первую очередь занимаются уг- ловые поля и количество «возвратов» в логике значительно уменьшается (найдите,
каких значений N и М ваш компь- ютер будет справляться с задачей).
Вариант процедуры Solve для этого случая.
Procedure
Var
.8] Of Integer;
xn,yn,i,j
-.Integer ;
Begin
A[x,y]:=q;
If
Then Begin
For i:=l To 8 Do Begin
массива
*}
: =0
: =x+Dx [i ] ;yn :
[i ] ;
If
Then Begin
For j
To 8 Do
If (A[xn+Dx[j]
Then
End
Else
End;
i:=l;
While
Do Begin
{*Ищем клетку, из которой можно сделать
наименьшее число
*}
For j:=2
8 Do If
Then Begin
If
And
Then Begin

Перебор и методы его совращения 8!)
:
использованную
в переборе клетку. *}
End;
Inc(i) ;
End;
End
Else Begin
решения>;
halt;{*Исключение этого оператора, нарушающего
структурный стиль
одна из
требуемых модификаций программы.
End;
End;
Пример 3 — «Задача о лабиринте». Классическая задача для темы. Как и предыдущие задачи, ее не обходят внима- нием в любой книге по информатике. Формулировка проста.
Дано клеточное поле, часть клеток занята препятствиями. Необ- ходимо попасть из некоторой заданной клетки в другую задан- ную клетку путем последовательного перемещения по клеткам.
Изложение задачи опирается на рисунок произвольного лаби- ринта и «прорисовку» действий по схеме простого перебора.
Классический перебор выполняется по правилам, предложен- ным в 1891 году Э. Люка в «Математических развлечениях»:
• в каждой клетке выбирается еще не исследованный путь;
• если из исследуемой в данный момент клетки нет путей,
то возвращаемся на один шаг назад (в предыдущую клет- ку) и пытаемся выбрать другой путь.
Э. Люка в 1891 году сформулировал общую схему решения задач методом перебора вариантов. Решение первой задачи.
Program Labirint;
Const Nmax=...;
.4] Of
.4] Of
Type
Of Inte-
ger;
Var
Procedure
Begin
{*Ввод лабиринта, координат начальной и конечной
клеток. Границы поля отмечаются как
*};

90 3. Перебор и методы его сокращения
End;
Procedure Print;
Begin
{*'Вывод матрицы А - метками выделен путь выхода
из
End;
Procedure
- номер шага,
х,у - координаты клетки. *}
Var
Begin
If (x=xk) And (y=yk) Then Print
Else For
To 4 Do
Then Solve (x+Dx[i]
,k+l) ;
End;
Begin
End.
С помощью данной схемы находятся все возможные вариан- ты выхода из лабиринта. Их очередность определяется прави- лом (задается массивами констант Dx, Dy) просмотра соседних клеток. Если требуется найти один выход из лабиринта, то тре- буется, естественно, изменить решение. Проделайте работу, со- хранив при этом структурный вид программного кода.
Второй способ решения задачи о лабиринте (поиск кратчай- шего по количеству перемещений пути) называют «методом волны». Его суть. Начальную клетку помечают, например, мет- кой со значением 1, а затем значение метки увеличивается на единицу на каждом шаге. Очередное значение метки записыва- ется в свободные клетки, соседние с клетками, имеющими пре- дыдущую метку. В любой момент времени множество клеток,
не занятых препятствиями, разбивается на три класса: поме- ченные и изученные; помеченные и неизученные и непомечен- ные. Для хранения клеток второго класса всего использовать структуру дан- ных «очередь» (мы предполагаем, что она изучена ранее, например, по книге авто- ра «Основы программирования»). Про- цесс заканчивается при достижении клетки выхода из лабиринта (есть путь)

3. Перебор и методы его сокращения 91
или при невозможности записать очередное значение метки
(тупик). На рисунке иллюстрируется этот процесс. Темные клетки означают препятствия. Начальная клетка находится вверху слева, конечная — внизу справа. Кроме того, из рас- смотрения примеров должно следовать понимание того факта,
что выход из лабиринта имеет кратчайшую длину.
Program Labirint;
Const
Of
;
[1.
Of
0 -1) ;
Type
Of Integer;
Var
N,M: Integer;
Function
Type
.
.2] Of Integer;
Var
*}
Begin
чтения из
очереди. *};
{*Указатель записи в очередь.*}
*}
координаты
начальной клетки в очередь. *}
While
And
Do
очередь не пуста и не найдено
*}
указателю чтения берем элемент из
If (i=xk) And
Then
=True {*Если это
клетка выхода из
то решение
найдено. *}
Else
For t:=l
4 Do
If
Then
этой
клетке мы еще не были. *}
значение метки. *}

92
Перебор и методы его сокращения
:=i+Dx[t] ;
координаты
клетки в очередь. *}
End;
End;
работы функции Solve. *}
End;
Основная программа имеет вид.
Begin
лабиринта, координат начальной
и конечной клеток. Текст процедуры
не
*}
Assign
{*'Выводим результат (массив А) в файл.*}
If Solve Then
процедуры Print в силу
её очевидности не
*}
Else
('Нет пути'};
Close (Output);
End.
Модифицировать предыдущее решение так, чтобы находил- ся не один путь, а, например, t путей, если они существуют.
Пример 4 — «Задача о рюкзаке (перебор вариантов)». В
рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено). Максимальный вес рюкзака W. Каждый предмет типа имеет вес и стоимость
(£=1,2, ..., N). Требуется определить максимальную стоимость груза, вес которого равен W. Обозначим количество предметов типа i через тогда требуется максимизировать при ограничениях где
— целые квадратные скобки означают це- лую часть числа.
Рассмотрим простой переборный вариант решения задачи,
работоспособный только для небольших значений N (опреде- лить, для каких?). Итак, данные:
Const
Var
предметов,
максимальный вес. *}
Of
стоимость предметов.*}

3. Перебор и методы его сокращения 93
Of Integer;
Наилучшее текущее решения. *}
*}
Решение, его основная часть — процедура перебора:
Procedure
{*k -
порядковый номер группы
w - вес,
который следует набрать из оставшихся
st - стоимость текущего
*}
Var
Begin
If (k>N) And (st>MaxPrice) Then Begin {*Найдено
*}
End
Else If
Then
For i:=0 To
Div Weight [k] Do Begin
Now[k]:=i;
End;
End;
Инициализация переменных, вывод решения и вызываю- щая часть очевидны.
Пример 5 — «Задача о коммивояжере». Классическая фор-
мулировка задачи известна уже более 200 лет: имеются N горо- дов, расстояния между которыми заданы; коммивояжеру необ- ходимо выйти из какого-то города, посетить остальные N— 1
городов точно по одному разу и вернуться в исходный город.
При этом маршрут коммивояжера должен быть минимальной длины (стоимости).
Задача коммивояжера принадлежит классу iVP-полных т. е.
неизвестны полиномиальные алгоритмы ее решения. В задаче с
N городами необходимо рассмотреть маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях N невозможно за разумное время получить резуль- тат.
Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данной класси- ческой схеме реализации.
Структуры данных.
Const Max—...;
Var
Of Integer;
{ *Матрица расстояний между городами. *}

94 3. Перебор и методы его сокращения
Of
массив, элементы каждой строки матрицы
сортируются в порядке
но сами
элементы не
а изменяются
в матрице В номера столбцов матрицы А.*}
Пример. Ниже приведены матрицы
В (после сортировки элементов каждой строки матрицы А).
Примечание
Символом @ обозначено бесконечное расстояние.
Of
текущее решение и лучшее решение. *}
Of
элемента массива False говорит о том,
что в соответствующем городе коммивояжер
уже
*}
лучшего решения. *}
Идея решения. Пусть мы находимся в городе с номером v.
Наши действия.
Шаг 1. Если расстояние (стоимость), пройденное коммивоя- жером до города с номером не меньше стоимости найденного ранее наилучшего решения (BestCost), то следует выйти из дан- ной ветви дерева перебора.
Шаг 2. Если рассматривается последний город маршрута
(осталось только вернуться в первый город), то следует срав- нить стоимость найденного нового решения со стоимостью луч- шего из ранее найденных решений. Если результат сравнения положительный, то значения BestCost и BestWay следует изме- нить и выйти из этой ветви дерева перебора.
Шаг 3. Пометить город с номером v как рассмотренный, за- писать этот номер по значению Count в массив Way.
Шаг 4. Рассмотреть пути коммивояжера из города v в ранее не рассмотренные города. Если такие города есть, то перейти на эту же логику с измененными значениями v, Count, Cost, иначе на следующий шаг.

3. Перебор и методы его сокращения
95
Шаг 5. Пометить город v как нерассмотренный и выйти из данной ветви дерева перебора.
Прежде чем перейти к обсуждению логики, целесообразно разобрать этот перебор на примере. На рисунке приведен при- мер и порядок просмотра городов. В кружках указаны номера городов, рядом с кружками — суммарная стоимость проезда до этого города из первого.
Итак, запись логики.
Procedure
- номер текущего города; Count - счетчик числа
пройденных
Cost - стоимость текущего
*}
Var
Begin
If Cost>BestCost Then
текущего
решения превышает стоимость лучшего из
ранее
*}
If
Then Begin
город
пути. Добавляем к решению стоимость
перемещения в первый город и сравниваем
его с лучшим из ранее
If Cost
нарушает структурный стиль
программирования

"любой фрагмент логики
должен иметь одну точку входа и одну точку
выхода. Следует убрать его" . *}
End;

96 3. Перебор и методы его сокращения
с номером v
записываем его номер в путь
*}
For
N Do
If
Then Solve
города, в который
коммивояжер может пойти из
с номером
:
город с номером v
в число
*}
End;
Первый вызов — Solve(l,l,0). Разработка по данному «шаб- лону» работоспособной программы — техническая работа. Если вы решитесь на это, то есть смысл проверить ее работоспособ- ность на следующем примере (матрица А приведена ниже). Ре- шение имеет вид 1 8 9 2 5 6 10 7 4 3 1, его стоимость 158.
@
32 33 22 41 15 16 31 32
@
51 58 27 42 35 18 17 34 19 51
@
23 35 49 26 34 35 41 33 58 23
@
33 37 23 46 46 32 22 27 35 33
@
19 10 23 23 9
41 42 49 37 19
@
24 42 42 10 18 35 26 23 10 24
@
25 25 14 15 18 34 46 23 42 25
@
1 32 16 17 35 46 23 42 25 1
@
32 31 34 41 32 9
10 14 32 32
@
Оцените время работы программы. Если у вас мощный компьютер, то создайте матрицу и попытайтесь найти наилучшее решение с помощью разобранного метода. За- метим, что набор 2500 чисел — утомительное занятие и разум- ная лень — «двигатель прогресса».
3.3. Динамическое программирование
Идея метода. Это важнейший раздел изучаемой темы, поэто- му вполне применим принцип: чем больше разнообразных за- дач, тем лучше. Разбор основной идеи метода и ее обсуждение можно сделать на классической задаче о Черепашке. Черепаш- ке необходимо попасть из пункта в пункт В. На каждом углу она может поворачивать только на север или только на восток.
Время движения по каждой улице указано на рисунке. Требу-

Перебор и методы его сокращения
97
ется найти минимальное время, за которое Черепашка может попасть из пункта в пункт В.
Путь, показанный на рисунке линиями со стрелкой, требует
21 единицу времени. Отметим, что каждый путь состоит из 6
шагов: трех на север и трех на восток. Количество возможных путей Черепашки 20
Мы можем перебрать все пути и вы- брать самый быстрый. Это метод полного перебора (ответ —
21). Для вычисления каждого времени требуется пять опера- ций сложения, а для нахождения ответа — 100 операций сло- жения и 19 операций сравнения. Задача решается вручную.
Однако при N, равном 8, у Черепашки уже 12870 путей. Под- счет времени для каждого пути требует 15 операций сложения,
а в целом — 193050 сложений и 12869 сравнений, то есть по- рядка 200000 операций. Компьютер при быстродействии
1000000 операций в секунду найдет решение за 0.2 секунды, а человек? Предположим, что N равно 30, тогда количество раз- личных путей
Это очень большое число, его поря- док 10 1 7
. Количество операций, необходимых для поиска реше- ния, равно
Компьютер с быстродействием 1000000
операций в секунду выполнит за год порядка 3.2*10 13
операций
(подсчитайте). А сейчас нетрудно прикинуть количество лет,
требуемых для решения задачи.
Вернемся к исходной задаче. Начнем строить путь Черепаш- ки от пункта В. Каждому углу присвоим вес, равный минима- льному времени движения Черепашки от этого угла до пункта
В. Как его находить? От углов X, Y решение очевидно. Для угла Z время движения Черепашки в пункт В через угол X
равно 15 единицам, а через угол Y — 11 единицам. Берем ми- нимальное значение, т. е. вес угла будет равен 11. Продолжим вычисления. Их результаты приведены на рисунке. Путь, от- меченный стрелками, является ответом задачи. Оценим коли- чество вычислений. Для каждого угла необходимо выполнить не более двух операций сложения и одной операции сравнения,
т. е. три операции. При N, равном 300, количество операций —
3*301*301, это меньше 1000000, и компьютеру потребуется ме-

98 3. Перебор и методы его сокращения ныне одной секунды. Итак, много лет при N=30 и 1 секунда при iV=300.
Идея второго способа решения задачи основана на методе динамического программирования. Заслуга его открытия при- надлежит американскому математику Ричарду Беллману. Вы- делим особенность задачи, которая позволяет решить ее опи- санным способом. Мы начинаем с угла В, и для каждого угла найденное число является решением задачи меньшей размер- ности. Поясним эту мысль. Если бы мы решали задачу поиска пути Черепашки из пункта Т в пункт В, то найденное число
17 — решение задачи. Для каждого угла найденное значение времени не изменяется и может быть использовано на следую- щих этапах.
3.4. Примеры задач для разбора идеи метода динамического программирования
Пример 1 — «Треуголь-
ник». На рисунке изобра- жен треугольник из чисел.
Напишите программу, кото- рая вычисляет наибольшую сумму чисел, расположен- ных на пути, начинающем- ся в верхней точке треуго- льника и заканчивающемся на основании треугольника.
• Каждый шаг на пути может осуществлять- ся вниз по диагонали влево или вниз по диагонали вправо.
• Число строк в треугольнике > 1 и
<100.
• Треугольник составлен из целых чисел от 0 до 99.
Рассмотрим идею решения на при- мере, приведенном в тексте задачи.
Входные данные запишем в матрицу
Она, для примера, имеет вид:
Будем вычислять матрицу R:ar-
следующим об- разом, предварительно обнулив ее элементы:
For
N Do
7 3
8 2
4 0
8 1
7 5
0 0
0 4
2 0
0 0
4 6
0 0
0 0
5 0
0 0
0 0
7 10 18 20 24 15 16 25 30 15 20 27 19 26 24

3. Перебор и методы его сокращения 99
For j:=l
i Do
] ,
где
— функция вычисления максимального из двух чи- сел.
Осталось найти наибольшее значение в последней строке матрицы оно равно 30.
Пример 2 — «Степень числа». Даны два натуральных числа
N и k. Требуется определить выражение, которое вычисляет
Разрешается использовать операции умножения и возведе- ния в степень, круглые скобки и переменную с именем
Ум- ножение считается одной операцией, возведению в степень q
соответствует операция. Найти минимальное количество операций, необходимое для возведения в степень N. Желатель- но сделать это для как можно больших значений N.
Так, при N=5 требуются три операции —
Определим массив его элемент Op[i] предназначен для хранения минимального количества операций при возведении в степень i
Для вычисления выражения, дающего степень числа k, арифметические операции применяют в некоторой последовательности, согласно приоритетам и рас- ставленным скобкам. Рассмотрим последнюю примененную операцию.
Если это было умножение, тогда сомножителями являются натуральные степени числа которые в сумме дают N. Сте- пень каждого из сомножителей меньше и ранее вычислено,
за какое минимальное число операций ее можно получить.
Итак:
{по всем l
[р] +Ор [п-р]
.
Если последней операцией являлось возведение в степень, то
орп2
для всех р
- делителей N,
div p]+p-l} .
Результат —
Фрагмент реализации:
Const
Var
к: Integer;
Op:
Of Integer;
Procedure Solve;
Var i, j: Integer;
Begin
For i:=2 To N Do Begin
For j:=2 To
Do Begin

3. Перебор и методы его сокращения
, Op [j ]+Ор [i-j ]+1) ;
If i Mod j=0 Then
,
Div j]+j-l)
End;
End;
End;
Пример 3 — «Алгоритм
(из молеку- лярной биологии). Молекулы ДНК содержат генетическую ин- формацию. Моделью ДНК можно считать длинное слово из че- тырех букв (А, Г, Ц, Т). Даны два слова (длины М и N),
состоящие из букв А, Г, Ц, Т. Найти подпоследовательность наибольшей длины, входящую в то и другое слово.
Пусть есть слова ГЦА-
ТАГГТЦ и АГЦААТГГТ.
Схема решения иллюстри- руется следующим рисун- ком. На рисунке закраше- ны клетки, находящиеся на пересечении строки и столбца с одинаковыми буквами. Принцип запол- нения таблицы W следую- щий: элемент W[i,j] равен наибольшему из чисел
W[i-l,j], W[i,j-1], а если клетка закрашена, то и
Формиро- вание первой строки и первого столбца выполняется до заполне- ния таблицы и осуществляется так: единицей отмечается первое совпадение, затем эта единица автоматически заносится во все оставшиеся клетки. Например, W[3,l] — первое совпадение в столбце, затем эта единица идет по первому столбцу. Подпосле- довательность формируется при обратном просмотре заполнен- ной таблицы от клетки, помеченной максимальным значением.
Путь — это клетки с метками, отличающимися на единицу, бук- вы выписываются из закрашенных клеток. Последовательность этих букв — ответ задачи. Для нашего примера две подпоследо- вательности: ГЦААГГТ и основной логики.
For i:=l
Length
Do
For j:=l To Length (S2) Do Begin
A[i,j] :=Max(A[i-l,j] ,A[i,j-l]) ;

3. Перебор и методы его сокращения 101
If
Then A[i ,
(A[i
A[i-l,j-l]+l) ;
End;
A [Length
(S2) ]) ;
Пример 4 — «Разбиение выпуклого N-угольника». Дан вы- пуклый заданный координатами своих вершин в порядке обхода. Он разрезается N-2 диагоналями на треуголь- ники. Стоимость разрезания определяется суммой длин всех использованных диагоналей. Найти разрез минимальной стои- мости.
Идея решения разбирается с использованием следующего рисунка.
Обозначим через стоимость разрезания мно- гоугольника диагона- лями на треугольники. При или следовательно, l>k+2. Вер- шина с номером i, i изменя- ется от до опреде- ляет какое-то разрезание многоугольника
Стоимость разрезания определим как:
диагонали
диагонали
При этом следует учитывать, что при диагональ является стороной многоугольника и ее длина считается равной нулю. Аналогично при i=l—l.
Пример 5 — «Задача о камнях». Из камней весом набрать вес W или, если это невозможно, максимально близ- кий к W снизу вес.
Рассмотрим идею решения на следующих данных: N равно
5,
Сформируем матри- цу
(A:Array[l..N,0..W] Of Integer), в которой номер строки соответствует номеру камня, а номер столбца — набираемому весу. В нулевой столбец запишем нули, в первую строку (по столбцам) до веса первого камня нули, а затем вес первого камня (пытаемся набрать требуемый вес одним камнем). Во второй строке фиксируем результат набора веса с помощью двух камней и т. д. После заполнения А имеет вид, показан- ный на рисунке. Вес 19 набрать нельзя, ближайший снизу вес 18.