Мобильная версияДавайте начнем с сетки 4 на 4; В конечном итоге я хочу расшириться до размера 8 на 8 или настолько большого, насколько смогу, если 8 на 8 слишком велико, но не больше. Я пометил ячейки, чтобы о них было легче говорить, и нам нужно с чего-то начинать, поэтому я добавил нашу стартовую позицию в 0-й ячейке красным цветом. Сейчас я концентрируюсь только на 0-й ячейке, но вы должны начать со списка всех отдельных ячеек. Я назову эту итерацию 1.
[img]https://i .sstatic.net/V0Ke7RTt.png[/img]
Далее я получу все возможные позиции, которые можно посетить отсюда. Я отметил зеленым цветом ячейки, которые может посещать начальная позиция. Правило заключается в том, что вы можете двигаться только вверх, вниз, влево или вправо, но вы можете перемещаться на переменное расстояние. Например, вы можете переместить одну плитку вправо или 3 плитки вправо. Возвращаясь к этому примеру, мы могли бы перейти к 1, 2, 3, 4, 8 и 12. (Я бы повторил это для всех 16 возможных стартовых позиций). В качестве набора пар они будут (0, 1), (0, 2), ... , (0, 12). Это вторая итерация.
[img]https://i. sstatic.net/XKaqVucg.png[/img]
Затем для каждой пары найдите все возможные тройки. В примере я использую (0, 8). Таким образом, это будут (0, 1, 8), (0, 2, 8), (0, 3, 8), (0, 4, 8), (0, 8, 9), (0, 8, 10). ), (0, 8, 11), (0, 8, 12)
И я буду повторять эти итерации до тех пор, пока не останется пустого места.
Я уже написал программу, которая может это сделать. Это довольно тривиально, но медленно и использует много памяти. Я надеюсь, что кто-нибудь сможет дать мне некоторое представление об этой проблеме.
Код
Я сохраняю позиции в виде битбордов. Он использует поиск в ширину, чтобы получить все позиции. Я делаю несколько оптимизаций, некоторые из которых не уверен, что работают, а некоторые, я думаю, могут сократить слишком много и слишком рано, что приведет к тому, что не все комбинации будут найдены.
Код: Выделить всё
internal class ValidPositionGenerator
{
// Used to store new bitboards we need to check
private readonly Queue bitBoards = new Queue();
// Used to store unique bitboards we have found
private readonly HashSet visited = [];
public ValidPositionGenerator(int maxTiles)
{
int i = 0;
// This corresponds to the first iteration
while (i < 64)
{
bitBoards.Enqueue(CanonicalizeBitboard((ulong)Math.Pow(2, i)));
i++;
}
GenerateValid(bitBoards, maxTiles);
}
private void GenerateValid(Queue bitBoards, int maxTiles)
{
int i = 0;
while (bitBoards.Count != 0)
{
ulong board = bitBoards.Dequeue();
if (visited.Contains(board))
{
continue;
}
if (BitOperations.PopCount(board) > maxTiles)
{
continue;
}
visited.Add(board);
GetNewPositions(board, bitBoards, visited);
i++;
}
}
private static void GetNewPositions(ulong board, Queue bitBoards, HashSet visited)
{
// Get the active bits from board
List indices = GetIndices(board);
int i;
ulong canonical;
// Loop over each one and attempt to add each one to the output
foreach (int index in indices)
{
(int, int) pair = GetXYPairFromIndex(index);
// Up
i = 1;
while (pair.Item2 - i > -1)
{
// Check if the next bit is already set: Optimization 1
if (Util.GetBitboardCell(board, pair.Item1, pair.Item2 - i) == true)
{
break;
}
// Optimization 2, 3, and 4 happens inside CanonicalizeBitboard()
canonical = CanonicalizeBitboard(SetBitboardBit(board, pair.Item1, pair.Item2 - i, true));
if (!visited.Contains(canonical))
{
bitBoards.Enqueue(canonical);
}
i++;
}
// I've removed the rest to keep the code shorter
// Left
// Right
// Down
}
}
}
private static List GetIndices(ulong board)
{
ulong temp = board;
List indices = new List();
int index = 0;
while (board > 0)
{
if ((board & 1) == 1)
{
indices.Add(index);
}
board >>= 1;
index++;
}
return indices;
}
// Convert index to an x, y pair
private static (int, int) GetXYPairFromIndex(int index)
{
return (index % 8, index / 8);
}
}
Если при сканировании новых позиций мы обнаружим уже активную позицию, мы можем остановиться, потому что можем продолжайте оттуда, когда доберемся туда. В приведенном ниже примере я нахожусь на (0, 2) и сканирую биты справа от 0. Когда мы достигаем 2, мы видим, что он уже активен, поэтому мы можем остановиться. Затем мы продолжаем сканирование вниз и влево, прежде чем сканировать биты около 2. Отсюда мы продолжим сканирование вправо, чтобы получить все, что мы пропустили. Я еще не проверял, улучшает ли это что-либо.
Я думаю, что возможной оптимизацией было бы создать еще один битборд со всеми местами, которые мы посетили во время этой проверки, и останавливаться, когда мы находим что-то уже найденное. Потому что как только мы доберемся до 2, он начнет сканировать влево к 0, но уже нашел все в этом направлении. Я думаю, что смогу объединить это с первой оптимизацией. Это похоже на его продолжение.
Оптимизация 2: не сохранять зеркала и повороты
Каждая комбинация имеет симметрию, и мне это не нужно это. Мне нужно сохранить только один из них. Это то, что делает метод canonicalizeBitboard. Он проверяет его на вращение и отражение. Это существенно сокращает пространство поиска. Вместо хранения 16 возможностей в первой итерации нам нужно сохранить только 3: 0, 1 и 5.
Оптимизация 3: не хранить похожие переводы
Рассмотрим две сетки ниже. По сути, они для меня одно и то же. Поэтому, когда я канонизирую битборд, я также смещаю его так, чтобы он оказался заподлицо с верхним левым углом.
[img]https://i.sstatic.net /Qsc8BhLn.png[/img]
Оптимизация 4: Краткое описание
Рассмотрены следующие два битборда. Для моих целей меня интересуют только уникальные комбинации перемещения вверх, вниз, влево или вправо. Если мы начнем с 0, мы сможем двигаться вправо и вниз в обоих из них, так что для меня они одинаковы, и мне нужен только один. Однако я не уверен, что смогу удалить его полностью. Я думаю, мне все равно придется сохранить его, когда я проверю наличие новых растровых изображений, но он мне не нужен для вывода. Меня смущает этот момент и в отношении других моих оптимизаций. Я думаю, что даже если они мне не нужны в выводе, мне все равно следует их проверить, поскольку новая позиция, которую я могу получить от них, может быть уникальной и не найдена в их сокращенной версии.
Вывод
Это все оптимизации, о которых я могу сейчас подумать, но написание этого поста заставило меня задуматься. Все, что я на самом деле делаю, это нахожу все возможные комбинации/перестановки вверх, вниз, влево или вправо, где сумма левого и правого равняется размеру ширины битборда - 1, и аналогично с верхним и нижним, но с возможно, какие-то дополнительные правила. Возможно, есть способ подумать об этом по-другому. Я думаю, что можно было бы подумать об этом как о строке вверх, вниз, влево и вправо, а затем это каким-то образом отображается на каноническом битборде.
Что я сделал пробовал
Я пробовал свой код, и он работает. Мне просто интересно, есть ли лучший способ. Когда я вызываю конструктор ValidPositionGenerator() и использую 6 в качестве входных данных, это занимает около 6 секунд и полгигабайта памяти. На 7 это занимает около 2 минут и использует 16 гигов памяти. Когда я профилирую это, очередь bitBoards взрывается как сумасшедшая, и это вполне может быть неизбежно. Я знаю, что существует 2^64 возможных битборда, но надеюсь, что мои правила и оптимизации сделают это более управляемым.
Подробнее здесь: https://stackoverflow.com/questions/793 ... binatorics
