Как решить головоломку, используя поиск в ширину?
Я брал уроки по этому вопросу несколько семестров назад, но в то время я мало чему научился. Я смотрел лекцию MIT о поиске ширины. Я многому научился из этого, однако он только научил меня, что BFS — хороший алгоритм для поиска на графике, потрясающий. Мне нужно решить головоломку.
Итак, я написал головоломку на C ++, но теперь мне нужно найти способ, чтобы компьютер мог ее решить. Исходя из того, что я понимаю, мне нужно будет, чтобы компьютер сгенерировал все состояния для этой головоломки в граф, а затем компьютер использовал BFS, чтобы найти решенное состояние? Как я могу рассчитать, сколько вершин и ребер есть в моей головоломке? Головоломка, о которой я говорю, — «Игра в треугольник с бочонком». Любая помощь будет оценена, как решить этот плохой мальчик.
Извините, я не упомянул, как работает головоломка. Таким образом, вы получите треугольник с 14 колышками и 15 местами, выглядит примерно так:
*
2 3
4 5 6
7 8 9 A
B C D E F
где * это пустое пространство. Теперь, подобно шашкам, вы можете только перепрыгнуть колышек через другой колышек в пустое пространство, так что здесь есть только два допустимых хода, 4 к 1 или 6 к 1, средний колышек удален, что приводит к следующему:
1
2 *
4 5 *
7 8 9 A
B C D E F
после прыжка с 6 до 1
Вы продолжаете делать это, пока на доске не останется только один колышек.
Решение
Вот стандартный подход к проблеме поиска в пространстве состояний:
Создайте функцию, которая может генерировать следующие возможные состояния:
Эта функция должна иметь возможность получать некоторую информацию, представляющую доску, и возвращать список ходов, которые потенциально могут быть сделаны (или доски, которые могли бы быть из них получены). Например, вы можете перебирать каждый колышек, вычислять ходы, которые может выполнить данный колышек, и добавлять их в список до тех пор, пока вы не проверите их все.
Используйте BFS для генерации / поиска графа:
Инициализируйте текущий узел в начальное состояние, а затем начните поиск в ширину. Для каждого узла рассчитайте следующие возможные состояния и добавьте их в конец своей очереди поиска. Сохраняйте словарь (потому что он более эффективен, чем список) для каждого состояния, которое вы уже добавили в очередь. Если вы генерируете тот, который находится в словаре, отмените его, а не редактируйте. В конце концов, вы попадете на доску, которая имеет только 1 колышек, после чего ваш поиск будет успешным.
Это стандартный подход к решению головоломки с помощью поиска в ширину. Вам не нужно заранее знать, сколько существует вершин и ребер, потому что ваш код будет генерировать график по мере его поступления. Обратите внимание, что он не будет автоматически генерировать полный график пространства состояний. Чтобы сделать это, вам нужно будет добавлять преимущество каждый раз, когда вы сталкиваетесь с дублированным состоянием доски.
Другие решения
Других решений пока нет …