[PYTHON] Apprenez avec Supra Nervous Weakness! La théorie des graphes

introduction

Présentation de la connaissance de la théorie des graphes utilisée dans Supra Nervous Weakness faite comme passe-temps, et comment l'algorithme de la théorie des graphes est appliqué à des problèmes réels. C'est un article qui vise à s'amuser à apprendre.

L'application est ouverte au public, alors jouez avec si vous le souhaitez.

Faiblesse supra nerveuse

Aperçu de l'application

J'ai écrit sur mon blog sur les règles, les problèmes lors du développement et une partie du contenu de l'implémentation, alors lisez-le pour plus de détails.

Sortie de l'application Supra Nervous Weakness - Gugurira Nikki

Voici un bref aperçu, en vous concentrant sur ce dont vous avez besoin pour lire cet article.

C'est fondamentalement la même règle que la faiblesse nerveuse normale.

La différence avec une faiblesse nerveuse normale est qu'il existe une grande variété d'adversaires pour les cartes à appairer, et le score change en fonction de la rareté de la paire.

Dans Supra Nervous Weakness, retournez chaque carte avec le buki de Suplatoon et associez-le.

Il y a beaucoup de buki dans Splatoon, et chaque buki a une arme principale, une arme secondaire et une arme spéciale.

Dans la figure ci-dessus, l'arme principale est affichée à gauche, et l'arme secondaire et l'arme spéciale sont affichées à droite.

Dans Supra Nervous Weakness, vous pouvez associer si l'une des armes principales, secondaires ou spéciales de Buki correspond.

De plus, le score lors de l'appariement changera en fonction du type de paire. Si vous obtenez une paire rare, vous obtiendrez un score élevé, et s'il s'agit d'un ensemble de cartes faciles à coupler, vous obtiendrez un score faible.

La logique de définition de ce score est omise dans cet article.

Vous pouvez le voir comme un graphique non orienté pondéré en utilisant Buki comme nœud, s'il peut être couplé en tant qu'arête, et le score lorsqu'il est associé en tant que poids d'arête.

Cette fois, j'aimerais apprendre les connaissances de la théorie des graphes requises pour la faiblesse nerveuse Supra en utilisant ce graphe non orienté pondéré comme thème.

Quelle carte utilisez-vous pour le jeu? ~ Graphe partiel concaténé ~

Cette fois, nous avons ciblé Splatoon 2 Buki, il y a donc 139 types de cartes au total. Si vous utilisez tout cela pour affaiblir vos nerfs, vos nerfs s'affaibliront vraiment, alors je voudrais n'en retirer qu'une partie et l'utiliser dans le jeu. (12 types seront utilisés pour le jeu cette fois.)

Le moyen le plus simple est de sélectionner parmi 139 types de buki de manière complètement aléatoire sans permettre la duplication, mais cette méthode tend à réduire le nombre de paires qui peuvent être créées.

de cette façon,

• Je veux que le type de carte change à chaque fois
• Et il est facile de faire une paire dans une certaine mesure

Il est impératif que vous souhaitiez obtenir un jeu de cartes.

Cette fois pour répondre à cette exigence

1. Sélectionnez au hasard un buki
2. Obtenir aléatoirement des candidats pour le buki qui peuvent être jumelés avec l'un des buki actuellement sélectionnés
3. Continuez 2 jusqu'à ce que 12 soient collectés

J'ai fait l'algorithme.

Lorsque vous créez un graphique avec Buki comme nœud et s'il est couplé en tant qu'arête, vous sélectionnez au hasard le nœud du point de départ et échantillonnez un graphe partiel connecté qui inclut ce nœud.

Voici celui implémenté en Python.

def get_connected_subgraph(mat, seed_node, nodes_num):
    """Reçoit une matrice adjacente et des nœuds qui sont des graines, et le nombre de nœuds est des nœuds_Renvoie un graphe partiel concaténé de num."""
    ans = {seed_node}
    while len(ans) < nodes_num:
        sampled = random.sample(ans, 1)[0]
        connected_nodes = set(np.where(mat[sampled] > 0)[0].tolist())
        candidates = list(connected_nodes - ans)
        if len(candidates) == 0:
            raise Exception("Failed.")
        to_be_added = random.choice(candidates)
        ans.add(to_be_added)
    return list(ans)

Bien sûr, il n'est pas nécessaire d'avoir un composant connecté, mais si vous prenez un graphe partiel avec un composant connecté avec un petit nombre d'éléments, la variété des paires sera petite et le jeu ne sera pas intéressant, donc le composant connecté est J'en ai fait un.

Voici un dessin du graphe acquis aléatoirement par ce code. Si c'est 12, c'est difficile à comprendre, alors je l'ai réduit à 6.

Pouvez-vous vous débarrasser de toutes les cartes? ~ Correspondance parfaite ~

Correspondance parfaite

Les sous-graphes concaténés obtenus par l'algorithme du chapitre précédent sont un peu plus faciles à appairer. Puisqu'il est lié, il y a des adversaires qui peuvent jumeler n'importe quelle carte au début de la partie.

Cependant, ce n'est pas parce qu'il est connecté que vous pouvez supprimer toutes les cartes. Ce qui suit est un exemple. Deux nœuds sont laissés de côté par tous les moyens.

L'appariement est le problème de la création de paires entre des nœuds connectés par des arêtes à partir des nœuds du graphe. (Le même nœud ne peut pas être utilisé deux fois.)

La question à laquelle je veux réfléchir cette fois est: "Lors de la mise en correspondance des nœuds du graphe obtenu, la mise en correspondance peut-elle être effectuée de sorte que tous les nœuds soient épuisés?"

La correspondance qui utilise tous les nœuds de cette manière est appelée correspondance parfaite.

Dans ce cas, si l'ensemble de cartes (le graphique composé de) est un graphique qui a une correspondance parfaite, alors ** j'espère que toutes les cartes peuvent être supprimées **. On peut dire ça.

Il semble difficile de récupérer directement un graphique qui a une correspondance parfaite entre les graphiques partiels d'un certain graphique (veuillez me dire s'il existe un bon moyen).

Cette fois, je jugerai "Est-ce que le graphe a une correspondance parfaite?" Le graphe obtenu en utilisant la méthode du graphe partiel expliquée précédemment. La logique est de continuer à échantillonner jusqu'à ce qu'un graphique avec une correspondance parfaite existe.

Jugement de l'appariement parfait

Le jugement est "Le graphe est-il avec une correspondance parfaite?", Mais cela peut être jugé en utilisant le théorème de Tutte.

Référence: Je veux être ami avec le théorème de Tutte

J'ai implémenté la logique de jugement selon ce théorème. Écrit en Python.

python

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
import itertools

def get_all_sub_indexes(repeat_num):
    """peu pour une recherche complète"""
    sub_indexes = []
    for case in itertools.product([0, 1], repeat=repeat_num):
        sub_indexes.append([i for i, v in enumerate(case) if v == 1])
    return sub_indexes

def exists_perfect_matching(G):
    """Prend la matrice adjacente du graphique et détermine si elle contient le graphique complet."""
    size_G = G.shape[0]
    sub_indexes = get_all_sub_indexes(size_G)

    for sub_index in sub_indexes:
        # sub_l'index est G-Équivalent à U
        size_U = size_G-len(sub_index)
        G_minus_U = G[np.ix_(sub_index, sub_index)]
        #Décomposé en composants de connexion
        csr_graph = csr_matrix(G_minus_U)
        _, groups = connected_components(csr_graph, directed=False)
        conntected_nodes = collections.Counter(groups)
        odd_G_minus_U = len(
            [freq for freq in conntected_nodes.values() if freq % 2 == 1])
        if odd_G_minus_U > size_U:  #Du théorème de Tutte
            return False
    return True

Une recherche de bits complète est effectuée sur l'ensemble de nœuds, les nœuds sont supprimés du graphe d'origine et décomposés en composants connectés, et le nombre de composants connectés avec un nombre impair de nœuds est compté et jugé par l'inégalité du théorème de Tutte.

La recherche complète de bits utilise «itertools» et la décomposition des composants concaténés utilise «scipy». Si le nombre de nœuds est de 12, cela prendrait un peu de temps. Cela coûte $ O (2 ^ n) $ dans la partie de recherche de bits complet, donc cela semble être lourd si le nombre de nœuds est un peu plus grand.

La logique était de continuer à échantillonner jusqu'à ce qu'un graphique avec une correspondance parfaite existe. J'avais peur que si la correspondance parfaite était difficile à obtenir, la latence augmenterait lorsque j'y accédais, alors j'ai expérimenté.

Quand j'ai pris un graphique avec 12 nœuds au hasard (mais concaténés) et vérifié s'il incluait une correspondance parfaite, j'ai simulé 100 fois et j'ai constaté que le graphique n'incluait pas de correspondance parfaite une seule fois. était. Il y a 1% de chances que la correspondance parfaite soit jugée deux fois, donc si vous sentez qu'elle est un peu lourde, elle peut être de 1%.

Comme le graphique d'origine est un graphique assez dense, il peut être facile d'obtenir une correspondance parfaite. (Bien sûr, il est efficace de faire venir des candidats faciles à associer parfaitement en introduisant un graphe concaténé.)

Ne pouvez-vous pas faire un "graphique qui peut prendre toutes les cartes absolument"?

Auparavant, un graphique avec une correspondance parfaite = ** J'espère que toutes les cartes peuvent être supprimées ** J'avais l'habitude de dire que quelque chose était coincé dans les dents arrière du graphique, mais ** Un graphique avec une correspondance parfaite est absolument Toutes les cartes ne peuvent pas être supprimées. ** **

Même s'il y a une correspondance parfaite, cela peut entraîner une correspondance non parfaite.

Ici encore, en termes de théorie des graphes, «l'appariement qui ne peut pas ajouter plus de paires» est appelé appariement maximal. En termes de faiblesse nerveuse Supra cette fois, il s'agit d'un appariement dans un état où le nombre de paires ne peut plus être augmenté.

On peut dire que la condition de fin du jeu est lorsque les cartes sont jumelées et que la correspondance devient la correspondance maximale. Tout simplement parce qu'il y a une correspondance parfaite, toutes les correspondances maximales ne sont pas des correspondances parfaites, c'est donc devenu l'expression ** j'espère que toutes les cartes peuvent être supprimées **. ..

Dans la faiblesse nerveuse conventionnelle, toute correspondance maximale est une correspondance parfaite, il est donc possible de finalement couper toutes les cartes, peu importe comment vous la prenez.

Alors, pour un graphe donné, ce serait bien si nous pouvions juger "Est-ce que tous les appariements maximaux sont parfaits?" Je pense, mais cela semblait difficile.

On juge si la correspondance minimale et maximale correspond parfaitement, mais j'ai abandonné car il semble difficile de trouver la correspondance minimale et maximale.

[Problème de correspondance minimum maximum - Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E6%A5%B5%E5%A4%A7%E3%83% 9E% E3% 83% 83% E3% 83% 81% E3% 83% B3% E3% 82% B0% E5% 95% 8F% E9% A1% 8C #: ~: texte =% E6% 9C% 80% E5% B0% 8F% E6% A5% B5% E5% A4% A7% E3% 83% 9E% E3% 83% 83% E3% 83% 81% E3% 83% B3% E3% 82% B0% E5% 95% 8F% E9% A1% 8C% EF% BC% 88% E3% 81% 95% E3% 81% 84,% E3% 81% 8C% E7% 9F% A5% E3% 82% 89% E3% 82 % 8C% E3% 81% A6% E3% 81% 84% E3% 82% 8B% E3% 80% 82)

Pour cette raison, puisque nous n'utilisons que des graphiques qui ont une correspondance parfaite, le problème de tomber dans une correspondance maximale qui n'est pas une correspondance parfaite demeure.

Le chiffre lorsque les deux dernières feuilles sont terminées sans être appariées.

Quel est le point le plus élevé théorique? ~ Correspondance de poids maximum ~

En plus de la partie qui échantillonne le graphe, j'aimerais présenter un autre processus qui utilise la théorie des graphes.

Nous utiliserons l'ensemble de cartes échantillonné comme décrit ci-dessus pour affaiblir nos nerfs, mais comme le score maximum qui peut être obtenu change pour chaque graphique échantillonné, ** le score que j'ai obtenu est élevé ou faible. Il y a un problème qu'il est difficile de comprendre **.

Par conséquent, il serait bien de pouvoir calculer et afficher le score le plus élevé pouvant être obtenu lorsque la faiblesse nerveuse se produit dans le graphique au stade de l'échantillonnage du graphique.

En théorie des graphes, ce problème est le problème de correspondance de poids maximum.

Le problème de correspondance de poids maximum est un problème de recherche d'une correspondance qui maximise la somme des poids, ce qui correspond à ce que nous voulons faire cette fois.

Il semblait y avoir une implémentation Python ici, alors j'ai utilisé ceci.

Référence: Optimisation de combinaison - Problème typique - Problème de correspondance de poids - Qiita

import networkx as nx
from ortoolpy import graph_from_table

def get_max_weight_matching(mat):
    node_df = pd.DataFrame({"id": list(range(len(mat)))})
    edge_df = graph2df(mat)
    g = graph_from_table(node_df, edge_df)[0]
    d = nx.max_weight_matching(g)
    return sum([mat[k, v] for k, v in d.items()])/2  #Parce que ça compte deux fois

def graph2df(graph):
    edge_df = pd.DataFrame(columns=['node1', 'node2', 'weight'])
    for i in range(graph.shape[0]):
        for j in range(i, graph.shape[1]):
            if graph[i, j] > 0:
                edge_df = edge_df.append(
                    {'node1': i, 'node2': j, 'weight': graph[i, j]}, ignore_index=True)
    return edge_df.astype("int64")

Trouvons le poids maximal correspondant à ce graphique obtenu précédemment.

C'est,

Il sera assorti comme ça. La valeur théorique du score le plus élevé de ce graphique était de 162.

En passant, dans ce résultat, la correspondance de poids maximum est une correspondance parfaite, mais en général elle ne correspond pas toujours.

En d'autres termes, même si vous coupez toutes les cartes comme indiqué sur cette figure, il est possible que vous n'atteigniez pas le score le plus élevé.

en conclusion

Cette fois, j'ai découvert la théorie des graphes utilisée en interne, en particulier la correspondance, basée sur ma propre application appelée Supra Nervous Weakness.

C'est passionnant de voir comment les mathématiques sont appliquées à de vrais problèmes, pas seulement à la théorie des graphes. Quand je suis réellement confronté à un problème, j'aimerais avoir beaucoup de tiroirs demandant "Cet algorithme est-il utilisable?"

Jusqu'à la fin Merci d'avoir lu!