TIPS_1_laba / Игра Перестановка

б) В пространстве состояний существуют не пересекаемые подмножества.

Родовые признаки (одинаковое количество символов, цифры в последовательности не повторяются) выделяют пространство состояний, следовательно, родовые признаки не пересекаемых подмножеств не равны пустому множеству, т.е. К^R≠Ø

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

Но при реализации игры «перестановка» следует учитывать условия:

1) Если количество знаков в состоянии 2m и применяется прямое правило, то мощность пространства поиска будет равным n!/2.

2) Если количество знаков в состоянии 2m-1 и применяется прямое правило, то мощность пространства поиска будет равным n!.

3) Если количество знаков в состоянии 2m и применяется обратное правило, то мощность пространства поиска будет равным n!.

4) Если количество знаков в состоянии 2m-1 и применяется обратное правило, то мощность пространства поиска будет равным n!/2.

Эти условия необходимы для того, чтобы определить существуют ли в пространстве состояний не пересекаемые подмножества состояний. Пример: если следовать условиям 2 и 3, то таких состояний не появится т.к из родительской вершины, состоящей из n символов можно образовать n! возможных комбинаций, а если следовать условям 1 и 4, то можно образовать только половину возможных состояний и в пространстве состояний окажутся непересекаемые вершны. Можно сделать вывод, что обязательним условием существованя искомой вершины является проверка количества символов в состоянии на четность/нечетность.

в) Отношения между состояниями пространства.

Пространство поиска в составе пространства состояний образуется за счет обобщения видовых признаков некоторых состояний. В этом случае обобщенные видовые признаки дополняют множество родовых признаков данных состояний, образуя собственное пространство поиска в пространстве состояний или класс состояний.

Каждое состояние пространства состояний получено прямым или обратным преобразованием.

Глубина пространства поиска меньше либо равна n-1, где n-число цифр в состоянии.

Элементы пространства поиска различны.