Реферат на тему: Бэктрекинг

Введение

Существуют задачи для которых нет хорошего метода решения, ответ на них нельзя получить вычислением по формулам. Это как поиск клада без карты. Надо все честно перекопать. Такие задачи называются задачами полного перебора или комбинаторными задачами. Но перебор перебору рознь. Очевидно, что нет смысла копать скальную породу, могут быть и другие разумные ограничения на действия кладоискателя. То есть все возможные ситуации можно разделить на два класса: могущие содержать решение и не могущие содержать решения. Конечно это грубое разбиение, но для нас этого достаточно.

Это очень простая и понятная идея не искать там, где решения нет, но вот в чём проблема, как определить отсутствие клада не копая

Пример 1.

Дано множество чисел. Составить из них подмножество такое что сумма его элементов будет в точности равна заданному числу А.

Оглавление

- Введение.

- Важное свойство этой задачи.

- Условие задачи.

- Решение полным перебором.

- Бэктрекинг.

- Заключение.

- Литература.

Заключение

Описанный метод выглядит достаточно специфически и кажется, что не так много задач подходят под его возможности. Однако рассмотрим задачу, которая как кажется на первый взгляд довольно далека от описанной выше.

Условие: Дана фигура из картона. Можно ли её разрезать на заданные фигуры (и по форме и по размеру)

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

Тогда задача становится задачей полного перебора. Бектрекинг накладывается на неё очень просто и естественно. Пусть мы провели очередной разрез. Проверим, дал ли он в совокупности с другими разрезами фигуру. Если да, то проверим, входит ли эта вырезанная фигура в множество искомых. Если нет, то данное множество разрезов тупиковое.

Список литературы

- Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.

- Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.

- Гусев В.В. Основы импульсной техники. М. Советское радио.

- Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.

- Машовцев В.А. Вступительные экзамены по информатике // Информатика.

- Орлов В.А. О вступительных экзаменах по информатике // Информатика.

- Яснева Г.Г. Логические основы ЭВМ // Информатика и образование.

- Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование.

- Шауцкова Л.З. Решение логических задач средствами алгебры логики, газета Информатика.