[PYTHON] Recherche complète simplifiée (facile à régler)

introduction

La mise en œuvre de la recherche de bits complète à l'aide de l'opération de bits est un peu lourde. Étant donné que la recherche de bits complète elle-même est la même que la recherche complète de l'ensemble, basée sur l'idée d'énumérer chaque sous-ensemble de l'ensemble, s'il s'agit d'un langage de programmation (Python, Ruby, Rust, etc.) qui a une bibliothèque qui répertorie les combinaisons Il peut être facilement implémenté. Cet article présentera sa mise en œuvre.

Réunion

Un ensemble de puissances (ensemble de puissances) est un ensemble nouvellement créé à partir d'un ensemble donné comme un ensemble de son sous-ensemble en mathématiques.

recherche peu complète

La recherche complète de bits est une méthode pour rechercher tous les modèles d'un sous-ensemble d'un ensemble.

Une combinaison peut être exprimée en exprimant l'ensemble sous forme de tableau de bits et en définissant 1 pour sélectionner un certain élément et 0 pour ne pas sélectionner d'élément.

Exemple de combinaison: sélectionnez B, C, E de A à F

Si vous collectez tous les modèles des combinaisons répertoriées dans la recherche de bits complète, ce ne sera qu'un ensemble.

Exemple de problème pratique

Je veux inviter certains de mes N amis à une soirée en ligne. Cependant, je ne veux pas avoir un mauvais groupe. Trouvez le nombre maximum de personnes que vous pouvez inviter.

Exemple

Exemple de combinaison

politique

Liste toutes les combinaisons d'amis à inviter. Trouvez une combinaison qui ne vous convient pas. Le nombre maximum de personnes dans la combinaison est affiché.

Méthode

Nous utiliserons le thème de cet article, "Easy bit full search". En d'autres termes, il s'agit d'une énumération de chaque sous-ensemble d'un ensemble simple.

Il existe déjà de nombreux articles très faciles à comprendre sur la recherche de bits complets à l'aide de l'opération de bits, veuillez donc vous y référer.

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

Dans cet article, je vais vous montrer comment énumérer facilement l'ensemble.

Recherche simple et complète

Tout d'abord, l'ensemble 冪 est un ensemble qui est une collection de sous-ensembles d'un certain ensemble.

Il énumère toutes les combinaisons lors de la sélection de 0 pièces, toutes les combinaisons lors de la sélection d'une pièce, toutes les combinaisons lors de la sélection de 2 pièces, ..., et toutes les combinaisons lors de la sélection de N pièces d'un ensemble avec N éléments. Vous pouvez le faire si vous y allez.

Python a une bibliothèque (combinaisons) qui répertorie les combinaisons, vous pouvez donc facilement l'implémenter. En plus de Python, la plupart des langages de programmation qui ont une bibliothèque qui répertorie des combinaisons telles que Ruby et Rust sont possibles.

Voici un exemple d'implémentation en Python.

from itertools import combinations 

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

#Une fonction qui détermine s'il y a des paires qui ne sont pas proches les unes des autres
def ok(comb):
    comb_set = set(comb)
    return not any(pair.issubset(comb_set) for pair in dislike_pairs)

ans = 0
#Recherche simple et complète
for i in range(len(friends)+1):
    for comb in combinations(friends, i):
        if ok(comb):
            ans = max(ans, i)
            
print(ans)

Les principales lignes de cet article sont:

#Recherche simple et complète
for i in range(len(friends)+1):
    for comb in combinations(friends, i):
        if ok(comb):
          ...

Les combinaisons pour sélectionner 0 pièces dans l'ensemble avec N éléments, la combinaison pour sélectionner 1 pièce, la combinaison pour sélectionner 2 pièces, ..., et la combinaison pour sélectionner N pièces sont listées respectivement.

Puisque chaque sous-ensemble de l'ensemble est répertorié dans ces quelques lignes, cela signifie qu'une recherche de bits complète est effectuée.

Résumé

--bit full search est une recherche complète de l'ensemble

• Afin d'énumérer chaque sous-ensemble de l'ensemble 冪, énumérer respectivement 0 à N combinaisons. --Facile à implémenter dans n'importe quel langage de programmation qui a une bibliothèque qui répertorie les combinaisons

Tâche

1. Résolvons le problème de la fête en ligne par une recherche de bits complète en utilisant le calcul de bits.
2. Les problèmes de boisson en ligne peuvent être considérablement réduits par le prétraitement. Par exemple, ** personne n'est en mauvais termes avec Bob **, vous pouvez donc l'inviter à l'avance. Étant donné que la quantité de calcul pour la recherche complète de bits est $ O (2 ^ N) $, la quantité de calcul peut être considérablement réduite si N est décrémenté de 1. Résolvons ce problème en ajoutant un processus qui repousse les amis qui n'ont pas de mauvais amis à l'avance.
3. Le problème des buveurs en ligne est ** le problème de trouver une combinaison qui répond aux contraintes , on peut donc dire qu'il s'agit d'un petit " problème de satisfaction de contraintes ". Un tel problème peut être trouvé plus efficacement que la recherche de bits complète par la recherche de priorité de profondeur appelée " méthode de retour arrière **". Résolvons-le avec la méthode backtrack.