ТИПИС

Приложение Б. Игра «Перестановка»	101

Приложение Б

ИГРА «ПЕРЕСТАНОВКА»

Суть игры «Перестановка» – получение из некоторой заданной последовательности знаков (состояние so So) целевую последовательность этих же знаков (состояние st St).

В качестве знаков в игре перестановка используются нетождественные цифры. Мощность пространства состояний S = n!, где n – количество цифр в состоянии. На рис. Б.1 показана схема задачи «Перестановка».

	S	o		S	t
s			s

123456 645321

Рис. Б.1. Задача для игры «Перестановка»

102		Приложения

Для инициализации поиска начальное состояние игры должно отличаться от целевого состояния расположением цифр. Следует отметить, что вместо цифр в игре могут быть использованы иные нетождественные знаки.

Целями игры «Перестановка» являются:

1)поиск, получение из некоторого заданного состояния so So целевое состояние st St;

2)определение кратчайшего расстояния Hi или MS от so до st;

3)выделение оптимального пути Li от so до st.

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

Схема преобразования состояний в игре «Перестановка» показана на рис. Б.2. Стрелки представляют собой правила преобразования состояний.

123456

134562 214563 312564 412365 512346

Рис. Б.2. Схема преобразования состояний для игры «Перестановка»

Преобразование состояний выполняется следующим образом:

1)в состоянии выделяются пары чисел (i, i + 1). Например, для состояния 123456 парами являются (1, 2), (2, 3), … (5, 6) (их количество равняется n – 1);

2)первое число пары i переносится в начало состояния, а второе –

i+ 1 – в конец состояния (рис. Б.2). Такое преобразование будем называть прямым преобразованием. При обратном преобразовании первое число пары i переносится в конец состояния, а второе – i + 1 – в начало состояния.

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

ПриложениеБ. Игра «Перестановка»	103

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

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

1)если количество знаков в состоянии 2m (где m – любое целое число) и применяется прямое правило, то мощность пространства поиска будет равным n!/2;

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

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

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

Из условий следует, что пространство состояний в игре «Перестановка» включает непересекаемые подпространства (условие 1 и 4). Поэтому при задании начального и целевого состояния следует учитывать это обстоятельство.

Определить до начала поиска принадлежность начального и целевого состояния одному пространству поиска в игре «Перестановка» в условиях 1 или 4 можно, если использовать следующие правило: «Если начальное состояние отличается от целевого расположением знаков в первой или

последней паре вида 1 2 3 4 5 6 2 1 3 6 5 4 или 1 3 2 4 5 6 3 2 1 4 6 5, то эти состояния находятся в разных пространствах поиска».

Следовательно, как и в условии 1, поиск состояния (2134) из состояния (1234) или состояния (2143), так и при нечетной последовательности цифр в условии 4 поиск состояния (123) из состояния (213) или состояния (132) будет изначально обречен на глобальную неудачу.

104		Оглавление

ОГЛАВЛЕНИЕ

Введение...............................................................................................................	3
Глава 1. ПОИСК, ЗАДАЧИ ПОИСКА
И ПРОСТРАНСТВО СОСТОЯНИЙ.................................................................	5
1.1. Понятие поиск....................................................................................	6
1.2. Задачи поиска и преследования цели ...........................................	15
1.3. Пространство состояний.................................................................	23
Глава 2. МЕТОДЫ ПОИСКА...........................................................................	31
2.1. Классификация методов поиска....................................................	32
2.2. Процедура генерации ......................................................................	37
2.3. Процедура проверки........................................................................	50
2.4. Процедура планирования................................................................	61
2.5. Организация n-направленного поиска..........................................	77
САМОСТОЯТЕЛЬНЫЕ РАБОТЫ..................................................................	83
Библиографический список .............................................................................	94
ПРИЛОЖЕНИЯ ................................................................................................	97
Приложение А. ИГРА «В ВОСЕМЬ» ...................................................	98
Приложение Б. ИГРА «ПЕРЕСТАНОВКА» ......................................	101