Optimale Lösung für die nicht überlappenden Sequenzen maximaler scoring

Question

Während ein Teil eines Simulators Entwicklung ich über das folgende Problem kam. Betrachten Sie eine Zeichenfolge der Länge N und M Teil dieser Saite mit einer nicht-negativ zu jedem von ihnen zugewiesen Punktzahl. Von besonderem Interesse sind die Sätze von Teil, die folgenden Anforderungen erfüllen:

1. Sie nicht überlappen.
2. Ihre Gesamtwertung (nach Summe, der Einfachheit halber) maximal ist.
3. Sie erstrecken sich über die gesamte Zeichenfolge.

Ich verstehe die naive Brute-Force-Lösung von O (M * N ^ 2) Komplexität ist. Während die Durchführung dieses Algorithmus würde wahrscheinlich nicht viel über die Leistung des gesamten Projektes verhängen (nirgendwo in der Nähe des kritischen Pfades kann vorberechnet usw. sein), nicht sitzt es wirklich nicht gut mit mir. Ich würde gerne wissen, ob es bessere Lösungen für dieses Problem sind, und wenn ja, welche sind das? Zeiger auf einen entsprechenden Code sind immer willkommen, aber nur Algorithmus Beschreibung wird auch tun.

Answer 1

Das kann man sich vorstellen als den längsten Weg durch eine DAG zu finden. Jede Position in dem String ist ein Knoten, und jedes Teilzeichen Spiel eine Kante. Sie können Induktions trivially beweisen, dass für jede durch die Knoten auf dem optimalen Weg die Verkettung des optimalen Weges von Anfang an diesen Knoten und von dem Knoten zu dem Ende das gleiche wie der optimalen Weg ist. Dank, dass Sie nur den Überblick über die optimalen Wege für jeden Knoten halten und stellen Sie sicher, dass Sie alle Kanten besucht haben, die in einem Knoten beenden, bevor Sie Pfade zu prüfen, die es enthalten starten.

Dann müssen Sie nur noch das Problem alle Kanten finden, die von einem Knoten zu starten, oder all das Spiel an einer bestimmten Position String. Wenn Sie bereits wissen, wo die Teilzeichenübereinstimmungen gibt, dann ist es so trivial, wie eine Hash-Tabelle zu bauen. Wenn Sie dies nicht tun können Sie immer noch eine Hash-Tabelle erstellen, wenn Sie Rabin-Karp .

Beachten Sie, dass dies mit Ihnen noch in der DAG alle Kanten für O (e) Komplexität besuchen werden. Oder mit anderen Worten, Sie einmal in jede Teilkette Spiel betrachten müssen, die in einer Folge von verbundenem Teil von Anfang bis zum Ende möglich ist. Sie könnten besser als diese durch die Vorverarbeitung des Teils tun Wege zu finden, einige Spiele auszuschließen. Ich habe meine Zweifel, ob irgendwelche allgemeinen Fall Komplexität Verbesserungen für diese kommen und alle praktischen Verbesserungen hängen stark von Ihrer Datenverteilung.

Answer 2

Es ist nicht klar, ob M Teil als Sequenzen von Zeichen oder Indices in der Eingabezeichenfolge angegeben werden, aber das Problem dadurch nicht viel ändern.

Lassen Sie uns Eingabe-String S der Länge N haben, und M Eingabezeichenfolgen Tj. Lassen Sie Lj die Länge von Tj sein, und Pj - Partitur für Streich Sj gegeben. Wir sagen, dass Zeichenfolge

Das heißt Dynamische Programmierung oder DP. Sie halten eine Array res von Ints der Länge N, wobei das i-te Element die Punktzahl ist kann man bekommen, wenn er nur den Teil aus dem i-ten Elemente ausgehend hat (zum Beispiel, wenn der Eingang „ABCD“ ist, dann res [ 2] stellen die beste Note, die Sie von „cd“ bekommen).

Dann iterieren Sie durch diese Anordnung von einem Ende zum Anfang, und prüfen Sie, ob Sie String Sj aus den i-ten Zeichen beginnen. Wenn Sie können, dann führen von (res [i + Lj] + Pj) ist eindeutig erreichbar. Iterieren über alle Sj, res [i] = max (res [i + Lj] + Pj) für alle Sj, die dem i-ten Zeichen angewendet werden kann.

res [0] wird Ihre endgültige asnwer sein.

Answer 3

Eingänge:

N, the number of chars in a string
e[0..N-1]: (b,c) an element of set e[a] means [a,b) is a substring with score c.  

(Wenn alle Teile möglich sind, dann könnten Sie einfach c haben (a, b).)

Mit dem z.B. [1,2) verstehen wir den Teil der zweiten Buchstaben des Strings Belag (halb offen Intervall).

(leer Teil sind nicht erlaubt, wenn sie waren, dann könnte man sie richtig behandeln nur, wenn Sie es ihnen ermöglichen, „genommen“ höchstens k mal werden)

Ausgänge:

s[i] is the score of the best substring covering of [0,i)
a[i]: [a[i],i) is the last substring used to cover [0,i); else NULL

Algorithm - O (N ^ 2), wenn die Intervalle nicht sparse e sind; O (N + E), wobei E die Gesamtzahl der Intervalle erlaubt ist. Dies wird effektiv den besten Weg durch einen azyklischen Graphen zu finden:

for i = 0 to N:
    a[i] <- NULL
    s[i] <- 0
a[0] <- 0
for i = 0 to N-1
    if a[i] != NULL
        for (b,c) in e[i]:
            sib <- s[i]+c
            if sib>s[b]:
                a[b] <- i
                s[b] <- sib

die beste Abdeckung verdreifacht, um (a, b, c), wo die Kosten von [a, b) ist c:

i <- N
if (a[i]==NULL):
    error "no covering"
while (a[i]!=0):
    from <- a[i]
    yield (from,i,s[i]-s[from]
    i <- from

Natürlich könnte man das Paar speichern (sib, c) in s [b] und die Subtraktion speichern.

Answer 4

O (N + M) Lösung:

Set f[1..N]=-1
Set f[0]=0
for a = 0 to N-1
    if f[a] >= 0
        For each substring beginning at a
            Let b be the last index of the substring, and c its score
            If f[a]+c > f[b+1]
                Set f[b+1] = f[a]+c
                Set g[b+1] = [substring number]
Now f[N] contains the answer, or -1 if no set of substrings spans the string.
To get the substrings:
b = N
while b > 0
    Get substring number from g[N]
    Output substring number
    b = b - (length of substring)