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

8

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?

Sixpanbass
quelle
Möchten Sie einen Algorithmus, der besser als Bruteforce ist, für ein NP-vollständiges Problem oder für ein dummes Problem wie Subset-Produkt-ist-0? Wie wäre es mit dem Trick, der für die Teilmengen-Summe ausführt, siehe z. B. den Horowitz- und Sahni-Algorithmus hier rjlipton.wordpress.com/2010/02/05/…2n/2+o(n)
Sasho Nikolov
Vielleicht habe ich die Frage nicht gut verstanden, aber wenn Sie ein leicht verständliches Problem in P mit einem Polynomzeitalgorithmus "mittlerer Ebene" benötigen, dann schlage ich die klassische 2-CNF-Erfüllbarkeit vor .
Marzio De Biasi
4
Wie wäre es mit 2-Farben vs 3-Farben?
Serge Gaspers
6
Die Art und Weise, wie diese Frage geschrieben wird, scheint vorauszusetzen, dass NP-vollständige Probleme nur durch Brute-Force-Suche gelöst werden können. Das wäre ein Fehler. Zum Beispiel benötigt die naive Brute-Force-Suche nach dem Problem des Handlungsreisenden Zeit, während sie durch einen dynamischen Programmieralgorithmus ohne Brute-Force in der viel schnelleren zeitgebundenen gelöst werden kann . O ( n 2 2 n )O(n!)O(n22n)
David Eppstein

Antworten:

22

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Θ(N)N6NNΘ(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:nmod3mmod3nm

Geben Sie hier die Bildbeschreibung ein

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.

Jeffε
quelle
Das ist ein ausgezeichnetes Lehrbeispiel, aber ich hätte die +1 nur für die Pilgerreferenz gegeben.
Luke Mathieson
10

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.

Andrej Bauer
quelle
1

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 MengenC={S1,S2,...,Sn}

ZielmengeT

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

Offensichtlicher, aber ineffektiver Algorithmus:

  • Bilden Sie alle möglichen Gewerkschaften2n
  • Überprüfen Sie, ob einer von ihnenT

Besserer Algorithmus

  • Markieren Sie die Mengen in , die inCT
  • Bilden Sie die Vereinigung dieser MengenS
  • Wennantworte mit , sonst mit|S|=|T|YESNO

Es gibt auch das Schwesterproblem

FORM_TARGET_SET_WITH_INTERSECTIONS

für die der bessere Algorithmus ist

  • Markieren Sie die Mengen in , die enthaltenCT
  • Bilden Sie den Schnittpunkt dieser MengenS
  • Wennantworte mit , sonst mit|S|=|T|YESNO

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.

Sixpanbass
quelle
1
Andere solche Probleme sind Primalität , Horn-SAT und maximale Übereinstimmung .