Эвристические методы

Begin

End

Else

Then

Begin

Then

Begin

Begin

Begin

End

Begin

Then

Begin

End.

Begin

Begin

Var

Type

Const

Begin

Then

Begin

Then

End.

Then

Begin

{Ввод массива Х}

Number:=1;

For I:=2 To N Do

If Abs(X [I]) > Abs(X [Number])

Number:=I;

WriteLn (Number)

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

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

Применяя метод перебора, эту задачу можно решать так: перебрать все пары точек из заданных и определить номера тех, расстояние между которыми наибольшее (наибольший модуль разности координат). Такой полный перебор реализуется через два вложенных цикла:

Number1:=1;

Number2:=2;

For I:=l to N do

For J:=l to N do

If Abs(X[I]-X[J])>Abs(X[Numberl]-X[Number2])

Number1:=I;

Number2:=J

End;

Очевидно, что такое решение задачи нерационально. Здесь каждая пара точек будет просматриваться дважды, например при i = 1, j = 2 и i = 2, j = 1.

Для случая п = 100 циклы повторят выполнение 100 * 100 = 10000 раз.

Выполнение программы ускорится, если исключить повторения. Исключить также следует и случай совпадения значений i и j.

Тогда число повторений цикла будет равно .

При n = 100 циклы повторят выполнение 4950 раз.

Для исключения повторений нужно в предыдущей программе изменить начало внутреннего цикла с 1 на i +1. Программа примет вид:

Number1:=1;

Number2:=2;

For I:=l to N do

For J:= I+l to N do

If Abs(X[I]-X[J])>Abs(X [Numberl]-X [Number2])

Number1:=I;

Number2:=J

End;

Рассмотренный вариант алгоритма назовем перебором без повторений.

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

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

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

For I:=l to N do

For J:=I+1 to N do

For K:=J+1 to N do

If X[I]+X[J]+X[K] = 10

Then WriteLn (X[I],X[J],X[K]);

А теперь представьте, что из массива X требуется выбрать все группы чисел, сумма которых равна десяти. В группах может быть от 1 до n чисел. В этом случае количество вариантов перебора резко возрастает, а сам алгоритм становится нетривиальным.

Казалось бы, ну и что? Машина работает быстро! И все же посчитаем. Число различных групп из п объектов (включая пустую) составляет 2ⁿ. При п = 100 это будет 2¹⁰⁰ = 10³⁰. Компьютер, работающий со скоростью миллиард операций в секунду, будет осуществлять такой перебор приблизительно 10 лет. Даже исключение перестановочных повторений не сделает такой переборный алгоритм практически осуществимым.

Путь практической разрешимости подобных задач состоит в нахождении способов исключения из перебора бесперспективных с точки зрения условия задачи вариантов

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

Для того, чтобы написать программу решения этой задачи нужно решить два вопроса:

• как организовать данные;

• как построить алгоритм.

Информацию о форме лабиринта будем хранить в квадратной матрице Lab символьного типа размером N*N, где N— нечетное число (чтобы была центральная точка). На профиль лабиринта накладывается сетка так, что в каждой ее ячейке находится либо стена, либо ход.

Матрица отражает заполнение сетки: элементы, соответствующие ходу, равны пробелу, а стене — какому-нибудь символу (например, букве м). Путь движения по лабиринту будет отмечаться символами +.

Например, приведенный выше средний рисунок соответствует следующему заполнению матрицы lab:

м	м	м	м	м	м	м	м	м	м	м
м		+	+	+			м
м	м	+	м	+	м		м		м	м
м		+	м	+	м	м	м		м	м
м	м	+	м	+	м					м
6м	м	+	м	+	+		м	м	м	м
м	м	+	м	м	м	м	м	м	м	м
м	м	+	+	+						м
м			м	+	м	м	м		м	м
м	м	м	м	+	+	+	+	+		м
м				м	м	м	м	+	м	м

Исходные данные — профиль лабиринта (исходная матрица Lab без крестиков); результат — все возможные траектории выхода из центральной точки лабиринта (для каждого пути выводится матрица lab с траекторией, отмеченной крестиками).

Алгоритм перебора с возвратом еще называют методом проб. Суть его в следующем:

1. Из каждой очередной точки траектории просматриваются возможные направления движения в одной и той же последовательности. Для определенности будем считать, что просмотр будет происходить каждыйраз против часовой стрелки — справа-сверху-слева-снизу; шаг производится в первую же обнаруженную свободную соседнюю клетку; клетка, в которую сделан шаг, отмечается крестиком.

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

3. Если очередная клетка, в которую сделан шаг, оказалась на краю лабиринта (на выходе), то на печать выводится найденный путь.

Программу будем строить методом последовательной детализации. Первый этап детализации:

Program Labirint;

N=11; {размер лабиринта NxN клеток}

Field =Array [l.. N, l..N] Of Char;

Lab: field;

Procedure GO (Lab: Field; X,Y: Integer);

{Поиск путей из центра лабиринта до края – каждый найденный путь выводится на экран}

End;

{Ввод лабиринта}

GO (Lab, N div 2+1, N div 2+1) {начинаем с середины}

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

Запишем сначала общую схему процедуры без детализации: |

Procedure GO (Lab: Field; X,Y: Integer);

If {клетка (х,у) свободна}

{шаг на клетку (х,у)}

If {дошли до края лабиринта}

Then {печатается найденный путь}

Else {попытка сделать шаг в соседние клетки в условленной последовательности}

{возвращение на один шаг назад}

End;

Для вывода найденных траекторий составляется процедура PRINTLAB.

В окончательном виде программа будет выглядеть так:

Program Labirint;

Const N=11; {размер лабиринта NxN клеток}

Type Field=Array[l..N, 1..N] Of Char;

Var LAB: Field; X,Y: Integer;

Procedure PRINTLAB(LAB: Field);

{Печать найденного пути в лабиринте}

Var X,Y: Integer;

For X:=l to N do

For Y:=l to N do

Write(LAB[X,Y]);

WriteLn

End;

WriteLn

End; {печати}

Procedure GO(LAB: Field; X,Y: Integer);

If Lab[x,y]=' ' {если клетка свободна}

Lab[x,y]:='+'; {делается шаг}

If (X=l) Or (X=N) Or (Y=l) Or (Y=N) {край}

PRINTLAB(LAB){печатается найденный путь}

Begin {поиск следующего шага}

GO(LAB,X+1,Y);

GO(LAB,X, Y+l);

GO(LAB,X-1,Y);

GO(LAB,X,Y-1)

End;

LAB[X,Y]:='' {возвращение назад}

End; {процедуры GO}

Begin {основной программы} {ввод лабиринта}

For X:=l to N do

For Y:=l to N do

Read (LAB[X,Y]);

ReadLn End;

GO(LAB,N Div 2+1,N Div 2+1)

End.

Еще один пример программы с использованием рекурсивного определения процедуры.

Схема алгоритма данной программы типична для метода перебора с возвратом. По аналогичным алгоритмам решаются, например, популярные задачи об обходе шахматной доски фигурами или о расстановке фигур на доске так, чтобы они «не били» друг друга; множество задач оптимального выбора (задачи о коммивояжере, об оптимальном строительстве дорог и т.п.).

Замечание. Из-за использования массива lab в качестве параметра-значения в процедуре GO могут возникнуть проблемы с памятью при реализации программы на ЭВМ. В таком случае можно перейти к глобальной передаче массива.

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

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

Дата добавления: 2014-01-06