Ich habe kürzlich von der gierigen Vermutung für das kürzeste Superstring-Problem erfahren .
In diesem Problem erhalten wir eine Menge von Strings und wollen den kürzesten Superstring dh so, dass jeder als ein Teilstring von .
Dieses Problem ist NP-hart und nach einer langen Abfolge von Arbeiten hat der bekannteste Näherungsalgorithmus für dieses Problem ein Verhältnis von [Paluch '14].
In der Praxis verwenden Biologen den folgenden Greedy-Algorithmus:
Führen Sie bei jedem Schritt zwei Zeichenfolgen zusammen, die sich über alle Paare maximal überlappen (das maximale Suffix, das dem Präfix einer anderen Zeichenfolge entspricht), und wiederholen Sie diese neue Instanz, bis nur noch eine Zeichenfolge übrig ist (die eine Superzeichenfolge aller Eingabezeichenfolgen ist) )
Eine untere Grenze von im Näherungsverhältnis dieses Greedy-Algorithmus kann aus der Eingabe .
Interessanterweise wurde vermutet, dass dies das schlechteste Beispiel ist, dh, dass Greedy eine Approximation für das kürzeste Superstring-Problem erreicht. Ich war sehr überrascht zu sehen, dass ein so natürlicher und einfacher Algorithmus so schwer zu analysieren ist.
Gibt es irgendwelche Anschauungen, Fakten, Beobachtungen, Beispiele, die nahelegen, warum diese Frage so herausfordernd ist?
quelle
Antworten:
Lassen Sie mich zunächst zusammenfassen, was über die Gierige Vermutung bekannt ist.
Ich denke, einer der Gründe, warum es schwierig ist, die gierige Vermutung zu beweisen, könnte folgender sein. Die meisten Ansätze zum Nachweisen von Approximationsgarantien des Greedy-Algorithmus analysieren den Überlappungsgraphen (oder äquivalent den Präfixgraphen) des Eingabesatzes von Zeichenfolgen. Wir kennen nur einige Eigenschaften dieser Graphen (wie Monge- und Triple-Ungleichungen), aber diese Eigenschaften reichen nachweislich nicht aus, um die Gierige Vermutung zu beweisen ( Weinard, Schnitger ; Laube, Weinard ).
quelle