Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. A) Плавно или с помощью кнопок- строки заголовка.
  2. C. Ветвящихся алгоритмов
  3. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
  4. III. Алгоритмическая конструкция ветвление и ее использование в языке Visual Basic
  5. IV. Алгоритмическая конструкция цикл и ее использование в языке Visual Basic
  6. LINUX|| Алгоритм замещения страниц в ОС Linux.
  7. LINUX|| Реализация потоков в ОС Linux.
  8. Lt;variant>возлагается. Эта обязанность состоит в том, что обвиняемому дозволяется обратиться за юридической помощью
  9. quot;Определение показателя преломления и концентрации растворов с помощью рефрактометра".
  10. А в это время в Китае остановили попытку распыления новой формы гриппа с помощью авиации.

Рассмотрим общий случай, когда решение задачи имеет вид вектора 1, а2,…), длина которого не определена, но ограничена сверху некоторым (известным или неизвестным) числом r, а каждое аi является элементом некоторого конечного линейно упорядоченного множества Аi. Таким образом, при исчерпывающем поиске в качестве возможных решений мы рассматриваем элементы множества А1 ´ А2 ´… ´Аi для любого i, где i£r , и среди них выбираем те, которые удовлетворяют ограничениям, определяющим решение задачи.

В качестве начального частичного решения берется пустой вектор ( ) и на основе имеющихся ограничений выясняется, какие элементы из А1являются кандидатами для их рассмотрения в качестве а1(множество таких элементов а1из А1 ниже обозначается через а1). В качестве а1 выбирается наименьший элемент множества S1, что приводит к частичному решению (а1) . В общем случае ограничения, описывающие решения, говорят о том, из какого подмножестваSk множества Аk выбираются кандидаты для расширения частичного решения от 1, а2,… , аk-1) до 1, а2,… , аk-1, аk) . Если частичное решение 1, а2,… , аk-1)не предоставляет других возможностей для выбора новогоаk (т.е. у частичного решения 1, а2,… , аk-1)
либо нет кандидатов для расширения, либо все кандидаты к данному моменту уже использованы), то происходит возврат и осуществляется выбор нового элемента аk-1 из Sk-1 . Если новый элемент аk-1 выбрать нельзя, т.е. к данному моменту множество Sk-1 уже пусто, то происходит еще один возврат и делается попытка выбрать новый элемент аk-2 и т.д.

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

k:=1;
Вычислить S1(*например, в качестве S1взять А1 *);
while k>0 do
while не пусто Sk do (* Продвижение *)
В качестве аkвзять наименьший элемент из Sk , удалив его из Sk
if(а1, а2,… , аk) является решением then Записать это решение
end;
if k<r then k := k + 1; Вычислить Sk
(* Например, в качестве Skможно взять Аk *)
end
end;
(* Возврат *) k := k - 1
end;
(* Все решения найдены *)

 

Более коротко общую процедуру поиска с возвращением можно записать в рекурсивной форме:

procedure ПОИСК (X: ВЕКТОР; i : Integer);
begin
if Х является решением then записать его end;
if i <= r then Вычислить Si
for all a from Si do ПОИСК (X || (a),i+1) end
end
end

Здесь || обозначает операцию конкатенации (соединения) двух векторов, т.е.
(а1, а2,… , аn) || (b1, b2,… , bm)= (а1, а2,… , аn,,b1, b2,… , bm) и () || (а1) для любых а1, а2,… , аn,,b1, b2,… , bm.

Вызов ПОИСК((),1) находит все решения, причем все возвраты скрыты в механизме, регулирующем рекурсию.

Для иллюстрации того, как описанный метод применяется при решении конкретных задач, рассмотрим задачу нахождения таких расстановок восьми ферзей на шахматной доске, в которых ни один ферзь не атакует другого. Решение расстановки ферзей можно искать в виде вектора (а1, а2, а3, а4, а5, а6, а7,

а8), где аi– номер вертикали, на которой стоит ферзь, находящийся в i-й горизонтали, т.е. А1=А2 =А3=А4 =А5 =А6 =А7 =А8 ={1,2,3,4,5,6,7,8} . Каждое частичное решение – это расстановка N ферзей (где 1£N£8) в первых N горизонталях таким образом, чтобы эти ферзи не атаковали друг друга. Заметим, что общая процедура поиска с возвращением при применении ее к задаче о расстановке ферзей уточняется таким образом, что в ней не вычисляются и не хранятся явно множества Sk .

Процесс поиска с возвращением удобно описывать в терминах обхода в глубину (см. ниже) дерева поиска решения, которое строится следующим образом. Корень дерева поиска решения (нулевой уровень) соответствует пустому вектору, являющемуся начальным частичным решением. Для любого k³1 вершины k-го уровня, являющиеся сыновьями некоторой вершины p, соответствуют частичным решениям
(а1, а2,… , аk-1, аk), где (а1, а2,… , аk-1) – это то частичное решение, которое соответствует вершине p, а аk Î Sk; при этом упорядоченность сыновей вершины p отражает упорядоченность соответствующих элементов аk в Sk .


Дата добавления: 2014-12-18; просмотров: 21 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2021 год. (0.014 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав