Основные стратегии решения задач. Предварительные понятия и примеры.

2. Основные стратегии решения задач. Предварительные понятия и примеры

Основные стратегии решения задач

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

Предварительные понятия и примеры

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

Эту задачу можно представлять себе как задачу выбора среди множества возможных альтернатив. В исходной ситуации альтернатива всего одна: поставить кубик С на стол. После того как кубик С поставлен на стол, мы имеем три альтернативы:

* поставить А на стол или

* поставить А на С, или

* поставить С на А. (Рис.)

Ясно, что альтернативу поставить С на стол не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию.

Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий:

(1) Проблемные ситуации.

(2) Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.