Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Алгоритмы поиска и сортировки деревьями: перебор с возвратом
2.1.1. Общая схема Даны N упорядоченных множеств U1, U2, ..., UN (N - известно), и требуется построить вектор A=(a1, a2, ..., aN), где a1ÎU1, a2ÎU2, ..., aNÎUN, удовлетворяющий заданному множеству условий и ограничений. В алгоритме перебора вектор А строится покомпонентно слева направо. Предположим, что уже найдены значения первых (k-1) компонент, А=(а1, а2, ..., а(k-1), ?, ..., ?), тогда заданное множество условий ограничивает выбор следующей компоненты аk некоторым множеством SkÌUk. Если Sk<>[ ] (пустое), мы вправе выбрать в качестве аk наименьший элемент Sk и перейти к выбору (k+1) компоненты и так далее. Однако если условия таковы, что Sk оказалось пустым, то мы возвращаемся к выбору (k-1) компоненты, отбрасываем а(k-1) и выбираем в качестве нового а(k-1) тот элемент S(k-1), который непосредственно следует за только что отброшенным. Может оказаться, что для нового а(k-1) условия задачи допускают непустое Sk, и тогда мы пытаемся снова выбрать элемент аk. Если невозможно выбрать а(k-1), мы возвращаемся еще на шаг назад и выбираем новый элемент а(k-2) и так далее. Графическое изображение - дерево поиска. Корень дерева (0 уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора а1, и, в общем случае, узлы k-го уровня являются кандидатами на выбор аk при условии, что а1, а2, ..., а(k-1) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы. procedure Backtrack(вектор,i); begin if <вектор является решением> then <записать его> else begin <вычислить Si>; for aÎSi do Backtrack(векторêêa,i+1); {êê- добавление к вектору компоненты} end; end;
Дата добавления: 2015-07-26; просмотров: 151; Нарушение авторских прав Мы поможем в написании ваших работ! |