P vs NP: Ein lehrreiches Beispiel dafür, wann eine Brute-Force-Suche vermieden werden kann

Um Nicht-Mathematikern das P vs NP-Problem erklären zu können, hätte ich gerne ein pädagogisches Beispiel dafür, wann eine Brute-Force-Suche vermieden werden kann. Das Problem sollte im Idealfall sofort verständlich sein und der Trick sollte weder zu einfach noch zu schwer sein.

Das Beste, was ich mir bisher ausgedacht habe, ist

SUBSET_PRODUCT_IS_ZERO

Das Problem ist leicht zu verstehen (kann bei einer Menge von ganzen Zahlen eine Teilmenge mit Produkt 0 gebildet werden?), Aber der Trick ist zu einfach (prüfen Sie, ob 0 unter den angegebenen Zahlen ist, dh es ist nicht erforderlich, viele zu betrachten Teilmengen).

Irgendwelche Vorschläge?

Ich empfehle Jenga !

Angenommen, Sie haben zwei vollkommen logische, nüchterne und geschickte Spieler, dann ist Jenga ein Zwei-Spieler-Spiel mit perfekten Informationen, genau wie Checkers oder Go. Angenommen, das Spiel beginnt mit einem Stapel von Steinen mit 3 Steinen in jedem Level. Während des größten Teils des Spiels hat jeder Spieler in jeder Runde -Wahlen für den nächsten Zug, und wenn keine dummen Fehler vorliegen, liegt die Anzahl der Runden immer zwischen und . So grob hat der Spielbaum Zustände. Wenn Sie den Spielbaum mit brutaler Gewalt erkundet haben, verbringen Sie möglicherweise exponentielle Zeit damit, einen Gewinnzug zu finden oder sich selbst davon zu überzeugen, dass Sie nicht gewinnen können.Θ ( N ) N 6 N N Θ ( N $3N$$\Theta(N)$$N$$6N$$N^{\Theta(N)}$

Tatsächlich hat Uri Zwick im Jahr 2005 bewiesen, dass Sie Jenga perfekt spielen können, indem Sie nur drei ganze Zahlen verfolgen und dabei einfache Regeln verwenden, die Sie problemlos auf eine Visitenkarte setzen können. Die drei Zahlen, die Sie brauchen, sind

• $m =$ die Anzahl der Ebenen (ohne die oberste Ebene) mit drei Steinen.
• $n =$ die Anzahl der Ebenen (ohne die oberste Ebene) mit zwei Steinen nebeneinander.
• $t =$ Anzahl der Steine ​​in der obersten Ebene (0, 1, 2 oder 3).

Tatsächlich müssen Sie sich die meiste Zeit nur an und anstelle von und erinnern . Hier ist die komplette Gewinnstrategie:$n\bmod 3$$m\bmod 3$$n$$m$

Hier bedeutet II, dass Sie den mittleren Stein von einer beliebigen 3-Schicht nach oben verschieben sollten. II- bedeutet, dass Sie einen Seitenstein von einer 3-Schicht nach oben verschieben sollten. -I- bedeutet, dass Sie einen Seitenstein von einer 2-Schicht verschieben sollten nach oben, und das Bob-Omb bedeutet, dass Sie über den Tod nachdenken und traurig werden sollten . Wenn in einer Box mehr als ein Zug vorgeschlagen wird, können Sie einen beliebigen auswählen. Es ist trivial, diese Strategie in -Zeit auszuführen, wenn Sie das Tripel bereits kennen , oder in -Zeit, wenn Sie dies nicht tun.$O(1)$$(m,n,t)$$O(N)$

Moral: Jenga macht nur Spaß, wenn alle ungeschickt und / oder betrunken sind.

Ein Kassierer muss einem Kunden Cent Wechselgeld zurückgeben. Kann sie es angesichts der verfügbaren Münzen tun und wie?$x$

• Brute Force: Betrachten Sie alle möglichen Sammlungen von Münzen und prüfen Sie, ob eine davon .$x$
• Non-Brute Force: Machen Sie es wie jeder Kassierer durch dynamische Programmierung.

Es gibt zwei Varianten des Problems:

1. Einfach : Der Kassierer hat unbegrenzten Vorrat an allen Stückelungen.
2. Schwieriger: Der Kassierer hat einen begrenzten Vorrat an Münzen.

Die einfache Variante kann mit einem gierigen Algorithmus gelöst werden. Das Schwierigere erfordert eine dynamische Programmierung.

Der Weg, dies zu präsentieren, besteht darin, die Brute-Force-Lösung vorzuschlagen, die Leute zu verstehen, dass sie sehr ineffizient ist, und sie dann zu fragen, was Kassierer tun, zuerst für die einfache Variante, dann für die schwierige. Sie sollten einige Beispiele zur Verfügung haben, die von leicht bis böse gehen.

Ich denke, ich habe selbst ein nützliches Beispiel gefunden!

Vielleicht war ich etwas vage, aber ich suchte nach einem Problem, das die folgenden Spezifikationen erfüllte:

• Das Problem selbst sollte für jemanden, der Sozialwissenschaften studiert, leicht zu erklären sein.
• Es sollte einen offensichtlichen, aber ineffektiven Algorithmus haben.
• Es sollte einen besseren Algorithmus haben, der auch für jemanden, der Sozialwissenschaften studiert, leicht zu erklären ist.

Für den Eulerschen Zyklus ist es leicht zu erklären, dass es eine notwendige Bedingung ist, dass jeder Knoten einen gleichmäßigen Grad haben muss, aber es ist nicht so einfach zu erklären, warum dies eine ausreichende Bedingung ist.

Dies ist das Problem, von dem ich denke, dass es die oben genannte Spezifikation am besten erfüllt:

FORM_TARGET_SET_WITH_UNIONS

Sammlung von Mengen$C=\{S_1, S_2,...,S_n\}$

Zielmenge$T$

Frage: Ist es möglich, die Zielmenge zu bilden, indem einige der Mengen in ?$T$$C$

Offensichtlicher, aber ineffektiver Algorithmus:

• Bilden Sie alle möglichen Gewerkschaften$2^n$
• Überprüfen Sie, ob einer von ihnen$T$

Besserer Algorithmus

• Markieren Sie die Mengen in , die in$C$$T$
• Bilden Sie die Vereinigung dieser Mengen$S_{_\cup}$
• Wennantworte mit , sonst mit$|S_{_\cup}|=|T|$$YES$$NO$

Es gibt auch das Schwesterproblem

FORM_TARGET_SET_WITH_INTERSECTIONS

für die der bessere Algorithmus ist

• Markieren Sie die Mengen in , die enthalten$C$$T$
• Bilden Sie den Schnittpunkt dieser Mengen$S_{_\cap}$
• Wennantworte mit , sonst mit$|S_{_\cap}|=|T|$$YES$$NO$

Wie Sie sehen, habe ich nach etwas wirklich Einfachem gesucht (fast so einfach wie SUBSET_PRODUCT_IS_ZERO).

Das Problem kann auch mit SUBSET SUM und SUBSET PRODUCT verglichen werden, die NP-vollständig sind, aber in ihrer Formulierung ähnlich sind. Bei all diesen Problemen wird eine Sammlung von Objekten angezeigt und gefragt, ob eine Operation an einer Auswahl dieser Objekte zu einem gewünschten Ergebnis führen kann.