Исчерпывающего поиска




НазваниеИсчерпывающего поиска
Дата конвертации28.02.2013
Размер444 b.
ТипРешение



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

  • Во многих задачах из различных областей знания ставятся вопросы-задания типа: “Сколько существует способов …”, “Подсчитайте количество элементов …”, “Перечислите все возможные варианты …”, “Есть ли способ …”, “Существует ли объект…” и т. п. Ответы на них, как правило, требуют исчерпывающего поиска в некотором множестве M всех возможных вариантов, среди которых находятся решения конкретной задачи. Один из общих методов организации исчерпывающего поиска: перебор с возвратом (backtracking).



Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отметать как можно раньше и как можно больше заведомо неподходящих вариантов M. Перебор с возвратом также можно рассмотреть как задачу об обходе дерева решений.

  • Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются. Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отметать как можно раньше и как можно больше заведомо неподходящих вариантов M. Перебор с возвратом также можно рассмотреть как задачу об обходе дерева решений.



Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева (вершины изображены на рисунке кружочками). Он умеет выполнять команды:

  • Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева (вершины изображены на рисунке кружочками). Он умеет выполнять команды:

  • вверх_налево (идти по самой левой из выходящих вверх стрелок)

  • вправо (перейти в соседнюю справа вершину)

  • вниз (спуститься вниз на один уровень)

  • и проверки, соответствующие возможности выполнить каждую из команд, называемые

  • "есть_сверху"

  • "есть_справа"

  • "есть_снизу"



У Робота есть команда "обработать" и его задача - обработать все листья (вершины, из которых нет стрелок вверх, то есть где условие "есть_сверху" ложно).

  • У Робота есть команда "обработать" и его задача - обработать все листья (вершины, из которых нет стрелок вверх, то есть где условие "есть_сверху" ложно).

  • Нам понадобится такая процедура: void вверх_до_упора_и_обработать

  • | //{дано: (ОЛ), надо: (ОЛН)}

  • {

  • | //{инвариант: ОЛ}

  • | while( есть_сверху ){

  • | | вверх_налево ();

  • | }

  • | //{ОЛ, Робот в листе}

  • | обработать();

  • | //{ОЛН}

  • }

  • Основной алгоритм:

  • //дано: Робот в корне, листья не обработаны

  • //надо: Робот в корне, листья обработаны

  • //{ОЛ}

  • вверх_до_упора_и_обработать ();

  • //{инвариант: ОЛН}

  • While(есть_снизу){

  • | if(есть_справа){

  • | |//{ОЛН, есть справа}

  • | | вправо();

  • | | //{ОЛ}

  • | | вверх_до_упора_и_обработать();

  • | }else{

  • | | //{ОЛН, не есть_справа, есть_снизу}

  • | | вниз();

  • | }

  • }

  • //{ОЛН, Робот в корне => все листья обработаны}



Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу - утверждения о результате ее выполнения):

  • Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу - утверждения о результате ее выполнения):

  • (1) {ОЛ, не есть_сверху}

  • обработать

  • {ОЛН}

  • (2) {ОЛ}

  • вверх_налево

  • {ОЛ}

  • (3) {есть_справа, ОЛН}

  • вправо

  • {ОЛ}

  • (4) {не есть_справа, ОЛН}

  • вниз

  • {ОЛН}









Похожие:

Исчерпывающего поиска icon«Требованиям к обеспеченности обучающихся высших учебных заведений Российской Федерации доступом к электронным научным и образовательным ресурсам» от 22 апреля 2011 год
Режим расширенного поиска предназначен для более тонкого, прицельного поиска учебников, глав, словарных статей, поиска по текстам,...
Исчерпывающего поиска iconЧто из себя представляет 23. 000 научных журналов
Точное и полное воспроизведение поиска, улучшенная система просмотра результатов поиска
Исчерпывающего поиска iconВ последнем отчете oclc : "College Student Perceptions"
...
Исчерпывающего поиска iconПонятие поиска; Понятие поиска
...
Исчерпывающего поиска iconТеория баз данных и информационного поиска Информационно-графовая модель данных
Шаг Определяется понятие задачи информационного поиска и функции ответа, реализуемой этой задачей
Исчерпывающего поиска iconЛекция Корпус как особый тип информационно-поисковой системы В. П. Захаров Санкт-Петербургский государственный университет Основные понятия информационного поиска
Ипс) это упорядоченная совокупность документов (массивов документов) и информационных технологий, предназначенных для хранения и...
Исчерпывающего поиска iconПоиск данных. Постановка, организация, последовательность поиска Классификация средств поиска Интернет
Всемирной паутины в базах данных. Специальные программы-роботы периодически «обходят» Web-серверы Интернета, читают все встречающиеся...
Исчерпывающего поиска iconДесять основных проблем Десять основных проблем
Отсутствие исчерпывающего перечня документов для регистрации Федеральным законом от 12. 01. 1996 n 7-фз «О некоммерческих организациях»...
Исчерпывающего поиска iconЗадача обобщенной сегментации цветных изображений и поиска ориентиров Задача обобщенной сегментации цветных изображений и поиска ориентиров
Выделить на цветном изображении однородные части реальных объектов и построить их сжатое описание, содержащие описание формы и полутоновое...
Исчерпывающего поиска iconМетод поиска должен учитывать терминологический состав учебных материалов; метод поиска должен учитывать терминологический состав учебных материалов
Любая деятельность может рассматриваться как технологический процесс и потому может быть улучшена
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница