Программа AI Puzzle
У меня загадка с начальным состоянием
R R R G R
R G G R R
R G G R G
R G G R R
R R R B R
куда R = Red, G = Green а также B = Moveable Blank
и цель государства
R R R R R
R G G G R
R G B G R
R G G G R
R R R R R
Я знаю, чтобы переместить пробел, я должен применить алгоритмы поиска, такие как DFS, BFS, A* etc
и я знаю, что должен создать классы:
Узел
class Node {
char board[5][5];
Node *parent;
};
дерево
class Tree {
Node *root;
};
Граница, подобная хэш-таблице, для обнаружения посещенного состояния в сложности O (1).
Так что я просто запутался, как мне начать реализовывать решение этой головоломки. Кто-нибудь может направить меня? Операторы, которые я могу применить на бланке: вверху, внизу, влево, вправо.
Решение
Простейшей идеей было бы инициализировать корневой узел с начальным состоянием. Затем заполните следующий слой; написать процедуру, которая генерирует дочерние узлы в соответствии с правилами перемещения пустого пространства. Вы должны быть осторожны здесь; когда пустое пространство находится на границах доски, некоторые движения будут недействительными. В таком случае эскиз алгоритма A * можно нарисовать так: определите расстояние от исходного состояния как g (n). Это может быть количество разнесенных букв по сравнению с исходным состоянием, учитывая текущее состояние. Определите эвристику h (n), которая дает ваше текущее расстояние от состояния цели, которое может быть числом разнесенных букв по сравнению с состоянием цели. Затем в своем текущем местоположении в дереве попробуйте выбрать следующее состояние, которое минимизирует f (n) = g (n) + h (n). Я не в состоянии глубоко проанализировать это прямо сейчас, но я полагаю, что этот подход может быть намного более эффективным, чем подходы с использованием грубой силы DFS или BFS.
Другие решения
Других решений пока нет …