[Risolto]determinare se due intervalli si intersecano

[jigen45]

Buonasera ragazzi, devo scrivere un programma in pseudocodice che stabilisce se in un array di n intervalli due di questi si intersecano.

Codice: Seleziona tutto

Intersezione(A)
    n = A.length
    for i = 0 to n do
        for j = i + 1 to n do
            if A[i].d >= A[j].s     // con questa notazione accedo agli estremi destro e sinistro: gli intervalli sono rappresentati in questo modo [h, k], con h e k estremi
                return true
    return false

ora (ammesso che il codice sia corretto) credo abbia una complessità temporale quadratica, mentre io dovrei progettarne uno di complessità O(nlgn). Sapreste darmi una mano?

[SuperStep]

quello che puoi fare, e' ordinarli a partire da un estremo o dall'altro e disporli in sequenza, in modo che se:

1)
il primo non si interseca con il secondo; ed il secondo non si interseca con il terzo; (essendo 1 > 2 e 2 > 3)
il primo non si interseca con il terzo.

2)
procedere in modo lineare:

se abbiamo per ipotesi tre intervalli, con queste coordinate sull'asse X: (disposte in modo INTERVALLO(inizio, fine))
A(3, 5)
B(4, 6)
C(5,7)

abbiamo che:
A interseca B,
B interseca C,
A !interseca C,

il modo piu semplice che mi viene per risolvere questo quesito e' questo, dato che sono ordinati: l'estremo superiore del precedente, deve essere MINORE dell'estremo inferiore del successivo;
se questa clausola e' vera, non c'e intersezione.

esempio:
A->superiore = 5 >= B->inferiore = 4; FALSO quindi intersezione (A con B)
A->superiore = 5 >= C->inferiore = 5; VERO quindi nessuna intersezione (A con C)

ovviamente dipende anche dal fatto se gli intervalli sono aperti o chiusi, io ho supposto aperti (per cui >= [maggiore uguale]), se erano chiusi la clausola e' diversa (per cui > [maggiore]).

abbastanza chiaro?

come vedi il tempo dopo l'ordinamento e' lineare. il tempo dell'ordinamento dipende dall'algoritmo che scegli per l'ordinamento.

[jigen45]

gli intervalli nell'array non sono ordinati..

[vaeVictis]

jigen45, se fornisci informazioni a piccole dosi, la discussione andrà avanti per parecchio prima che qualcuno (per esempio me ) interpreti correttamente la natura del problema e possa darti una mano.
Pertanto, potresti cortesemente porre precisamente cosa acquisisci e cosa devi ottenerne?
Proprio per passetti, altrimenti a fare ipotesi (come ha giustamente potuto fare SuperStep) andiamo avanti per un bel po'

[jigen45]

Scusate ragazzi, come tanti tra quelli che si trovano in periodo d'esame è un periodo un po' di "passione" Ecco il testo:
"Data una lista di n intervalli rappresentati da estremo sinistro ed estremo destro (ad
esempio, [5,6], [4,5], [7,9], [1,2], [6,8], [7,10]), progettare un algoritmo che decida se
esistono due intervalli che si intersecano. Due intervalli si intersecano se hanno almeno un
punto in comune. L'algoritmo deve avere tempo di esecuzione O(n log n) nel caso
peggiore.
Per esempio, tra gli intervalli [5,6], [4,5], [7,9], [1,2], [6,8], [7,10], quelli che si intersecano
sono: [4,5] e [5,6], [6,8] e [7,9], [5,6] e [6,8], [6,8] e [7,10], e infine [7,9] e [7,10].
Gli intervalli sono memorizzati in un array A. Se A=[h,k] è l’i-esimo intervallo, allora A.s
= h (“s” denota l’estremo sinistro) e A.d = k (“d” denota quello destro)."

[vaeVictis]

Scusate ragazzi, come tanti tra quelli che si trovano in periodo d'esame è un periodo un po' di "passione"

Ci siamo passati più o meno tutti, chi per un verso chi per un altro
La mia "richiesta" non era tanto per riprenderti, quanto per cercare di capire come poterti aiutare.

Ora ti sei spiegato.
Devo riflettere un attimo (in quanto programmo per "passione" e non sono un programmatore di formazione) su che tempi di esecuzione hanno alcuni algoritmi che ho in mente (o meglio... che ho visto in passato ).

[vaeVictis]

p.s.: no scusa... un'altra domanda... stiamo parlando di pseudocodice o hai anche un linguaggio di riferimento?

[SuperStep]

allora quello che farei e' utilizzare heap sort per l'ordinamento (che ha come tempo massimo nlogn) e contemporaneamente controllare il precedente

http://it.wikipedia.org/wiki/Algoritmo_di_ordinamento

se guardi wiki a questo indirizzo, l'immagine sulla destra ti rende il tutto piu chiaro, mentre ordini in base ad un estremo, fai anche il controllo di incidenza.

http://it.wikipedia.org/wiki/Heap_sort

[jigen45]

p.s.: no scusa... un'altra domanda... stiamo parlando di pseudocodice o hai anche un linguaggio di riferimento?

grazie mille a te e anche a SuperStep per esservi prodigati ad aiutarmi posso scriverlo semplicemente in pseudocodice quindi l'idea è semplicemente quella di utilizzare un algoritmo di ordinamento che richiede magari un tempo pari a O(nlgn) e poi con tempo lineare attraversare la lista e confrontare l' i-esimo intervallo (estremo destro) con quello successivo (estremo sinistro) con 0 < i < n - 1, con n lunghezza dell'array o sbaglio?..

[SuperStep]

volendo si puo' fare tutto simultaneamente; ovvero,

dopo la fase di riordinazione (non di ordinamento), passi a spostare il piu' alto estremo alla fine,
dopodiche' sposti il secondo piu' grande estremo alla (fine-1) e controlli l'intersezione con (fine),
dopodiche' sposti il terzo piu' grande estremo alla (fine-2) e controlli l'interszeione con (fine-1),
...
fino ad arrivare al primo intervallo

il numero di confronti e' n-1.
il tempo di ordiamento e' O(nlong),

dal momento che il confronto e' innestato nell'ordinamento, la complessita' temporale e' statica a O(nlogn) [poiche' vanno fatti tutti i confronti].

quindi al momento dello scambio, devi fare il controllo dell'intersezione se esiste un elemento successivo.

Esistono altri ordinamenti il cui tempo e O(nlogn), ma heapsort li distribuisce in maniera da tenerli ordinati eseguendo il confronto in maniera successiva, e questo ti serve per controllare la collisione sull'elemento superiore.

Se gli intervalli non sono ordinati non e' possibile definire un algoritmo il cui tempo di esecuzione non sia quadratico.

Per questo sfruttiamo un algoritmo di ordinamento con tempo inferiore, e simultaneamente facciamo i controlli, se li fai in momenti distinti la complessita' temporale diventa:

O(nlogn) + O(n-1).

in realta' il tempo di eseguzione e' pressoche' il medesimo, non varia quasi per nulla, ma varia la complessita'.

[M_A_W_ 1968]

Ecco il testo:
"Data una lista di n intervalli rappresentati da estremo sinistro ed estremo destro (ad
esempio, [5,6], [4,5], [7,9], [1,2], [6,8], [7,10]), progettare un algoritmo che decida se
esistono due intervalli che si intersecano. Due intervalli si intersecano se hanno almeno un
punto in comune. L'algoritmo deve avere tempo di esecuzione O(n log n) nel caso
peggiore.

Presumibilmente, nonostante l'uso di un array nella specifica, questo esercizio è concepito per indurti a prendere in mano il CLRS e leggere subito (almeno) i paragrafi dedicati agli interval trees, che sono poi in definitiva solo specializzazioni degli alberi di ricerca binari, così come i loro cugini AVL e Red/Black. Con codeste strutture dati si trattano in tutta la letteratura ordinariamente diffusa problemi del genere indicato: se poi i numeretti coinvolti sono davvero piccoli, dell'ordine di O(n), esistono anche ulteriori strutture dati algebriche molto raffinate, in grado di fornire prestazioni eccellenti.

[vbextreme]

GRAZIE maw mi hai dato un'ottima idea per gestire le collisioni!!!!!!!!!!

[jigen45]

grazie a tutti ragazzi

[jackynet92]

Se ritieni risolto il problema, modifica il titolo del primo post aggiungendo all'inizio [Risolto].

Se vuoi puoi installare questo script che ti aggiunge un pulsante che ti permette di mettere [Risolto] con un solo click.

Alla prossima