алгоритм обхода вариантов по дереву

Question

Помогите решить следующую проблему (язык не важен, важен алгоритм, а в вопросе я для простоты на питоне запишу):

есть все возможные 5-битовые маски:

требуется применить каждую маску для анализа

analyze(mask)

при этом если результат анализа положительный, то не рассматривать все остальные маски имеющие со сработавшей хотя бы один общий установленный бит, т.е. если сработала маска 0b00001, то маской 0b01101 анализировать уже не следует

в лоб алгоритм выглядит так:

excluded = 0

for mask in masks:
    # если маска в исключениях - перейти к следующей маске
    if mask & excluded:
        continue

    # проанализировать текущую маску и установить исключения
    if analyze(mask):
        excluded |= mask

алгоритм неплохой, но медленный, поэтому (+ была еще одна целесообразность) я разбил все маски на группы по кол-ву установленных бит, а каждую группу разбил на 0b100000 групп, в результате алгоритм приобрел вид:

excluded = 0

for size in range(0, 6):

    # анализировать только требуемыми масками
    for mask in masks_groups[size][excluded]:

        # проанализировать текущую маску и установить исключения
        if analyze(mask):
            excluded |= mask

такой подход увеличил производительность в 2 раза с незначительным увеличением использования памяти

И тут встал вопрос:

а можно ли (вернее чувствую, что можно, но голова уже не варит) сделать не дискретную выборку маски по кол-ву бит в маске, а плавный - т.е. чтобы после каждого анализа на основании значения из excluded выбиралась следующая маска?

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

mask = tree

while mask != 0:
    mask = mask[excluded]

    if analyze(mask):
        excluded |= mask

подскажите, можно ли так сделать и если можно, то как?

т.е. с помощью текущей маски и исключений я определяю следующую маску, которая не содержит бит из исключений

например, если analyze постоянно будет отрицательным мне придется пройти по всем существующим маскам, а если analyze для масок 0b10000, 0b01000, 0b00100, 0b00010, 0b00001, будет положительным, то после последней маски цикл прекратится

как я понимаю должно быть дерево (по сути некоторый массив) где каждый элемент массива содержит индекс массива в который надо заглянуть и этот индекс и есть текущая маска, если элемент массива с этим индексом нулевой (содержит 0 или -1 не суть) значит обход масок закончился

Answer 1

Посмотрите, правильно ли я понял задачу?

check - эмуляция, ловля двух масок. После того, как найдена маска 0b00010, числа, в которых включен второй бит, в проверках уже не участвуют.

После того, как проверена маска 0b00101, числа, в которых включены либо первый, либо третий бит, в проверках уже не участвуют (но часть из них уже была проверена ранее, и не похоже, что от этого можно избавиться)

Базовый перебор подмасок - например, здесь описан

def inv(s):
    return s^0b11111

def check(s):
    return((s & 0b10 == 0b10) or (s & 0b101 == 0b101))

mask = 0b11111
excl = 0b00000
sm = mask
while sm:
    sm = (sm - 1) & mask
    sub = inv(sm | excl)
    print("check {0:b}".format(sub))
    if check(sub):
        print('out        ', "{0:b}".format(sub))
        excl |= inv(sm)
        mask = sm

check 1
check 10
out         10
check 1
check 100
check 101
out         101
check 1000
check 10000
check 11000

Answer 2

Придумал как можно сделать

основная мысль - требуется матрица NxN где N = 2^k (по сути кол-во бит в маске), ячейка в матрице показывает какая следующая маска должна выбираться

первоначально создаем совокупность масок при excluded = 0, т.е. как обходили маски по умолчанию
далее рассчитываем таблицу так чтобы ячейка с координатами [excluded][mask] содержала бы следующую маску

код:

# сформировать таблицу для обхода масок
size = 0b10000

table = [[0] * size for _ in range(size)]

# заполнить таблицу для обхода масок
for excluded in range(size):

    # сформировать массив масок в которых не установлены исключённые биты
    masks_prepared = [mask for mask in masks if mask & excluded == 0]
   
    # внести обход подготовленных масок в таблицу
    for mask_index in range(len(masks_prepared) - 1):
        table[excluded][masks_prepared[mask_index]] = masks_prepared[mask_index + 1]

    table[excluded][masks_prepared[len(masks_prepared) - 1]] = -1

    # внести обход оставшихся масок в таблицу
    for mask_index in range(len(masks)):
        # не рассматривать уже обработанные маски
        if masks[mask_index] in masks_prepared:
            continue

        # найти следующую обработанную маску
        found_index = mask_index

        for index in range(mask_index + 1, len(masks)):
            if masks[index] in masks_prepared:
                found_index = index
                break

        table[excluded][masks[mask_index]] = -1 if found_index == mask_index else masks[found_index]

В результате обход получается очень простым и максимально коротким (С++):

int excluded = 0;
int mask = 0;

while ((mask = table[excluded][mask]) != -1)
{
    if (analyze(mask))
        excluded |= mask;
}

БЛОГ НА HUSL

алгоритм обхода вариантов по дереву

Ответы (2 шт):