Angenommen, ich habe ein Intervall (a, b) und eine Anzahl von Subintervallen {(a i , b i )} i wessen Vereinigung ist alles von (a, b). Gibt es eine effiziente Möglichkeit, eine Teilmenge mit minimaler Kardinalität dieser Teilintervalle zu wählen, die immer noch (a, b) umfasst?
Ein gieriger Algorithmus, der bei a oder b beginnt, liefert immer die optimale Lösung.
Beweis: Betrachte die Menge S a aller Subintervalle, die a abdecken. Natürlich muss einer von ihnen zur optimalen Lösung gehören. Wenn wir es durch ein Subintervall (a max , b max ) von S ersetzen, dessen rechter Endpunkt b
Beginnen Sie also bei a und wählen Sie iterativ das Intervall, das am weitesten rechts liegt (und das Ende des vorherigen Intervalls abdeckt), wiederholen Sie, bis Sie auf b drücken. Ich glaube, dass das Auswählen des nächsten Intervalls in Protokoll (n) erfolgen kann, wenn Sie die Intervalle in einem erweiterten Intervallbaum speichern.
Es gibt zwei Fälle zu beachten: Fall 1: Es gibt keine überlappenden Intervalle nach der Zielzeit eines Intervalls. Wählen Sie in diesem Fall das nächste Intervall mit der kürzesten Startzeit und der längsten Endzeit. (Amin, Bmax). Fall 2: Es gibt 1 oder mehr Überlappungsintervalle mit dem letzten Intervall, das Sie betrachten. In diesem Fall spielt die Startzeit keine Rolle, da Sie dies bereits abgedeckt haben. So optimieren Sie die Endzeit. (a, bmax).
Fall 1 wählt immer auch das erste Intervall als das erste Intervall in der optimalen Menge aus (der Beweis ist der gleiche wie der von @RafalDowgrid bereitgestellte).
Sie meinen, dass sich die Subintervalle immer noch so überlappen, dass (a, b) an allen Punkten vollständig bedeckt bleibt?
Vielleicht teilen Sie die Subintervalle selbst in Basisblöcke auf, die mit ihrer Herkunft in Zusammenhang stehen, so dass Sie Optionen für jedes Basisblockintervall auflisten können, die auch für andere Regionen gelten, die vom Subintervall abgedeckt werden. Dann können Sie eine Suche basierend auf jedem Sub-Subintervall verwenden und zumindest sicher sein, dass keine Lücken übrig sind.
Dann müsste man ... effizient suchen .. das wäre härter.
Kann jede Sammlung von Intervallen eliminieren, die vollständig von einem anderen Satz kleinerer Nummern abgedeckt sind, und das Problem nach der Vorverarbeitung beheben.
Wäre nicht das Minimum für das Ganze minimal für mindestens die Hälfte? Ich bin mir nicht sicher.
Gefunden ein Treffermenge und allgemein NP_hard.
Konnte dieses nicht lesen, sieht aber wie ein umgekehrtes Problem aus.
Konnte es nicht lesen, aber ein weiterer Link , der die Aufteilungsintervalle angibt.
Hier ist eine verfügbare Referenz auf Randomized Algorithmen für GeometricOptimization Probleme.
Seite 35 dieser pdf hat einen Greedy-Algorithmus.
Seite 11 von Karp (1972) erwähnt das Schlag-Set und wird viel zitiert.
Google result . Recherchieren hat Spaß gemacht, aber ich muss jetzt gehen.
Tags und Links algorithm optimization math geometry