[PYTHON] Lerne mit übernervöser Schwäche! Graphentheorie

Einführung

Einführung in die Kenntnisse der Graphentheorie, die in Supra Nervous Weakness als Hobby verwendet werden, und wie der Algorithmus der Graphentheorie auf tatsächliche Probleme angewendet wird. Dies ist ein Artikel, der Spaß am Lernen haben soll.

Die App ist für die Öffentlichkeit zugänglich. Spielen Sie also bitte damit, wenn Sie möchten.

Supra nervöse Schwäche

Übersicht über die App

Ich habe in meinem Blog über die Regeln, Probleme während der Entwicklung und einen Teil des Inhalts der Implementierung geschrieben. Bitte lesen Sie dies für Details.

Supra Nervous Weakness App veröffentlicht - Gugurira Nikki

Hier ist eine kurze Übersicht, die sich auf das konzentriert, was Sie zum Lesen dieses Artikels benötigen.

Es ist im Grunde die gleiche Regel wie normale Nervenschwäche.

Der Unterschied zur normalen Nervenschwäche besteht darin, dass es eine Vielzahl von Gegnern für die zu paarenden Karten gibt und sich die Punktzahl je nach Seltenheit des Paares ändert.

Drehen Sie in Supra Nervous Weakness jede Karte mit Suplatoons Buki um und koppeln Sie sie.

Es gibt viele Buki in Splatoon, und jeder Buki hat eine Hauptwaffe, eine Nebenwaffe und eine Spezialwaffe.

In der Abbildung oben wird links die Hauptwaffe und rechts die Nebenwaffe und die Spezialwaffe angezeigt.

In Supra Nervous Weakness kannst du koppeln, ob eine der Hauptwaffen, Nebenwaffen oder Spezialwaffen von Buki übereinstimmt.

Außerdem ändert sich die Punktzahl beim Pairing je nach Paartyp. Wenn Sie ein seltenes Paar erhalten, erhalten Sie eine hohe Punktzahl, und wenn es sich um einen Kartensatz handelt, der leicht zu koppeln ist, erhalten Sie eine niedrige Punktzahl.

Die Logik zum Festlegen dieser Punktzahl wird in diesem Artikel weggelassen.

Sie können es als gewichtetes ungerichtetes Diagramm anzeigen, indem Sie Buki als Knoten verwenden, ob es als Kante gepaart werden kann, und die Punktzahl, wenn es als Kantengewicht gepaart wird.

Dieses Mal möchte ich die Kenntnisse der Graphentheorie erlernen, die für die Supra-Nervenschwäche erforderlich sind, indem ich diesen gewichteten ungerichteten Graphen als Thema verwende.

Welche Karte benutzt du für das Spiel? ~ Verketteter Teilgraph ~

Dieses Mal haben wir Splatoon 2 Buki ins Visier genommen, also gibt es insgesamt 139 Arten von Karten. Wenn Sie all dies verwenden, um Ihre Nerven zu schwächen, werden Ihre Nerven wirklich geschwächt, daher möchte ich nur einen Teil herausnehmen und ihn im Spiel verwenden. (Dieses Mal werden 12 Typen für das Spiel verwendet.)

Der einfachste Weg besteht darin, aus 139 Buki-Typen völlig zufällig auszuwählen, ohne eine Duplizierung zuzulassen. Diese Methode verringert jedoch tendenziell die Anzahl der Paare, die erstellt werden können.

auf diese Weise,

• Ich möchte, dass sich der Kartentyp jedes Mal ändert
• Und es ist bis zu einem gewissen Grad einfach, ein Paar zu bilden

Es ist eine Voraussetzung, dass Sie einen Kartensatz erhalten möchten.

Diesmal, um diese Anforderung zu erfüllen

1. Wählen Sie zufällig einen Buki aus
2. Erhalten Sie zufällig von Kandidaten für Buki, die mit einem der aktuell ausgewählten Buki gepaart werden können
3. Fahren Sie mit 2 fort, bis 12 gesammelt sind

Ich habe den Algorithmus gemacht.

Wenn Sie ein Diagramm mit Buki als Knoten erstellen und angeben, ob es als Kante gepaart ist, wählen Sie zufällig den Startpunktknoten aus und probieren ein verbundenes Teildiagramm aus, das diesen Knoten enthält.

Hier ist die in Python implementierte.

def get_connected_subgraph(mat, seed_node, nodes_num):
    """Empfängt eine benachbarte Matrix und Knoten, die Seeds sind, und die Anzahl der Knoten ist Knoten_Gibt einen verketteten Teilgraphen von num zurück."""
    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)

Natürlich ist es nicht erforderlich, eine verbundene Komponente zu haben, aber wenn Sie einen Teilgraphen mit einer verbundenen Komponente mit einer kleinen Anzahl von Elementen erstellen, ist die Anzahl der Paare gering und das Spiel nicht interessant, so dass die verbundene Komponente ist Ich habe es geschafft.

Hier ist eine Zeichnung des Diagramms, das zufällig von diesem Code erfasst wurde. Wenn es 12 ist, ist es schwer zu verstehen, also habe ich es auf 6 eingegrenzt.

Kannst du alle Karten loswerden? ~ Perfekte Übereinstimmung ~

Perfekte Übereinstimmung

Die verketteten Untergraphen, die der Algorithmus im vorherigen Kapitel erhalten hat, sind etwas einfacher zu koppeln. Da es verknüpft ist, gibt es Gegner, die zu Beginn des Spiels jede Karte koppeln können.

Nur weil es verbunden ist, bedeutet dies nicht, dass Sie alle Karten entfernen können. Das Folgende ist ein Beispiel. Es bleiben auf jeden Fall zwei Knoten übrig.

Matching ist das Problem, Paare zwischen Knoten zu bilden, die durch Kanten von den Knoten im Diagramm verbunden sind. (Derselbe Knoten kann nicht zweimal verwendet werden.)

Die Frage, über die ich diesmal nachdenken möchte, lautet: "Kann beim Abgleichen der Knoten des erhaltenen Graphen der Abgleich durchgeführt werden, damit alle Knoten aufgebraucht sind?"

Ein Matching, bei dem alle Knoten auf diese Weise verwendet werden, wird als perfektes Matching bezeichnet.

In diesem Fall, wenn der Kartensatz (das Diagramm, aus dem er besteht) ein Diagramm ist, das perfekt übereinstimmt, ** können hoffentlich alle Karten entfernt werden **. Das kann man sagen.

Es scheint schwierig zu sein, ein Diagramm direkt abzurufen, das perfekt zu den Teildiagrammen eines bestimmten Diagramms passt (bitte sagen Sie mir, ob es einen guten Weg gibt).

Dieses Mal werde ich beurteilen, ob der Graph perfekt übereinstimmt. Der Graph, der unter Verwendung der zuvor erläuterten partiellen Graphmethode erhalten wurde. Die Logik besteht darin, die Abtastung so lange fortzusetzen, bis ein Diagramm mit perfekter Übereinstimmung vorhanden ist.

Beurteilung der perfekten Übereinstimmung

Das Urteil lautet "Stimmt der Graph perfekt überein?", Dies kann jedoch mit dem Satz von Tutte beurteilt werden.

Referenz: Ich möchte mit Tuttes Theorem befreundet sein

Ich habe die Beurteilungslogik nach diesem Theorem implementiert. Geschrieben in Python.

python

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

def get_all_sub_indexes(repeat_num):
    """Bit für die vollständige Suche"""
    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):
    """Nimmt die benachbarte Matrix des Diagramms und bestimmt, ob sie das vollständige Diagramm enthält."""
    size_G = G.shape[0]
    sub_indexes = get_all_sub_indexes(size_G)

    for sub_index in sub_indexes:
        # sub_Index ist G.-Entspricht U.
        size_U = size_G-len(sub_index)
        G_minus_U = G[np.ix_(sub_index, sub_index)]
        #In Verbindungskomponenten zerlegt
        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:  #Aus Tuttes Satz
            return False
    return True

Eine Vollbit-Suche wird an dem Knotensatz durchgeführt, die Knoten werden aus dem ursprünglichen Graphen entfernt und in verbundene Komponenten zerlegt, und die Anzahl verbundener Komponenten mit einer ungeraden Anzahl von Knoten wird gezählt und anhand der Ungleichung des Tutte-Theorems beurteilt.

Verwenden Sie "itertools" für die Vollbit-Suche und "scipy" für die Verkettung verketteter Komponenten. Wenn die Anzahl der Knoten 12 beträgt, würde dies einige Zeit dauern. Es kostet $ O (2 ^ n) $ im Bit-Vollsuche-Teil, daher scheint es schwer zu sein, wenn die Anzahl der Knoten etwas größer ist.

Die Logik bestand darin, die Abtastung so lange fortzusetzen, bis ein Diagramm mit perfekter Übereinstimmung vorhanden ist. Ich befürchtete, dass sich die Latenz erhöhen würde, wenn es schwierig wäre, eine perfekte Übereinstimmung zu finden, wenn ich darauf zugreifen würde, und experimentierte.

Als ich ein Diagramm mit 12 zufälligen Knoten (aber verkettet) nahm und überprüfte, ob es eine perfekte Übereinstimmung enthielt, simulierte ich 100 Mal und stellte fest, dass das Diagramm nicht nur einmal eine perfekte Übereinstimmung enthielt. war. Es besteht eine Wahrscheinlichkeit von 1%, dass die perfekte Übereinstimmung zweimal beurteilt wird. Wenn Sie also der Meinung sind, dass sie etwas schwer ist, kann sie 1% betragen.

Da das ursprüngliche Diagramm ein ziemlich dichtes Diagramm ist, kann es leicht sein, eine perfekte Übereinstimmung zu erzielen. (Natürlich ist es effektiv, Kandidaten einzubeziehen, die sich leicht perfekt anpassen lassen, indem Sie ein verkettetes Diagramm einfügen.)

Können Sie nicht ein "Diagramm erstellen, das alle Karten absolut aufnehmen kann"?

Früher ein Diagramm mit perfekter Übereinstimmung = ** Hoffentlich können alle Karten entfernt werden ** Ich habe immer gesagt, dass sich etwas in den hinteren Zähnen des Diagramms verfangen hat, aber ** Ein Diagramm mit perfekter Übereinstimmung ist absolut Nicht alle Karten können entfernt werden. ** ** **

Selbst wenn es eine perfekte Übereinstimmung gibt, kann dies zu einer nicht perfekten Übereinstimmung führen.

Auch hier wird in Bezug auf die Graphentheorie "Matching, bei dem keine weiteren Paare hinzugefügt werden können" als maximales Matching bezeichnet. In Bezug auf die Supra-Nervenschwäche ist es diesmal ein Matching in einem Zustand, in dem die Anzahl der Paare nicht mehr erhöht werden kann.

Es kann gesagt werden, dass die Endbedingung des Spiels ist, wenn die Karten gepaart werden und die Übereinstimmung die maximale Übereinstimmung wird. Nur weil es eine perfekte Übereinstimmung gibt, ist nicht jede maximale Übereinstimmung eine perfekte Übereinstimmung, daher ist es der Ausdruck geworden ** hoffentlich können alle Karten entfernt werden **. ..

Bei konventioneller Nervenschwäche ist jede maximale Übereinstimmung perfekt, so dass es möglich ist, alle Karten endgültig abzuschneiden, egal wie Sie es nehmen.

Dann wäre es für ein gegebenes Diagramm gut, wenn wir beurteilen könnten, ob alle maximalen Übereinstimmungen perfekt übereinstimmen. Ich denke, aber das schien schwierig.

Es wird beurteilt, ob die minimale und maximale Übereinstimmung perfekt ist, aber ich habe aufgegeben, weil es schwierig zu sein scheint, die minimale und maximale Übereinstimmung zu finden.

[Minimum Maximum Matching Problem-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 #: ~: Text =% 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)

Aus diesem Grund bleibt das Problem bestehen, in eine maximale Übereinstimmung zu fallen, die nicht perfekt übereinstimmt, da wir nur Diagramme verwenden, die eine perfekte Übereinstimmung aufweisen.

Die Zahl, wenn die letzten beiden Blätter fertig sind, ohne gepaart zu werden.

Was ist der theoretisch höchste Punkt? ~ Maximale Gewichtsanpassung ~

Zusätzlich zu dem Teil, der den Graphen abtastet, möchte ich einen weiteren Prozess vorstellen, der die Graphentheorie verwendet.

Wir werden das wie oben beschrieben abgetastete Kartenset verwenden, um unsere Nerven zu schwächen. Da sich jedoch die maximale Punktzahl, die erzielt werden kann, für jedes abgetastete Diagramm ändert, ** ist die Punktzahl, die ich erhalten habe, hoch oder niedrig. Es gibt ein Problem, das schwer zu verstehen ist **.

Daher wäre es schön, die höchste Punktzahl berechnen und anzeigen zu können, die erzielt werden kann, wenn im Diagramm zum Zeitpunkt der Abtastung des Diagramms eine Nervenschwäche auftritt.

In der Graphentheorie ist dieses Problem das Problem der maximalen Gewichtsanpassung.

Das Problem der maximalen Gewichtsanpassung ist das Problem der Suche nach einer Übereinstimmung, die die Summe der Gewichte maximiert und mit dem übereinstimmt, was wir diesmal tun möchten.

Hier schien es eine Python-Implementierung zu geben, also habe ich sie verwendet.

Referenz: Kombinationsoptimierung - Typisches Problem - Gewichtsanpassungsproblem - 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  #Weil es zweimal zählt

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")

Lassen Sie uns die maximale Gewichtsübereinstimmung für dieses Diagramm ermitteln, die zuvor erhalten wurde.

Das ist,

Es wird so abgestimmt. Der theoretische Wert der höchsten Punktzahl in dieser Grafik betrug 162.

Abgesehen davon ist in diesem Ergebnis die maximale Gewichtsanpassung eine perfekte Übereinstimmung, aber im Allgemeinen stimmt sie nicht immer überein.

Mit anderen Worten, selbst wenn Sie alle Karten wie in dieser Abbildung gezeigt abschneiden, ist es möglich, dass Sie nicht die höchste Punktzahl erreichen.

abschließend

Dieses Mal lernte ich die intern verwendete Graphentheorie, insbesondere das Matching, basierend auf meiner eigenen App namens Supra Nervous Weakness.

Es ist aufregend zu sehen, wie Mathematik auf reale Probleme angewendet wird, nicht nur auf die Graphentheorie. Wenn ich tatsächlich vor einem Problem stehe, hätte ich gerne viele Schubladen mit der Frage "Ist dieser Algorithmus verwendbar?"

Bis zum Ende Danke fürs Lesen!