Punkt abdeckt Problem

Question

I kürzlich dieses Problem auf einem Test hat: Bei einem gegebenen Satz von Punkten m (alle auf der x-Achse) und einen Satz n von Linien mit Endpunkten [l, r] (wieder auf der x-Achse), finden Sie die minimale Teilmenge von n so, dass alle Punkte durch eine Linie abgedeckt sind. Beweisen Sie, dass Ihre Lösung immer die minimale Teilmenge findet.

Der Algorithmus, den ich für sie schrieb, war etwas in der Art von: (zB Linien als Arrays mit der linken Endpunkt in Position 0 und der rechten Seite in Position gespeichert sind 1)

algorithm coverPoints(set[] m, set[][] n): 
    chosenLines = [] 
    while m is not empty: 
     minX = min(m) 
     bestLine = n[0] 
     for i=1 to length of n: 
      if n[i][0] <= minX and n[i][1] > bestLine[1] then 
       bestLine = n[i] 
     add bestLine to chosenLines 
     for i=0 to length of m: 
      if m[i] <= bestLine[1] then delete m[i] from m 
    return chosenLines 

Ich bin einfach nicht sicher, ob dies immer die minimale Lösung findet. Es ist ein einfacher Greedy-Algorithmus, also sagt mir mein Bauchgefühl, dass es nicht geht, aber einer meiner Freunde, der viel besser ist als ich, sagt, dass ein gieriger Algorithmus für dieses Problem immer die minimale Lösung findet. Um zu beweisen, dass meins immer die minimale Lösung findet, habe ich eine sehr handbewaffnete Beweisführung durch Widerspruch gemacht, wo ich eine Vermutung gemacht habe, die wahrscheinlich überhaupt nicht wahr ist. Ich vergesse genau, was ich getan habe.

Wenn dies keine minimale Lösung ist, gibt es einen Weg, es in weniger als O (n!) Zeit zu tun?

Dank

Answer 1

Ihr Greedy-Algorithmus IS korrekt. Wir können dies beweisen, indem wir zeigen, dass JEDE andere Deckung nur verbessert werden kann, indem Sie sie durch die Abdeckung ersetzen, die von Ihrem Algorithmus erzeugt wurde.

Sei C eine gültige Überdeckung für eine gegebene Eingabe (nicht unbedingt eine optimale), und sei S die Überdeckung nach deinem Algorithmus. Lassen Sie uns jetzt die Punkte p1, p2, ... pk untersuchen, die die Min-Punkte darstellen, mit denen Sie in jedem Iterationsschritt umgehen. Die Abdeckung C muss sie alle ebenfalls abdecken. Beachten Sie, dass es in C kein Segment gibt, das zwei dieser Punkte abdeckt; andernfalls hätte Ihr Algorithmus dieses Segment gewählt! Daher gilt | C |> = k. Und wie hoch sind die Kosten (Segmente) in Ihrem Algorithmus? | S | = k.

Das vervollständigt den Beweis.

Zwei Anmerkungen:

1) Umsetzung: Initialisierung BestLine mit n [0] ist falsch, da die Schleife um es zu verbessern nicht in der Lage sein kann, und n [0] nicht unbedingt minX decken.

2) Eigentlich ist dieses Problem eine vereinfachte Version des Problems Set Cover. Während das Original NP-vollständig ist, ergibt sich diese Variation als Polynom.

Answer 2

Hinweis: versuchen Sie zuerst Algorithmus für die Sätze von Größe funktioniert beweist 0, 1, 2 ... und sehen, ob Sie diese verallgemeinern kann einen Beweis durch Induktion zu erstellen.