Как индексировать большое количество перестановок? - PullRequest
Новая
       33

Как индексировать большое количество перестановок?

0 голосов
/ 02 октября 2019

Я пытаюсь закодировать программу, которая находит Алгоритм Бога, который решает конкретную головоломку - кратчайшую последовательность, которая ведет текущее состояние до его решенного состояния.

Для этого мне нужно отобразить всеперестановки / состояния (узлы) с соответствующими расстояниями до решения (глубиной).

Я использую некоторые концепции поиска в ширину, чтобы получить перестановки, которые помещают головоломку в другую / не посещаемую перестановку, и зацикливаю ее доне получайте никакой новой позиции.

Помимо этого, я использую два алгоритма, чтобы закодировать перестановки в один индекс и извлечь перестановку обратно, стремясь использовать это, чтобы поместить значения глубины в массив. Следующий псевдокод может продемонстрировать, что я делаю: 

Fill table completely with -1
table[pos2idx(theSolvedPermutation)] = 0
depth = 0
loopbegin {
    numOfVisitedPositions = 0
        for (i = 1 to N_PERMUTATIONS) {
            if (table[i] == depth) then {
                for (each available movement m) {
                    current = pos2idx(m applied to idx2pos(i))
                    if (table[current]= -1) then {
                        numOfVisitedPositions++
                        table[current] = depth + 1
                    } endif
                } endfor
            } endif
        } endfor
    depth++
    print numOfVisitedPositions " positions at distance " depth
} loop while numOfVisitedPositions > 0

Однако, похоже, слишком много информации для обработки с помощью этого подхода на этом этапе отображения / индексации.

ЗдесьЭто, соответственно, псевдо для методов pos2idx () и idx2pos (): 

pos2idx(permutation[])
    index = 0
    for i = 1 to length - 2
        index *= (length - i + 1)
        for j = i + 1 to length
            if permutation[i] > permutation[j] then
                index += 1
        endfor
    endfor
return index

idx2pos(index, length)
    n = length
    perm[n]     = 2
    perm[n - 1] = 1
    sum = 0

    for i = n - 2 to 1
        perm[i] = 1 + (index % (n - i + 1))
        sum += perm[i] - 1
        index/= (n - i + 1)
        for j = i + 1 to n
            if perm[j] >= perm[i] then
                perm[j]++
        endfor
    endfor

    if sum % 2 = 1 then
        swap perm[n] with perm[n - 1]

    return perm

Головоломка имеет 12 «движущихся фигур», 8 различных движений и ограничение четности. Последнее означает, что мы не можем получить перестановки с нечетным числом перестановок (например, [1,2,4,3, ..., 12], допустимым может быть [1,2,4,3,12,... 11]), что я думаю, что можно выразить значением 12! / 2. Но, вероятно, с точки зрения сложности, алгоритм не заканчивается с таким количеством данных: мой ноутбук i3 с 6 ГБ оперативной памяти потратил 6 минут, чтобы получить JavaHeapSizeException, хахаха.

Я просто применил тот же подход с учетом головоломкиу меня было только 8 элементов с 4 различными движениями (тогда было бы 8! / 2 перестановок), и я успешно достигал примерно 130000 и 145000 решений в секунду.

Затем, есть какой-нибудь намек на то, как обрабатывать / индексироватьэто количество перестановок в этом алгоритме или этот алгоритм не может закончить в такой большой обработке? Любая помощь приветствуется!

Некоторые ссылки: - Компьютерная головоломка - Индексирование - Полезная математика

1 Ответ

1 голос
/ 03 октября 2019

Одно соображение, которое уменьшило бы количество конфигураций для просмотра:

Ваш текущий код рассматривает два состояния как отличающиеся, когда они действительно одинаковы с человеческой точки зрения;это когда вы можете сделать переход, просто повернув весь куб. Такой переход не считается движением, поэтому эти два состояния следует рассматривать как одно и то же. Это уменьшает количество отдельных состояний в 12 раз.

Например, вы можете потребовать, чтобы одна конкретная фигура всегда оставалась в одной и той же координате. Это будет означать, что вам придется переопределить некоторые из доступных ходов, чтобы они не касались этой конкретной части. Например, допустим, что вы всегда будете держать фигуру 12 в позиции 12 (она никогда не будет переставлена), и что у вас в данный момент есть ход, закодированный как перестановка фигур 10, 11 и 12. Затем переопределите этот ход как перестановку. частей 1..9, как если бы вы сначала повернули весь куб в направлении, противоположном предполагаемому движению (вокруг этого угла), а затем выполнили это движение (вернув кусок 12 в свое гнездо).

Это означает, что вам не нужно ничего хранить в 12-м фрагменте: вместо length может быть 11. При этом ваше table будет в 12 раз меньше.

...