Решение Ханойской башни с использованием хорошего пространства состояний, а затем дерева поиска

Question

Я хочу решить проблему «Ханойских башен», используя хорошее «пространство состояний».Использование подходящего пространства состояний - это способ, который предлагается некоторыми методами ИИ.Имея хорошее пространство состояний, я бы хотел иметь возможность построить дерево поиска, а затем использовать некоторую стратегию, например «DFS» (поиск в глубину), чтобы найти решение.просто не знаю, как разработать хорошее пространство состояний, а затем использовать его для построения дерева поиска.Кто-нибудь может описать, как создать пространство состояний для проблемы Ханойской башни?Тогда скажите мне, как построить дерево поиска для этого?

Answer 1

Я предлагаю следующее пространство состояний:

Предполагая, что у вас есть n кирпичей и 3 башни, обозначенные 0,1,2.Обозначим текущее состояние через тройные числа, например (в случае n = 9):

987654321
001102020 (current state)

, означая, что кирпичи 9,8,5,3 и 1 находятся в 0-й башне.Кирпичи 7 и 6 в 1-й башне и кирпичи 4 и 2 во 2-й башне.

Это даст вам пространство состояний размером 3 ^ n, которое не слишком велико.

(Это только частичный ответ. Но каждая строка состояния будет соответствовать законному состоянию. То есть,

1. в каждой башне размер кирпичей будет уменьшатьсяснизу вверх

2. в двух разных башнях кирпич не появится.

Поэтому я считаю, что предложенное пространство состояний минимально.)

Answer 2

Я думаю, что Вы можете легко решить эту проблему, используя подход «Разделяй и властвуй»: Предположим, что U должен решить проблему перемещения n дисков из src в dest с помощью некоторого вспомогательного колышка. Вы можете рекурсивно определить функцию:

towers(n,src,dest,peg)
{
    if(n==1) //BASE CASE
        move a disc from src to dest. 

   else  //INDUCTIVE CASE
   {
    towers(n-1,src,aux,dest);
    towers(1,src,dest,aux);
    towers(n-1,aux,dest,src)
   }
}

Анализ сложности: Т (п) = 2T (п-1) + 1

Это приводит к решению T (n) = O (2 ^ n) [экспоненциальный порядок].

Может быть, вы также можете использовать какое-то напоминание для хранения решения уже решенных подзадач, чтобы еще больше повысить сложность времени, но это компромисс для увеличения использования сложности пространства.

Answer 3

2 ^ (n + 1) -1 не подходит для проблемы Ханоя.Если вы посмотрите на рисунок 2 здесь , то при применении n = 3 к 2 ^ (n + 1) -1 выдает 2 ^ 4 - 1 или 15 состояний.Но цифра 2 показывает 27 состояний.

Answer 4

Я думаю оптимальное решение (2 ^ n - 1)

пространство состояний задается как 3 ^ n

Вот еще одна ссылка с древовидной диаграммой, которую вы можете использовать для подсчета состояния (я думаю, это относится к вашему вопросу о пространстве состояний)