Реферат: Механизм бектрекинга

end.

Заключение

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

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

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

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

Литература

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

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

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

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

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

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

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

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

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