Реферат Курсовая Конспект
Алгоритм поиска с возвращением, их реализация с помощью рекурсий и динамических структур. - раздел Компьютеры, Алгоритм поиска с возвращением Рассмотрим Общий Случай, Когда Решение Задачи Имеет Вид Вектора (А...
|
Рассмотрим общий случай, когда решение задачи имеет вид вектора (а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 thenk := k + 1; Вычислить Sk
(* Например, в качестве Skможно взять Аk *)
end
end;
(* Возврат *) k := k - 1
end;
(* Все решения найдены *)
Более коротко общую процедуру поиска с возвращением можно записать в рекурсивной форме:
– Конец работы –
Эта тема принадлежит разделу:
Алгоритм поиска с возвращением... Обходы ордерева в глубину и в ширину... Обходы графа в глубину и в ширину...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм поиска с возвращением, их реализация с помощью рекурсий и динамических структур.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов