Finden Sie die minimale Abdeckung von einem Intervall mit subintervals

Angenommen ich habe ein Intervall (a,b), und eine Reihe von subintervals {(ai,bi)}i, deren union all (a,b). Gibt es einen effizienten Weg zu wählen, eine minimal-Kardinalität der Teilmenge dieser subintervals, die immer noch deckt (a,b)?

  • Sind Sie auf der Suche nach der kleinsten Anzahl von subintervals, oder die Menge der subintervals, die die wenigsten Elemente (und damit die wenigsten Duplikate)?
InformationsquelleAutor Alex Coventry | 2008-11-15
  1. 14

    Einen greedy-Algorithmus, beginnend bei a oder b immer die optimale Lösung.

    Beweis: betrachten Sie die Menge Sa alle subintervals abdecken. Klar, einer von Ihnen zu gehören, um die optimale Lösung zu finden. Wenn wir ersetzen Sie es mit ein subinterval (amax,bmax) aus den Sa, deren rechter Endpunkt bmax ist maximal in Sa (erreicht am weitesten rechts), die noch offenen Intervall (bmax,b) wird ein Teil des restlichen Intervalls von der optimalen Lösung, so kann es sein, bedeckt mit nicht mehr subintervals als die Analog aufgedeckt Intervall von der optimalen Lösung. Daher wird eine Lösung hergestellt aus (amax,bmax) und die optimale Lösung für die verbleibenden Intervall (bmax,b) wird auch optimal sein.

    Also, beginnen Sie einfach mit ein und iterativ wählen Sie das Intervall zu erreichen, die am weitesten rechts (und für den Ende des vorherigen Intervall), wiederholen Sie, bis Sie auf b. Ich glaube, dass die Auswahl der nächsten Pause kann man in log(n) wenn Sie speichern die Intervalle in einer augmented-Intervall-Baum.

    • Können Sie erläutern: "die noch offenen Intervall (bmax,b) wird ein Teil des restlichen Intervalls von der optimalen Lösung"?
    • Ich glaube, dass diese Lösung funktioniert, und es ist besser als meins.
    • Nehme an, dass die optimale Lösung beginnt mit einem Intervall (ai,bi), die umfasst (a,bi) und Blätter (bi,b) aufgedeckt. Aus der definition von (amax,bmax), die wir haben, bmax>=bi, so dass (bmax,b) eine Teilmenge (subinterval) von (bi,b).
    • "Wenn wir ersetzen Sie es mit ein subinterval (amax,bmax) von Sa...": meinst du die sub-Intervall (amin bmax)? Und ich bin mir nicht so sicher (bmax, b) entweder.
    • 'Max' ist nur ein index für das gesamte Intervall. Intervall 'foo' ist (a_foo,b_foo). (b_max,b) ist das Verbleibende Intervall.
    InformationsquelleAutor Rafał Dowgird
  2. 1

    Klingt wie dynamische Programmierung.

    Hier ist eine illustration des Algorithmus (vorausgesetzt die Intervalle sind in einer Liste, sortiert nach der Endzeit):

    //works backwards from the end
int minCard(int current, int must_end_after)
{
    if (current < 0)
        if (must_end_after == 0)
            return 0; //no more intervals needed
        else
            return infinity; //doesn't cover (a,b)

    if (intervals[current].end < must_end_after)
        return infinity; //doesn't cover (a,b)

    return min( 1 + minCard(current - 1, intervals[current].start),
                minCard(current - 1, must_end_after) );
           //include current interval or not?
}

    Aber es sollte auch um caching (memoisation).

    • minCard() soll eine minimale Kardinalität aber die Frage fragt nach einer Teilmenge mit minimaler Kardinalität.
    • Es wäre nur eine Erweiterung dieses Algorithmus, der verfolgt auch die Teilmenge wurde verwendet, um form, dass der optimale Wert.
    • Was ist die Komplexität Ihres Algorithmus ?
    • Die Komplexität ist O(n^2) im worst case. Zum Beispiel, wenn alle Intervalle haben eine identische Endpunkt, sondern verschiedenen start-Punkten, die alle diese Punkte start gehen zu propagieren, zurück an den Anfang. Der greedy-Ansatz ist besser.
    InformationsquelleAutor Artelius
  3. 0

    Gibt es zwei Fälle zu betrachten:
    Fall 1: Es gibt keine überschneidenden Intervallen nach der Endzeit eines Intervalls. In diesem Fall wählen Sie den nächsten Intervall mit der kleinsten Startzeit und die längste Bearbeitungszeit. (amin bmax).
    Fall 2: Es gibt 1 oder mehr über-Läppen Abständen mit dem letzten Intervall, die Sie suchen. In diesem Fall wird die Startzeit spielt keine Rolle, weil Sie bereits abgedeckt. So optimieren Sie für die Endzeit. (a, bmax).

    Fall 1 wählt immer das erste Intervall als das erste Intervall in der optimalen Menge als auch (der Beweis ist der gleiche wie das, was @RafalDowgrid zur Verfügung gestellt).

    InformationsquelleAutor user183037
  4. -2

    Du meinst also, dass die subintervals noch überschneiden sich in der Weise, dass (a,b) bleibt vollständig bedeckt ist, überhaupt Punkte?

    Vielleicht aufteilen, die subintervals sich in basic blocks zugeordnet, von wo Sie gekommen sind, so können Sie Liste mit Optionen für jeden basic block-Intervall-Buchhaltung für andere Regionen, die von der subinterval auch. Dann können Sie eine Suche auf Basis jedes sub-subinterval und zumindest sicher sein, keine Lücken gelassen werden.

    Dann würde suchen müssen.. effizient.. das würde schwieriger werden.

    Beseitigen könnte jeder Ansammlung von Intervallen, die vollständig abgedeckt durch einen anderen Satz von kleiner Anzahl und zu arbeiten, das problem nach der Vorverarbeitung.

    Wäre das nicht der minimal für das ganze minimal sein für mindestens die Hälfte? Ich bin mir nicht sicher.

    Gefunden link eine Zeitschrift, aber konnte es nicht Lesen. 🙁

    Wäre dies eine hitting set problem und NP_hard im Allgemeinen.

    Nicht Lesen konnte, diese beiden, aber sieht aus wie entgegengesetzte Art von problem.

    Konnte es nicht Lesen, aber eine andere link erwähnt das splitting Abständen.

    Hier ist ein verfügbaren Verweis auf Randomisierte Algorithmen für GeometricOptimization Probleme.

    Seite Fünf und dreißig dieses pdf hat ein greedy-Algorithmus.

    Seite 11 von Karp (1972) erwähnt hitting-set und zitiert eine Menge.

    Google Ergebnis. Die Erforschung war Spaß, aber ich muss jetzt gehen.

    InformationsquelleAutor waynecolvin
Schreibe einen Kommentar