[PYTHON] Einfache Bit-Vollsuche (Easy Set)

Einführung

Die Implementierung der Vollbit-Suche unter Verwendung der Bit-Operation ist etwas schwer. Da die Bit-Vollsuche selbst mit der Vollsuche der Menge identisch ist, basierend auf der Idee, jede Teilmenge der Menge aufzulisten, wenn es sich um eine Programmiersprache (Python, Ruby, Rust usw.) handelt, die über eine Bibliothek verfügt, in der Kombinationen aufgelistet sind Es kann leicht implementiert werden. Dieser Artikel wird seine Implementierung vorstellen.

Besprechung

Eine Potenzmenge (Potenzmenge) ist eine Menge, die aus einer gegebenen Menge als Ganzes ihrer Teilmenge in der Mathematik neu erstellt wird.

Bit vollständige Suche

Die Bit-Vollsuche ist eine Methode zum Durchsuchen aller Muster einer Teilmenge einer Menge.

Eine Kombination kann ausgedrückt werden, indem die Menge als Bitarray ausgedrückt wird und 1 eingestellt wird, um ein bestimmtes Element auszuwählen, und 0, um kein Element auszuwählen.

Kombinationsbeispiel: Wählen Sie B, C, E von A bis F.

Wenn Sie alle Muster der Kombinationen sammeln, die in der Bit-Vollsuche aufgeführt sind, handelt es sich nur um eine Menge.

Praktisches Problembeispiel

Ich möchte einige meiner N Freunde zu einer Online-Trinkparty einladen. Ich möchte jedoch keine schlechte Gruppe haben. Finden Sie die maximale Anzahl von Personen, die Sie einladen können.

Beispiel

Kombinationsbeispiel

Politik

Listen Sie alle Kombinationen von Freunden auf, die Sie einladen möchten. Finden Sie eine Kombination, die für Sie nicht schlecht ist. Die maximale Anzahl von Personen in der Kombination wird ausgegeben.

Methode

Wir werden das Thema dieses Artikels "Einfache Bit-Vollsuche" verwenden. Mit anderen Worten, es ist eine Aufzählung jeder Teilmenge einer einfachen Menge.

Es gibt bereits viele sehr leicht verständliche Artikel über die Vollbit-Suche mit Bit-Arithmetik. Bitte beziehen Sie sich darauf.

https://drken1215.hatenablog.com/entry/2019/12/14/171657 --Kenchon-san https://qiita.com/gogotealove/items/11f9e83218926211083a-@gogotealove https://qiita.com/hareku/items/3d08511eab56a481c7db-@ hareku

In diesem Artikel werde ich Ihnen zeigen, wie Sie den Satz einfach aufzählen können.

Einfache vollständige Suche

Erstens ist die 冪-Menge eine Menge, die eine Sammlung von Teilmengen einer bestimmten Menge ist.

Es listet alle Kombinationen auf, wenn 0 Teile ausgewählt werden, alle Kombinationen, wenn 1 Teil ausgewählt wird, alle Kombinationen, wenn 2 Teile ausgewählt werden, ... und alle Kombinationen, wenn N Teile aus einem Satz mit N Elementen ausgewählt werden. Sie können es tun, wenn Sie gehen.

Python verfügt über eine Bibliothek (Kombinationen), in der Kombinationen aufgelistet sind, sodass Sie sie problemlos implementieren können. Zusätzlich zu Python sind die meisten Programmiersprachen mit einer Bibliothek möglich, in der Kombinationen wie Ruby und Rust aufgelistet sind.

Unten finden Sie ein Beispiel für die Implementierung in Python.

from itertools import combinations 

friends = ["Alice", "Bob", "Charlie", "Dave", "Elisabeth"]
dislike_pairs = [{"Alice", "Charlie"}, {"Alice", "Elisabeth"}, {"Charlie", "Dave"}]

#Eine Funktion, die bestimmt, ob es Paare gibt, die nicht nahe beieinander liegen
def ok(comb):
    comb_set = set(comb)
    return not any(pair.issubset(comb_set) for pair in dislike_pairs)

ans = 0
#Einfache vollständige Suche
for i in range(len(friends)+1):
    for comb in combinations(friends, i):
        if ok(comb):
            ans = max(ans, i)
            
print(ans)

Die Hauptzeilen dieses Artikels sind:

#Einfache vollständige Suche
for i in range(len(friends)+1):
    for comb in combinations(friends, i):
        if ok(comb):
          ...

Die Kombinationen zum Auswählen von 0 Teilen aus dem Satz mit N Elementen, die Kombination zum Auswählen von 1 Stück, die Kombination zum Auswählen von 2 Teilen, ... und die Kombination zum Auswählen von N Teilen werden aufgelistet.

Da jede Teilmenge der Menge in diesen wenigen Zeilen aufgeführt ist, bedeutet dies, dass eine Vollbit-Suche durchgeführt wird.

Zusammenfassung

--bit full search ist die vollständige Suche des Sets

• Um jede Teilmenge der 冪-Menge aufzulisten, zählen Sie jeweils 0 bis N Kombinationen auf.
• Einfache Implementierung in jeder Programmiersprache mit einer Bibliothek, in der Kombinationen aufgelistet sind

Aufgabe

1. Lösen wir das Problem der Online-Trinkparty durch vollständige Bit-Suche mithilfe der Bit-Berechnung.
2. Probleme mit Online-Trinkpartys können durch Vorverarbeitung erheblich reduziert werden. Zum Beispiel ** hat niemand schlechte Beziehungen zu Bob **, sodass Sie ihn im Voraus einladen können. Da der Rechenaufwand für die Bit-Vollsuche $ O (2 ^ N) $ beträgt, kann der Rechenaufwand stark reduziert werden, wenn N um 1 dekrementiert wird. Lösen wir dieses Problem, indem wir einen Prozess hinzufügen, der Freunde abstößt, die im Voraus keine schlechten Freunde haben.
3. Das Problem der Online-Trinkparty ist ** das Problem, eine Kombination zu finden, die die Einschränkungen erfüllt , so dass es sich um ein kleines " Problem der Einschränkungszufriedenheit " handelt. Ein solches Problem kann effizienter als die Vollbit-Suche durch die Tiefenprioritätssuche gefunden werden, die als " Backtrack-Methode **" bezeichnet wird. Lösen wir es mit der Backtrack-Methode.