двумя кубиками (2), и над кубиком № 2 – один кубик (1), а над кубиком 3 – ни одного (0):
Номер кубика |
На своём месте? |
1 |
Нет |
2 |
Нет |
3 |
Нет |
∑ |
3 |
|
|
Место кубика |
Занято? |
1 |
Нет |
2 |
Да |
3 |
Да |
∑ |
2 |
|
|
Номер кубика |
Сколько кубиков сверху? |
1 |
0 |
2 |
1 |
3 |
0 |
∑ |
1 |
Тогда эвристическая функция для второй вершины |
ˆ |
= |
h(2) |
= 3 + 2 + 1 = 6, а оценочная функция |
|
|
|
ˆ |
ˆ |
= 1 + 6 = 7. |
|
|
f (2) |
= gˆ (2) + h(2) |
|
|
Получим оценочную функцию для третьего варианта первого шага:
Это мы получим вершину № 3. Определим эвристическую функцию для этой вершины. Не на своём месте расположены куби-
ки 2, 3, 1 (3). Место, которое должен занять кубик № 3, занято кубиком № 2 (1), над кубиком № 2 – нет кубиков (0), а над кубиком № 3 – ни одного (0), над кубиком № 1 – нет кубиков (0):
|
Номер кубика |
На своём месте? |
|
|
|
|
1 |
Нет |
|
|
|
|
2 |
Нет |
|
|
|
|
3 |
Нет |
|
|
|
|
∑ |
3 |
|
|
|
|
|
|
|
|
|
|
Место кубика |
Занято? |
|
|
|
1 |
Нет |
|
|
|
|
2 |
Нет |
|
|
|
|
3 |
Да |
|
|
|
|
∑ |
1 |
|
|
|
|
|
|
|
|
|
|
Номер кубика |
Сколько кубиков сверху? |
|
|
|
1 |
0 |
|
|
|
|
2 |
0 |
|
|
|
|
3 |
0 |
|
|
|
|
∑ |
0 |
|
|
|
Тогда эвристическая |
функция для этой вершины |
ˆ |
= |
h(3) |
= 3 + 1 + 0 = 4, а оценочная функция
ˆ |
= gˆ |
ˆ |
= 1 + 4 = 5. |
f (3) |
(3) + h(3) |
Получим оценочную функцию для четвёртого, последнего варианта первого шага:
Это мы получим вершину № 4. Определим эвристическую функцию для этой вершины. Не на своём месте расположены кубики 2, 3, 1 (3). Место, которое должен занять кубик № 3, занято кубиком № 2 (1), над кубиком № 2 – нет кубиков (0), а над кубиком № 3 – ни одного (0), над кубиком № 1 – один кубик (1):
|
|
Номер кубика |
На своём месте? |
|
|
|
|
|
1 |
Нет |
|
|
|
|
|
2 |
Нет |
|
|
|
|
|
3 |
Нет |
|
|
|
|
|
∑ |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Место кубика |
Занято? |
|
|
|
1 |
Нет |
|
|
|
|
2 |
Нет |
|
|
|
|
3 |
Да |
|
|
|
|
|
∑ |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Номер кубика |
Сколько кубиков сверху? |
|
|
|
|
|
1 |
1 |
|
|
|
|
|
2 |
0 |
|
|
|
|
|
3 |
0 |
|
|
|
|
|
|
∑ |
1 |
|
|
|
|
Тогда эвристическая |
функция для этой вершины |
ˆ |
= |
h(4) |
= 3 + 1 + 1 = 5, а оценочная функция
ˆ |
= gˆ |
ˆ |
= 1 + 5 = 6. |
f (4) |
(4) + h(4) |
Ищем вершину с минимальной оценочной функцией. Это
f (3) = 5,
поэтому на втором шаге раскрываем эту вершину (рис. 8.1):
Рис. 8.1. Первоеветвление
Исходное положение для второго шага:
Первый вариант второго шага:
Это мы получим вершину № 5. Определим эвристическую функцию для этой вершины. Не на своём месте расположены кубики 2, 3, 1 (3). Места, которые должны занять кубики, не заняты (0), над кубиком № 3 – кубик № 2 (1), а над кубиком № 2 – ни одного (0), над кубиком № 1 – ни одного (0):
Номер кубика |
На своём месте? |
1 |
Нет |
2 |
Нет |
3 |
Нет |
∑ |
3 |
224
Место кубика |
Занято? |
1 |
Нет |
2 |
Нет |
3 |
Нет |
∑ |
0 |
|
|
Номер кубика |
Сколько кубиков сверху? |
1 |
0 |
2 |
0 |
3 |
1 |
∑ |
1 |
Тогда эвристическая функция для вершины |
ˆ |
= 3 + 0 +1= 4, |
h(5) |
а оценочная функция (это второй шаг!) |
|
|
|
|
ˆ |
ˆ |
+ 4 |
= 6. |
|
|
f (5) |
= gˆ (5) + h(5) = 2 |
|
|
Второй вариант второго шага:
Это мы получим вершину № 6. Определим эвристическую функцию для этой вершины. Не на своём месте расположены кубики 2, 3, 1 (3). Места, которые должны занять кубики, не заняты (0), над кубиком № 3 – нет (0), над кубиком № 2 – ни одного (0), над кубиком № 1 – один (1):
Номер кубика |
На своём месте? |
1 |
Нет |
2 |
Нет |
3 |
Нет |
∑ |
3 |
|
|
Место кубика |
Занято? |
1 |
Нет |
2 |
Нет |
3 |
Нет |
∑ |
0 |
|
Номер кубика |
|
Сколько кубиков сверху? |
|
|
|
1 |
|
|
|
1 |
|
|
|
|
|
2 |
|
|
|
0 |
|
|
|
|
|
3 |
|
|
|
0 |
|
|
|
|
|
∑ |
|
|
|
1 |
|
|
|
|
Тогда эвристическая функция для вершины |
ˆ |
= 3 + 0 +1 = 4, |
h(6) |
а оценочная функция (это второй шаг!) |
|
|
|
|
|
|
ˆ |
= gˆ |
|
ˆ |
+ 4 |
= 6. |
|
|
|
|
f (6) |
(6) + h(6) = 2 |
|
|
|
Третий вариант второго шага:
Это мы получим вершину № 7. Определим эвристическую функцию для этой вершины. Не на своём месте расположены кубики 2, 3, 1 (3). Места, которые должны занять кубики 2, 3, заняты (2), над кубиком № 3 – нет (0), над кубиком № 2 – один (1), над кубиком № 1 – нет (0):
Номер кубика |
На своём месте? |
1 |
Нет |
2 |
Нет |
3 |
Нет |
∑ |
3 |
|
|
Место кубика |
Занято? |
1 |
Нет |
2 |
Да |
3 |
Да |
∑ |
2 |
|
|
Номер кубика |
Сколько кубиков сверху? |
1 |
1 |
2 |
0 |
3 |
0 |
∑ |
1 |
226
Тогда эвристическая |
функция для |
этой вершины |
ˆ |
= |
h(7) |
= 3 + 2 + 1 = 6, а оценочная функция (это второй шаг!) |
|
|
ˆ |
ˆ |
= 8. |
|
|
f (7) = gˆ |
(7) + h(7) = 2 + 6 |
|
|
Четвёртый вариант второго шага:
Это мы получим вершину № 8. Определим эвристическую функцию для этой вершины. Не на своём месте расположены кубики 2, 3, 1 (3), Место, которое должен занять кубик № 3, занято кубиком 2 (1), над кубиком № 3 – кубик 1 (1), над кубиком № 2 – нет (0), над кубиком № 1 – нет (0):
|
Номер кубика |
На своём месте? |
|
|
|
|
1 |
Нет |
|
|
|
|
2 |
Нет |
|
|
|
|
3 |
Нет |
|
|
|
|
∑ |
3 |
|
|
|
|
|
|
|
|
|
|
Место кубика |
Занято? |
|
|
|
1 |
Нет |
|
|
|
|
2 |
Нет |
|
|
|
|
3 |
Да |
|
|
|
|
∑ |
1 |
|
|
|
|
|
|
|
|
|
|
Номер кубика |
Сколько кубиков сверху? |
|
|
|
1 |
0 |
|
|
|
|
2 |
0 |
|
|
|
|
3 |
1 |
|
|
|
|
∑ |
1 |
|
|
|
Тогда эвристическая |
функция для этой вершины |
ˆ |
= |
h(8) |
= 3 + 1 + 1 = 5, а оценочная функция (это второй шаг!)
ˆ |
= gˆ |
ˆ |
= 2 + 5 = 7. |
f (8) |
(8) + h(8) |
Пятый вариант второго шага:
Он уже был – это вершина 4:
ˆ |
= gˆ (4) |
ˆ |
= 1 + 5 = 6. |
f (4) |
+ h(4) |
У этой вершины |
ˆ |
|
|
|
|
h(4) = 5, поэтому предпочтение отдаётся |
ˆ |
|
|
|
ˆ |
|
|
вершинам 5, 6 – у них h(5) = 4, |
h(6) = 4. |
Шестой вариант второго шага: |
|
|
|
|
|
|
|
|
|
|
|
|
– |
|
– |
|
– |
|
|
|
3 |
|
– |
|
– |
|
|
|
2 |
|
– |
|
1 |
|
Это исходное состояние – |
его не рассматриваем. |
Больше вариантов нет. Итак, имеем две вершины 5, 6 с одинаковым значением оценочной функции.
Раскрываем вершину № 5. Исходное положение для третьего шага раскрытие вершин № 5:
–3 1
Первыйвариант третьегошага, если раскрываем вершину №5:
–3 –
Это мы получили вершину № 9. Определим эвристическую функцию для этой вершины. Не на своём месте расположены кубики 2, 3, 1 (3). Места, которые должны занять кубики, не заняты (0),
над кубиком № 3 – два кубика (2), над кубиком № 2 – |
один (1), над |
кубиком № 1 – нет (0): |
|
|
|
|
|
|
|
|
|
|
|
|
|
Номер кубика |
|
На своём месте? |
|
|
|
|
1 |
|
Нет |
|
|
|
|
2 |
|
Нет |
|
|
|
|
3 |
|
Нет |
|
|
|
|
∑ |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
Место кубика |
|
Занято? |
|
|
|
|
1 |
|
Нет |
|
|
|
|
2 |
|
Нет |
|
|
|
|
3 |
|
Нет |
|
|
|
|
∑ |
|
0 |
|
|
|
|
|
|
|
|
|
|
Номер кубика |
|
Сколько кубиков сверху? |
|
|
1 |
|
0 |
|
|
|
|
2 |
|
1 |
|
|
|
|
3 |
|
2 |
|
|
|
|
∑ |
|
3 |
|
|
|
Тогда эвристическая функция для вершины |
ˆ |
= 3 + 0 + 3 = 6, |
h(9) |
а оценочная функция (это уже третий шаг!) |
|
|
|
|
ˆ |
|
ˆ |
|
|
|
|
f (9) = gˆ |
(9) + h(9) = 3 + 6 = 9. |
|
|
|
Второйварианттретьего шага, еслираскрываем вершину №5:
Это мы получим вершину № 9'. Определим эвристическую функцию для этой вершины. Не на своём месте расположены кубики 2, 3, 1 (3). Место, которое должен занять кубик № 3, занято кубиком 1 (1), над кубиком № 3 – кубик № 2 (1), над кубиком № 2 – нет (0), над кубиком № 1 – нет (0):
|
Номер кубика |
На своём месте? |
|
|
|
|
1 |
Нет |
|
|
|
|
2 |
Нет |
|
|
|
|
3 |
Нет |
|
|
|
|
∑ |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Место кубика |
Занято? |
|
|
|
|
|
|
1 |
Нет |
|
|
|
|
2 |
Нет |
|
|
|
|
|
3 |
Да |
|
|
|
|
|
∑ |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
Номер кубика |
Сколько кубиков сверху? |
|
|
|
|
|
|
1 |
0 |
|
|
|
|
|
|
2 |
0 |
|
|
|
|
|
|
3 |
1 |
|
|
|
|
|
|
∑ |
1 |
|
|
|
|
|
Тогда эвристическая |
функция для этой вершины |
ˆ |
= |
h(9') |
= 3 + 1 + 1 = 5, а оценочная функция (это уже третий шаг!)
ˆ |
= gˆ |
ˆ |
f (9') |
(9')+ h (9')= 3+ 5= 8 |
Третийварианттретьего шага, еслираскрываем вершину №5:
Это уже было – вершина № 6, да третий шаг (оценка 6) – получаем оценочную функцию 7.
Четвёртый вариант третьего шага, если раскрываем вершину № 5:
Тоже было – вершина № 3 (первый шаг, оценка 5), да третий шаг – получаем оценочную функцию 7.
