Bună ziua. Un student boboc la Universitatea Academic citește algoritmii rata anuală. Fiecare curs este urmat de un workshop in care am analizat sarcinile algoritmice. Atelierele sunt organizate în grupuri mici. Acest semestru am prelegere și conduc o practică în grupuri.
Astăzi vreau să împărtășesc cu voi două probleme cu aceste seminarii.
Problema 1. Pe linia sunt date n segmente, trebuie să selectați dimensiunea maximă a disjuncte subset.
Problema 2. Pe arce de cerc sunt n (linii), este necesar pentru a selecta dimensiunea maximă subsetul disjuncte.
Prima sarcină - unul dintre exemple privind „lacomi“. Soluția poate fi vizualizată mai jos. Pe scurt, se presupune decizie pentru O (sort + n) de sortare. Aici am apel pentru un timp de sortare de sortare o serie de lungime n. De altfel, sort - opțional nlogn (de exemplu, sortare găleată, sortare radix, datele de intrare de la un domeniu limitat).
A doua problemă are o soluție pentru O probabilitate frumoasă (sort + n). In ciuda asemanarii sale cu prima, a doua sarcină, în lăcomia frunte nu poate fi rezolvată. Sau, mai degrabă eu nu știu soluție personal lacom, dacă oricare dintre cititorii vor veni și împărtăși, voi fi bucuros să aud. Și așa a fost mai ușor să se gândească, am descrie doar cateva idei de non-performante, cele mai multe pop-up pentru a rezolva această problemă atunci când încearcă să:
- Să-un cerc un punct care nu este acoperit de nici un segment, apoi un cerc poate fi tăiat în acest moment și pentru a obține în mod direct despre sarcina, știm deja cum să rezolve!
Da. Dar aceste puncte nu pot fi. Mai mult, fiecare punct de pe cerc poate fi acoperit cu 2, 10, sau chiar Θ (n) segmente - Se taie cercul într-un punct acoperit cu un număr minim de segmente!
Nu funcționează. Imaginați-vă trei segmente de pereți despărțitori 10 circumferențiare. Un total de 30 de bucăți. În două dintre aceste „partiții“ segmente ușor se suprapun reciproc. Trebuie să ghicească a treia de partiții și alegeți punctul de tăiere de la capătul uneia dintre aceste 10 segmente. - Avantajoasă pentru a lua ca răspuns la cel mai scurt interval!
Nu. Chiar și pe linia dreaptă nu mai este valabil: (0,49) (50,100) (48.51) - arunca profitabile dintr-o varietate de cea mai lunga durata de timp pe care cineva trece!
Nu. A se vedea exemplul anterior. - Și mai mult.
Există mai multe idei non-performante pentru a opri transferul de exprimat deja.
rezolvarea problemelor
Soluția 1.
Fiecare segment i este capătul din stânga al L [i] și R capătul din dreapta [i]. Sortarea segmentelor în ordine crescătoare a R [i]. În acest mod, vom rezolva segmentele. Următorul segment va fi adăugat la răspunsul, în cazul în care este mai mare decât limita maximă a limitelor dreapta-stanga-hand deja adăugate segmente.
Soluția 2.
Vă avertizez, decizia este lung și mult mai greu de cel anterior. Pe de altă parte, un mod fundamental de idei complexe nu este aici, astfel încât totul poate fi înțeleasă fără formarea inițială.
Pentru a începe cu, ca un set de arc pe cerc. Lăsați un cerc - segment curbat [0..M) și arce (segmente) sunt stabilite în perechi circumferențial L [i] .. R [i]. Dacă R [i]
Prezentarea toate obiectele într-un cerc, pentru a rezolva problema nu este foarte convenabil. Prin urmare, folosind tehnica „dublarea cercului“, trece la linia.
1. Dacă un anumit segment de R [i]
Acum avem segmente 2n pe linie și se taie un cerc cu un punct x corespunde lungimii acestei linii [x..x + M), unde 0 <= x Soluția 2 pentru O (sort + n 2). Se filtrează o dată segmentele de pe capătul din dreapta, apoi iteram n posibile puncte tăiate R [i], rezolvare pentru fiecare sarcină în O (n), precum și sarcina 1. Soluția 2 pentru O (sort + nk). unde k - mărimea setului, răspunsul la problema. Lăsați sortarea. Acum, să ne facă o observație interesantă: În funcție de dimensiunea seturilor de puncte tăiate obținute de noi diferă de cel optim pentru nu mai mult de 1. Asta este, dacă am tăiat în primul punct și mărimea k a primit o mulțime, este suficient pentru a găsi setul de K-1 dimensiune, și Acesta va fi cu siguranță optimă. Soluție: itera prima etapă, face k-2 pași înainte cu link-uri pentru următoarele, în cazul în care distanța dintre dreapta și punctul cel mai din stânga mai mică decât M, am găsit k-1 arce care nu se intersectează. Soluție O (sort + n) Nu este întotdeauna suficient pentru un anumit subiect de sarcini gata, trebuie să vină în mod regulat cu altele noi. Tocmai am vazut un efect amuzant: să ia o sarcină simplă clasic de sortare, înlocuiți „direct“ „cerc“, avem o problemă complexă în metoda de două-indicii și ideea probabilistă. Multe sarcini de învățare interesante și inventate. Apropo, încearcă să rezolve alte două probleme:
Și imediat după sortare utilizarea de către două indicatoare și O (n) pentru fiecare segment i numărat următorul segment următor [i], că ne-ar lua aviditate nostru (lăcomie: L [următor [i]]> R [i], astfel următor [i] = min).
Ia-un punct de timp aleatoriu i = aleator [0..n-1]. Pentru fiecare dintre i O (k) încercați = următor [i], în codul de mai sus.
Pentru că în cazul în care răspunsul de la segmentele K-1 există, a fost de ajuns pentru a intra în unele dintre aceste K-1, atunci probabilitatea ca în încercările nu am primit este atunci când merge la infinit. Rețineți că, în cazul în care a = Θ (1), algoritmul precedent pentru O (nk) au aranjat complet. Ie am primit un algoritm randomizat, a cărui funcționare timp O (n + sortare). Pentru a realiza o mai bună eroare de e -T. suficient pentru a nu încerca. și puncte, respectiv operația să fie O (sort + Tn).
Problema 3. Având în vedere n segmente de pe linia de a selecta subsetul dimensiunea maximă a segmentelor, astfel încât fiecare punct este acoperită de nu mai mult de k ori (ea ne-am rezolvat pentru k = 1).
Sarcina 4. Dată fiind n arce (segmente) pe un cerc ... și aceeași sarcină.Chiar și mai multe probleme
articole similare