Алгоритмы с возвратом

End.

Begin

Else

m ¬ (i+j-1)/2;

return MERGE(SORT(i, m), SORT(m+ 1, j))

Подсчёт числа сравнений в алгоритме 4.4 приводит к рекуррентным уравнениям

решением которых по теореме 4.1 является Т (n)= О (nlog₂n). Для больших n сбалансированность размеров подзадач даёт значительную выгоду. Аналогичный анализ показывает, что общее время работы процедуры SORT, затрачиваемое не только на сравнение, также есть О (nlog₂n).

4.3.4. Динамическое программирование

Рекурсивная техника полезна, если задачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим. Из теоремы 4.1вытекает, что если сумма размеров подзадач равна an для некоторой постоянной а >0, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность. Но если очевидное разбиение задачи размера n сводит её к n задачам размера n-1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность.

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

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

Рассмотрим эту технику на примере вычисления произведения k матриц М=М₁ x М₂ x...x М_k, где M_i - матрица с r_i-1 строками и r_i столбцами. Порядок, в котором эти матрицы перемножаются, может существенно сказаться на общем числе операций, требуемых для вычисления М, независимо от алгоритма, применяемого для умножения матриц.

Пример 4.1. Будем считать, что умножение (р x q)-матрицы на (q x r)-матрицу требует pqr операций, и рассмотрим произведение (в квадратных скобках указаны размерности матриц).

М= М₁ x М₂ x М₃ x М₄

[10 x 20] [20 x 50] [50 x 1] [1 x 100]

Если вычислять М в порядке М₁x(М₂x(М₃xМ₄)), то потребуется 125000 операций, тогда как вычисления в порядке (М₁x(М₂xМ₃))xМ₄ занимают лишь 2200 операций.

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

Особенно интересный раздел программирования - это задачи из области “искусственного интеллекта”. Здесь нужно строить алгоритмы, которые находят решение определённой задачи не по фиксированным правилам вычисления, а методом проб и ошибок. Обычно процесс проб и ошибок разделяется на отдельные подзадачи. Часто эти подзадачи наиболее естественно описываются с помощью рекурсии. Процесс проб и ошибок можно рассматривать в общем виде как процесс поиска, который постепенно строит и просматривает (а также обрезает) дерево подзадач. Во многих случаях такие деревья поиска растут очень быстро, обычно экспоненциально, в зависимости от заданного параметра. Соответственно увеличивается стоимость поиска. Часто дерево поиска можно обрезать, используя только эвристические соображения, и тем самым сводить количество вычислений к разумным пределам.

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

Задача “Обход конем шахматной доски n x n ”. Конь помещается на поле с начальными координатами Х₀, У₀. Нужно покрыть ходами коня всю доску (осуществить обход доски) за n ²-1 ход, при том, что каждое поле посещается ровно один раз.

Эта задача покрытия n ² полей сводится к более простой: или выполнить очередной ход, или установить, что никакой ход невозможен.

Характерная черта этого алгоритма состоит в том, что он предпринимает какие-то шаги по направлению к общему решению, эти шаги фиксируются (записываются), но можно возвращаться обратно и стирать записи, если оказывается, что шаг не приводит к решению, а заводит в “тупик”. Такое действие называется возвратом.

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

procedure try (i)

begin k:= 0; (*инициировать выборку возможных шагов*)

repeat k:= k +1; выбрать k-й возможный путь;

if приемлемо then

begin записать его;

if i < n then (*решение неполно*)

begin try (I +1); (*попробовать очередной шаг*)

if неудачно then стереть запись

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