Строится полное дерево решений для какой-либо игры независимо от размера самого состояния игры, состояние в дереве решений на этапе построения занимает 3 бита, после создания можно сохранить всё дерево по 2 бита на состояние. Этого хватает, чтобы из произвольного игрового состояния найти кратчайшее решение.
Интересный алгоритм, мало памяти требует, работает быстро, есть свои недостатки, но это мелочи.
Самое интересное, что я нашёл реализацию, но нигде не встречал этой идеи, потому было бы интересно узнать что это вообще за алгоритм и почитать про него подробнее.
А дети как хранятся? Так-то только по графу-дереву состояний можно найти кратчайший путь в конечную вершину, вообще ничего не храня в вершинах дополнительно.
EDIsaev, Не всегда же. Ведь если среди двух веток детей в одной путь за 2 шага, а в другой за 4 - то вы никак это не отловите. Возможно есть какая-то специфика игры, позволяющая делать это. Но вряд ли у этого приема есть какое-то название, ибо он слишком специфичен под конкретную игру.
EDIsaev, Ну хорошо, пусть длины в двух детях 10000 и 10002. Только через 10000 шагов отловите?
Ну так вам тогда не надо ничего хранить в вершинах вообще. Если вы и так перебор во всю глубину запускаете, то можно обход в ширину запустить.
И вообще, могут быть игры, где количество ходов будет одинаковой четности всегда. Например у вас лабиринт в котором двигаются 2 фишки и игроку надо свою фишку вывести из лабиринта раньше соперника. Тут в зависимости от шахматной раскраски доски получается что фишка всегда должна сделать количество ходов одной четности. Так что в этом дереве вообще все пути будут одинаковой четности и ваши пометки не дадут вообще никакой информации.
Wataru, Возможно при многих игроках свои ньюансы, у меня игрок всегда один и на каждом этапе ему доступно один из X возможных ходов, потому не задумывался... Но эти тонкости не имеют отношения в вопросу.
EDIsaev, Но вы же все-равно храните в каждой вершине ребра-ходы? Вам же как-то надо определять, куда преведет какой-то ход и, соответственно, где 2-бита для следующего состояния смотреть?
Даже при одном игроке - все то же самое. Вот у вас тупо лабиринт без циклов и надо из него выйти. Если вы пойдете не туда, вы длину кратчайшего пути увеличите на 1 или уменьшите на 1. Ваша оптимизация вообще не помогает.
Поскольку она похоже очень специфична к вашей игре - у нее нет никакого названия.
Wataru, не храню. в процессе поиска делается каждый след возможный ход - выбирается который из них кратчайший - зацыкливается. не туда пойти нельзя, т.к. мы идём от нужного состояния к старту, а значит проход всегда есть, т.к. узел был создан.
EDIsaev, Но тогда вам надо хранить какой-то ассоциативный массив со всеми известными состояниями в ключах. Ведь вот есть у вас текущее состояние (одна переменная), вы сделали какой-то ход - поменяли состояние, и вам надо найти узел для этого состояния.
По памяти это может быть даже сильно больше, чем просто граф с набором ребер. Если состояние больше X чисел.
Wataru, это я обошёл использованием идеального хеша, вычисляемого из текущего состояния и использованого для прямого позиционирования по битовому массиву... и искать ничего не нужно и доступ мгновенный, один минус для каждой задачи хеш-функцию переписывать
А причем тут алгоритм?
Ты имел ввиду типы данных?
Ну так граф. Но сейчас работать с битами - неудобно, ибо память не критична, а работа с битами занимает больше, чем с байтами, ибо усложнена адресация.
EDIsaev, С точки зрения работы CPU, проще адресовать байт, а не бит в байте. Ибо байт это одна команда, а бит в байте - это несколько инструкций. То есть в 2-3-4 раза больше работы.
Десяток миллионов же это всего лишь десяток мегабайт.
Вопрос в том, что это не алгоритм, а тип данных, который представляет собой обычный граф. Но топикстартер хочет хранить его на уровне битов, а не байтов.
Такого типа данных нет, сейчас даже булевые значения хранятся в отдельных байтах.
Поэтому тут не в вопросе не алгоритм.
Это можно создать свой тип данных, с методами добавления/ удаления/ обхода/ графа и реализовать хранение данных с битовой адресацией. Но я лично не вижу особых преимуществ.
Последний раз я данные в битах хранил еще в начале 2000х, с тех пор не возникало желания с этим работать, так как медленно.
Единственное где хранить что-то в битах полезно и быстро - это набор флагов.
Одна битовая операция типа AND позволяет быстро понять включена/выключена конкретная опция или набор опций, храня их всех в одном байте/инте/инт64.
Но там нет адресации, это одна переменная, в которой хранится некоторое количество флагов.
Saboteur, ну стоит отметить, что использование байта для данных в случае структуры с указателем на вектор указателей на элементы, к которым есть пути, займёт в 2 раза больше памяти, чем использование двух старших битов этого указателя для хранения данных, т.е. на amd64 только твоя структура данных займёт уже 160мб вместо 80, без учёта хранения векторов указателей.
Касательно "медленно работает", это неправда, выполнение нескольких инструкций подряд не будет являться узким местом программы, т.к. во-первых есть конвейер, а начиная с пентиума (93 год) ещё и не один, поэтому задержкой на вычисление конкретного бита можно пренебречь, а вот то, что у тебя ухудшится локальность твоей структуры данных это проблема, которая приведёт и к кэш-промахам и к промахам в TLB.
Скорее всего ты имеешь в виду задачу о нахождении наибольшего предка в дереве (lca). Здесь есть много разных алгоритмов. В твоём случае скорее всего используется вариация этого алгоритма https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%...
