Biorąc pod uwagę zestaw zakresów S i pokrywający się zakres R, znajdź najmniejszy podzbiór w S, który obejmuje R

Question

Poniżej znajduje się pytanie dotyczące ćwiczenia, które zostało mi udzielone przez kogoś, i nie jestem pewien, jakie najlepsze rozwiązanie do tego dochodzi:

Biorąc pod uwagę zestaw zakresów:
(np S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)} a biorąc pod uwagę zakres docelowy R (np R = (3, 13) - czyli zakres począwszy od 3 do 13) Napisz algorytm.. znajdź najmniejszy zestaw zakresów obejmujący zakres docelowy. Wszystkie zakresy w zestawie muszą się pokrywać, aby można je było uznać za obejmujące cały zakres docelowy. (W tym przykładzie, odpowiedź byłaby {(3, 9), (9, 12), (11, 14)}.

Jaki jest najlepszy sposób, aby rozwiązać ten problem? Myślałam byłoby to zrobić za pomocą algorytmu zachłannego. W naszym przykładzie powyżej, będziemy patrzeć na wszystko liczb, które przecinają się z 3, i wybieraj spośród tych, które mają najwyższą wartość maksymalną, a następnie zrobilibyśmy to samo z tym, którego właśnie wybieraliśmy, więc odkąd wybraliśmy (3, 9), teraz chcemy znaleźć wszystkie zakresy przecinają się 9, a spośród nich wybieramy ten, który ma najwyższą maks. W tej iteracji wybraliśmy (9, 12). Robimy to samo z tym i stwierdzamy, że następny zakres przecina 12 , z najwyższym maksimum wynosi (11, 14).Po tej iteracji widzimy, że 14 jest większe niż 13 (maksimum naszego zakresu), więc możemy się zatrzymać.

Problem z tym algorytmem polega na tym, jak efektywnie wyszukiwać zakresy przecinające się? Jeśli spróbujemy wyszukiwania liniowego, otrzymamy algorytm, który jest O(n^2). Moja następna myśl polegała na tym, by za każdym razem, gdy przechodzimy przez pętlę, wykreślać każdy z naszych przecinających się zakresów z naszej listy. Tak więc w pierwszej iteracji przechodzimy przez (1, 4) i (3, 9). W następnej iteracji przechodzimy przez: (9, 12), (3, 9) i (8, 10). Tak więc ostatnia iteracja, wszystko, co musimy przejrzeć, to: {(30, 40), (20, 91), (6, 7)}. Moglibyśmy uczynić to jeszcze bardziej efektywnym, również poprzez wykreślenie wszystkiego, co ma min> 13, i maks. < 3. Problem w tym, że to wciąż może nie wystarczyć. Nadal istnieje potencjalny problem polegający na posiadaniu dużej liczby zduplikowanych sekwencji w granicach naszego zakresu. Jeśli nasza lista zakresów zawierała coś w rodzaju {(6, 7), (6, 7), (6, 7), (6, 7), (6, 7)}, musielibyśmy przejrzeć te za każdym razem , chociaż nie są dla nas przydatne. Nawet gdybyśmy mieli przechowywać tylko unikalne wartości (umieszczając je wszystkie w zestawie), moglibyśmy mieć naprawdę duży zasięg, z szeregiem zakresów, które znajdują się w naszym zakresie docelowym, ale mamy również jeden zakres wewnątrz tego rozpiętości. cały zakres docelowy.

Jaki byłby skuteczny sposób zapytania naszych zakresów? A może, jaki byłby skuteczniejszy algorytm rozwiązania tego problemu?

Answer 1

Co powiesz na używanie drzewa interwałowego do zapytań? (https://en.m.wikipedia.org/wiki/Interval_tree) Nie jestem pewien, czy chciwi mogą tu pracować, czy nie.Jeśli spojrzymy na ostatni zestaw opcji, pokrywa się z wysokim punkcie R, istnieje możliwość nakładania się wcześniejszych wyborów dla każdego z nich, na przykład:

R = (2,10) and we have (8,10) and (7,10) both overlapping with (6,8) 

W takim przypadku musimy tylko zapisać jedną wartość dla (6,8) jako drugą nogę ścieżki; ponowne odwiedziny pod numerem (6,8), ponieważ wydłużamy ścieżki w kierunku niskiego punktu w R, będą zbyteczne, ponieważ wiemy już, że odwiedziliśmy (6,8) odwiedziliśmy z mniejszą liczbą nóg. Tak więc twój pomysł wyeliminowania interwałów w miarę upływu czasu ma sens. Czy coś takiego może działać?

leg = 1 
start with the possible end (or beginning) intervals 
label these intervals with leg 
until end of path is reached: 
    remove the intervals labeled leg from the tree 
    for each of those intervals labeled leg: 
    list overlapping intervals in the chosen direction 
    leg = leg + 1 
    label the listed overlapping intervals with leg 

Answer 2

Mogę zasugerować następujący algorytm o złożoności O(n log n) bez użycia drzew przedziałów.

Pozwolić wprowadzić trochę notacji. Powinniśmy pokrywać zakres (X,Y) według przedziałów czasowych (x_i,y_i).

Pierwszy sortowanie z podanymi interwałami (x_i,y_i) według punktu początkowego. To zajmie O(n log n)

Pozwolić wybrać z przerwami (x_i,y_i) z x_i <= X przedziale (x_k,y_k) z maksymalnie y_i. Ponieważ przedział już posortowany według punktu początkowego, możemy po prostu zwiększyć indeks, a przedział spełnia warunek. Jeśli y_k mniej niż X, nie ma rozwiązania dla danego zestawu i zakresu. W innym przypadku interwał (x_k,y_k) zawiera "X" i ma maksymalny punkt końcowy między interwałami zawierającymi X.

Teraz musimy pokryć przedział (y_k, Y), aby spełnić warunek zachodzenia na siebie. Ponieważ dla wszystkich przedziałów zawierających X ma punkt końcowy mniejszy niż y_k+1, możemy rozpocząć od ostatniego przedziału od poprzedniego kroku.

Każdy interwał został użyty tylko raz na tym etapie, więc złożoność czasowa tej części to O(n) iw sumie O(n log n).

Po fragment kodu do sporządzania roztworu:

intervals // given intervals from set S 
(X, Y) // range to cover 
sort intervals 
i = 0 // start index 
start = X // start point 
result_set // set to store result 
while start <= Y && i < len(intervals): 
    next_start = intervals[i].y 
    to_add = intervals[i] 
    while intervals[i].x <= start && i < len(intervals): 
     if next_start > intervals[i].y: 
      next_start = intervals[i].y 
      to_add = intervals[i] 
     i++ 
    if(next_start < start): 
     print 'No solution' 
     exit 
    start = next_start 
    result_set add to_add 

Answer 3

Twoje zadanie intryguje mnie, więc napisałem program w C++, który rozwiązuje ten problem przez iteracja zakresach, które pokrywają się z lewej strony zakresu docelowego i rekurencyjnie przeszukuje dla najmniejszej liczby zakresów, która obejmuje pozostałą (prawą stronę) zakresu docelowego.

Istotną optymalizacją tego algorytmu (nie pokazanego w tym programie) byłoby, aby dla każdego poziomu rekursywnego użyć zakresu pokrywającego się po lewej stronie zakresu docelowego o największą wartość i odrzucając od dalszego rozważenia wszystkie zakresy które nakładają się na lewą stronę mniejszymi kwotami. Korzystając z tej reguły, uważam, że byłoby najwyżej pojedyncze zejście do rekurencyjnego drzewa wywołań. Taka optymalizacja wytworzyłaby algorytm o złożoności O (n log (n)). (n do uwzględnienia głębokości rekursji i log (n) do uwzględnienia wyszukiwania binarnego w celu znalezienia zakresu, który najbardziej pokrywa się.)

Ten program produkuje następujące jako wyjście:

{ (3, 9) (9, 12) (11, 14) } 

Oto program:

#include <utility> // for std::pair 
#include <vector> // for std::vector 
#include <iostream> // for std::cout & std::endl 

typedef std::pair<int, int> range; 
typedef std::vector<range> rangelist; 

// function declarations 
rangelist findRanges (range targetRange, rangelist candidateRanges); 
void print (rangelist list); 


int main() 
{ 
    range target_range = { 3, 13 }; 

    rangelist candidate_ranges = 
     { { 1, 4 }, { 30, 40 }, { 20, 91 }, { 8, 10 }, { 6, 7 }, { 3, 9 }, { 9, 12 }, { 11, 14 } }; 

    rangelist result = findRanges (target_range, candidate_ranges); 

    print (result); 
    return 0; 
} 


// Recursive function that returns the smallest subset of candidateRanges that 
// covers the given targetRange. 
// If there is no subset that covers the targetRange, then this function 
// returns an empty rangelist. 
// 
rangelist findRanges (range targetRange, rangelist candidateRanges) 
{ 
    rangelist::iterator it; 
    rangelist smallest_list_so_far; 

    for (it = candidateRanges.begin(); it != candidateRanges.end(); ++it) { 

     // if this candidate range overlaps the beginning of the target range 
     if (it->first <= targetRange.first && it->second >= targetRange.first) { 

      // if this candidate range also overlaps the end of the target range 
      if (it->second >= targetRange.second) { 

       // done with this level - return a list of ranges consisting only of 
       // this single candidate range 
       return { *it }; 
      } 
      else { 
       // prepare new version of targetRange that excludes the subrange 
       // overlapped by the present range 
       range newTargetRange = { it->second + 1, targetRange.second }; 

       // prepare new version of candidateRanges that excludes the present range 
       // from the list of ranges 
       rangelist newCandidateRanges; 
       rangelist::iterator it2; 
       // copy all ranges up to but not including the present range 
       for (it2 = candidateRanges.begin(); it2 != it; ++it2) { 
        newCandidateRanges.push_back (*it2); 
       } 
       // skip the present range 
       it2++; 
       // copy the remainder of ranges in the list 
       for (; it2 != candidateRanges.end(); ++it2) { 
         newCandidateRanges.push_back (*it2); 
       } 

       // recursive call to find the smallest list of ranges that cover the remainder 
       // of the target range not covered by the present range 
       rangelist subList = findRanges (newTargetRange, newCandidateRanges); 

       if (subList.size() == 0) { 
        // no solution includes the present range 
        continue; 
       } 
       else if (smallest_list_so_far.size() == 0 ||    // - first subList that covers the remainder of the target range 
         subList.size() < smallest_list_so_far.size()) // - this subList is smaller than all previous ones checked 
       { 
        // add the present range to the subList, which represents a solution 
        // (though possibly not optimal yet) at the present level of recursion 
        subList.push_back (*it); 
        smallest_list_so_far = subList; 
       } 
      } 
     } 
    } 
    return smallest_list_so_far; 
} 

// print list of ranges 
void print (rangelist list) 
{ 
    rangelist::reverse_iterator rit; 
    std::cout << "{ "; 
    for (rit = list.rbegin(); rit != list.rend(); ++rit) { 
     std::cout << "(" << rit->first << ", " << rit->second << ") "; 
    } 
    std::cout << "}" << std::endl; 
} 

Answer 4

Ok, po wypróbowaniu kilka różnych rzeczy, tu jest moje rozwiązanie. Działa w czasie i nie wymaga użycia drzewa interwałów (chociaż prawdopodobnie bym go użył, gdybym mógł zapamiętać, jak go wdrożyć na rozmowę kwalifikacyjną, ale myślę, że zajęłoby to zbyt dużo czasu bez dostarczenia zasiłek).

Węzeł tego algorytmu polega na sortowaniu. Każdy przedmiot jest tylko raz dotykany, ale działa tylko z posortowaną tablicą, więc to jest pierwsza rzecz, którą robimy. Tak więc złożoność czasu. Ponieważ modyfikuje on oryginalną tablicę, ma on złożoność przestrzeni, ale jeśli nie wolno nam modyfikować oryginalnej tablicy, możemy po prostu zrobić jej kopię i zachować resztę algorytmu tak samo, tworząc przestrzeń złożoność O(n).

import java.util.*; 

class SmallestRangingSet { 
    static class Interval implements Comparable<Interval>{ 
     Integer min; 
     Integer max; 
     public Interval(int min, int max) { 
      this.min = min; 
      this.max = max; 
     } 

     boolean intersects(int num) { 
      return (min <= num && max >= num); 
     } 

     //Overrides the compareTo method so it will be sorted 
     //in order relative to the min value 
     @Override 
     public int compareTo(Interval obj) { 
      if (min > obj.min) return 1; 
      else if (min < obj.min) return -1; 
      else return 0; 
     } 
    } 

    public static Set<Interval> smallestIntervalSet(Interval[] set, Interval target) { 
     //Bottleneck is here. The array is sorted, giving this algorithm O(nlogn) time 
     Arrays.sort(set); 

     //Create a set to store our ranges in 
     Set<Interval> smallSet = new HashSet<Interval>(); 
     //Create a variable to keep track of the most optimal range, relative 
     //to the range before it, at all times. 
     Interval bestOfCurr = null; 
     //Keep track of the specific number that any given range will need to 
     //intersect with. Initialize it to the target-min-value. 
     int currBestNum = target.min; 
     //Go through each element in our sorted array. 
     for (int i = 0; i < set.length; i++) { 
      Interval currInterval = set[i]; 
      //If we have already passed our target max, break. 
      if (currBestNum >= target.max) 
       break; 
      //Otherwise, if the current interval intersects with 
      //our currBestNum 
      if (currInterval.intersects(currBestNum)) { 
       //If the current interval, which intersects currBestNum 
       //has a greater max, then our current bestOfCurr 
       //Update bestOfCurr to be equal to currInterval. 
       if (bestOfCurr == null || currInterval.max >= bestOfCurr.max) { 
        bestOfCurr = currInterval; 
       } 
      } 
      //If our range does not intersect, we can assume that the most recently 
      //updated bestOfCurr is probably the most optimal new range to add to 
      //our set. However, if bestOfCurr is null, it means it was never updated, 
      //because there is a gap somewhere when trying to fill our target range. 
      //So we must check for null first. 
      else if (bestOfCurr != null) { 
       //If it's not null, add bestOfCurr to our set 
       smallSet.add(bestOfCurr); 
       //Update currBestNum to look for intervals that 
       //intersect with bestOfCurr.max 
       currBestNum = bestOfCurr.max; 
       //This line is here because without it, it actually skips over 
       //the next Interval, which is problematic if your sorted array 
       //has two optimal Intervals next to eachother. 
       i--; 
       //set bestOfCurr to null, so that it won't run 
       //this section of code twice on the same Interval. 
       bestOfCurr = null; 
      } 

     } 

     //Now we should just make sure that we have in fact covered the entire 
     //target range. If we haven't, then we are going to return an empty list. 
     if (currBestNum < target.max) 
      smallSet.clear(); 
     return smallSet; 
    } 

    public static void main(String[] args) { 
     //{(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)} 
     Interval[] interv = { 
       new Interval(1, 4), 
       new Interval(30, 40), 
       new Interval(20, 91), 
       new Interval(8, 10), 
       new Interval(6, 7), 
       new Interval(3, 9), 
       new Interval(9, 12), 
       new Interval(11, 14) 
     }; 
     Set<Interval> newSet = smallestIntervalSet(interv, new Interval(3,14)); 
     for (Interval intrv : newSet) { 
      System.out.print("(" + intrv.min + ", " + intrv.max + ") "); 
     } 

    } 
} 

wyjściowy

(3, 9) (9, 12) (11, 14)