Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Читайте также:
  1. Алгоритмы
  2. Алгоритмы арбитража
  3. Алгоритмы взаимного исключения
  4. Алгоритмы возведения в степень в конечном поле
  5. Алгоритмы выполнения реляционных операций
  6. АЛГОРИТМЫ ЗАДАЧ ПРОЕКТИРОВАНИЯ
  7. Алгоритмы замещения страниц
  8. Алгоритмы и способы их описания
  9. Алгоритмы идентификации на основе замкнутых динамических систем
  10. Алгоритмы контроля параметров технологического процесса и состояния оборудования. Алгоритмы цифрового регулирования. Уравнения П, ПИ, ПИД регуляторов.
  11. Алгоритмы логического вывода в условиях определенности
  12. Алгоритмы маршрутизации

End.

Begin

Else

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

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

 

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

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

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

 

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

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

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

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

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

М= М1 x М2 x М3 x М4

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

Если вычислять М в порядке М1x(М2x(М34)), то потребуется 125000 операций, тогда как вычисления в порядке (М1x(М23))xМ4 занимают лишь 2200 операций.

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

 

 

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



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

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

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

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

Пусть число возможных дальнейших путей на каждом шаге конечно и фиксировано (например, равно 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; Просмотров: 194; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2018) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление ip: 54.166.141.69
Генерация страницы за: 0.003 сек.