Имеется некая игра. Необходимо оптимально быстро найти кратчайшую последовательность ходов для достижения перехода из одного игрового состояния в другое. (или всевозможные последовательности определённой длины). При чём нужна будет функция возможности ограничения возможных ходов. Например, если возможных ходов 4 (влево, вправо, вверх, вниз), то мы моглы бы запросить путь, который, допустим, не использует ходы влево и вниз. Как всё это дело лучше хранить и какие алгоритмы использовать для поиска?
[Размышления] Представляю себе принцип примерно следующим образом... При каждом ходе строится граф, где ребро это ход, а узел это состояние игры после данного хода (т.е. можно будет как анализировать существующую игру, так и сгенерировать до определённой глубины всевозможные 'виртуальные' комбинации для поиска по ним). Направление хода это вес, видимо. Но я не припомню ни одного стандартного алгоритма, который исключал бы из поиска определённые веса... Т.е. нужно пробежаться по графу и проставить исключаемым ходам неприлично высокий вес? (что тоже не исключает его участие на 100%) Или лучше подправить алгоритм, чтобы он по списку игнорировал определённые веса, а сам граф воспринимал, как невзвешенный?
На входе алгоритма - некие состояния игры, т.е. для каждого узла нужно хранить какой-то хеш (т.к. хранить все состояния довольно накладно), чтобы входные данные сразу можно было ассоциировать с нужными узлами графа. А потом поиском кратчайшего пути (A* наверное будет в данном случае оптимально?) можно будет найти кратчайший, а поиском вглубину(?) с ограничением по глубине для определённой длины.
Это все решается через А*, как ни странно. А* предназначен для нахождения маршрутов по графу между вершинами.
Берете стартовое состояние игры (входная вершина) и проходите все возможные переходы (ребра графа), проходите по ним, получаете новые состояния (вершины). Проверяете не совпадают ли вершины с ранее известными, и объединяете их. К каждой вершине записываете минимальную "цену" её достижения из стартовой вершины. Повторяете рекурсивно, каждый раз выбирая вершину с наименьшей "ценой", до тех пор пока одна из вершин не будет целевым состоянием игры. В процессе построения графа, следите за своими правилами и проверяете из какого состояния (вершины) они дают перейти в другое или нет. Т.е. другими словами, ребра переходов могут быть однонаправленными.
Направление хода это вес, видимо.
Нет. Направление - это существование односторонней связи (ребра). Ребра могут быть односторонними, это нормально.
На входе алгоритма - некие состояния игры, т.е. для каждого узла нужно хранить какой-то хеш
Можно хэш, это ускорит поиск одинаковых состояний в большом графе.
Как меняется крипторынок и к чему готовиться владельцам криптообменников
Собственно код который был на WinForm, нужно сделать что-то подобное на WPF
В ASPNET-приложении необходимо реализовать разворот картинок на 90 градусов
Имеется приложение с 2-мя Юзер контролами1 - со списком пользователей, 2 - с историей сообщений