Przepraszam, czy to było gdzieś odpowiedziałeś, próbowałem wyszukać, ale nie wiem, czy ten rodzaj problemu ma określoną nazwę, więc nic nie pojawiło się w moim wyszukiwaniu ...

Mam listę obiektów, a każdy z tych obiektów może zostać przyjęty lub odrzucony. Każda kombinacja przypisuje wartość, podczas gdy niektóre kombinacje są nieprawidłowe. (Tak więc na przykład mamy 4 obiekty, a obiekty 1 i 2 nie idą razem, a następnie każda kombinacja, która ma obiekty 1 i 2 jako akceptowane jest nieprawidłowe.) Nie jest znany wcześniej, które obiekty nie idą razem i jest Nie można znaleźć nieprawidłowych tych, którzy patrząc na pary. (Na przykład możliwe jest, że obiekty 1, 2 są ważne razem, obiekty 2,3 są ważne, obiekty 1,3 są ważne, ale 1,2,3 są nieprawidłowe.) Modelowałem to jako listy 0 i 1 Teraz chcę przemierzać te listy, aby znaleźć ten z maksymalną wartością w sposób efektywny.

Moim pomysłem było przemieszczenie list takich jak drzewo, zaczynając od wszystkich zer, a następnie w każdym kroku odwracając zero do jednego, więc na przykład dla 3 obiektów daje drzewo

                000
            /    |    \
        100     010     001
        / \     / \     / \
      110 101 110 011 101 011
        \  \   \   /   /   /
                111

Który jest w rzeczywistości gorszy niż wpisanie wszystkich opcji 2 ^ n, ponieważ są duplikaty, ale w każdym węzła mogłem zatrzymać się, gdybym odkrył, że jest to nieprawidłowe. Zapisywanie nieprawidłowych kombinacji z nich i utrzymywanie listy wszystkich już odwiedzanych węzłów, które mogłem upewnić się, że nie odwiedzam już sprawdzonych węzłów. (Ale nadal musiałbym sprawdzić te, gdy już byli odwiedzane)

Czy jest lepszy sposób, aby to zrobić?

1
Tobias Kietreiber 3 sierpień 2020, 11:40

1 odpowiedź

Najlepsza odpowiedź

Możesz spróbować zbudować drzewo wariantów (najwyżej 2 ^ n opcjach, jak zauważyłeś), ale wyciąć niezwykłe gałęzie jak najszybciej.

W przykładzie poniżej ustawiłem dwie maski binarne - nie 1,2,3 razem i nie 2,4 razem

def buildtree(x, maxsize, level, masks):
    if level == maxsize:
        print("{0:b}".format(x).zfill(maxsize))
    else:
        buildtree(x, maxsize, level + 1, masks)
        t = x | (1 << level)
        good = True
        for m in masks:
            if (t & m) == m:
                good = False
                break
        if good:
            buildtree(t, maxsize, level + 1, masks)

buildtree(0, 4, 0, [7, 10])

0000
1000
0100
1100
0010
0110
0001
1001
0101
1101
0011

Jest możliwe również usuwanie niektórych masek, ale kod będzie bardziej skomplikowany

0
MBo 3 sierpień 2020, 09:06