Глава 2. ПРЕДСТАВЛЕНИЕ ЗАДАЧ В ПРОСТРАНСТВЕ СОСТОЯНИЙ

2.1. ОПИСАНИЯ СОСТОЯНИЙ

В предыдущей главе мы ввели понятия состояний и операторов. Здесь мы займемся детальной разработкой этих идей и дадим несколько примеров формулировки задач в терминах пространства состояний.

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

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

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

Й широко используемом описании употребляются двоичные деревья. Неконцевые вершины в таком дереве описания представляют арифметические знаки . а концевые вершины представляют переменные или постоянные символы появляющиеся в этом выражении. Таким образом

деревом представления для выражения должно быть

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

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