Ordinamento particolare di coppie di interi (rotte su grafo)
Buonasera a tutti, provo ad esporvi il mio problema nella speranza di avere un confronto sull'argomento.
Poniamo di avere un grafo G=(V,E) non orientato di nodi $N=\{1,2,3,4,5,6,7,8\}$ completo, ovvero in cui ogni coppia di nodi sia connessa,
per cui E coincide col sottoinsieme del prodotto cartesiano $(i,j) \in N x N : i \ne j = (1,2), \dots , (7,8)$
Ai nostri scopi una "rotta" è semplicemente una sequenza di link senza ripetizioni della forma:
$r = \{ (1, 4), (4,6), (6,5), (5,1) \}$
in cui
A) la lunghezza della sequenza è almeno 2 (es. rotta "minimale": $\{ (1,x), (x,1) \} \forall x \in V$) ;
B) ogni rotta inizia e finisce nel nodo origine (convenzionalmente 1).
In altri termini una rotta non è altro che un sottoinsieme del prodotto cartesiano di cui sopra in cui vale una certa relazione d'ordine. Essa "visivamente" rappresenta il "partire" dal nodo 1, "recarsi" nel nodo 4, da 4 a 6 ... per poi rientrare nel nodo 1.
Dopo aver generato una rotta con un apposito algoritmo, ho il problema che il risultato che ottengo non tiene conto dell'ordinamento, ovvero mi restituisce una sequenza "scrumbled" del tipo:
$r' = \{ (5,1), (1, 4), (6,5), (4,6) \}$
Questo non è un errore di per sè, dipende semplicemente dal fatto che il modello risolutivo sta risolvendo un problema di programmazione matematica in cui non esiste il concetto di "rotta" come lo stiamo discutendo. Mi chiedo allora se esista un modo di adattare un algoritmo di ordinamento efficente (ad esempio un merge-sort) di tali coppie. In fondo se posso ordinare liste di interi, tale potenzialità esce fuori dal fatto che gli interi sono ordinabili, ovvero esiste una relazione d'ordine che mi permette di affermare se $a \leq b$ o meno, $\forall a,b \in N$.
In effetti posso dedurre una relazione d'ordine sulle mie coppie, dato che posso stabilire che:
$a=(i,j)$ "segue strettamente" $b=(h,k)$ sse $j=h$ ovviamente per tutte le rotta,
ma credo che questa relazione sia leggermente più "stringente" della precedente, dato che di fatto impone come debba porre le coppie nella lista.
Avevo tentato come soluzione sbrigativa un mapping che facesse corrispondere ad ogni coppia un numero, ordinasse il vettore "shadow" di numeri e poi riportasse il risultato ordinato nel dominio delle coppie, ma in alcune circostanze questo approccio non andava ed ho lasciato perdere.
Spero di essere stato chiaro e di avere fornito i dettagli sufficenti, magari mi sto complicando la vita...
Domanda: secondo voi è praticabile adattare un merge sort per ordinare coppie? Conoscete un metodo per fare qualcosa anche soltanto di simile?
Poniamo di avere un grafo G=(V,E) non orientato di nodi $N=\{1,2,3,4,5,6,7,8\}$ completo, ovvero in cui ogni coppia di nodi sia connessa,
per cui E coincide col sottoinsieme del prodotto cartesiano $(i,j) \in N x N : i \ne j = (1,2), \dots , (7,8)$
Ai nostri scopi una "rotta" è semplicemente una sequenza di link senza ripetizioni della forma:
$r = \{ (1, 4), (4,6), (6,5), (5,1) \}$
in cui
A) la lunghezza della sequenza è almeno 2 (es. rotta "minimale": $\{ (1,x), (x,1) \} \forall x \in V$) ;
B) ogni rotta inizia e finisce nel nodo origine (convenzionalmente 1).
In altri termini una rotta non è altro che un sottoinsieme del prodotto cartesiano di cui sopra in cui vale una certa relazione d'ordine. Essa "visivamente" rappresenta il "partire" dal nodo 1, "recarsi" nel nodo 4, da 4 a 6 ... per poi rientrare nel nodo 1.
Dopo aver generato una rotta con un apposito algoritmo, ho il problema che il risultato che ottengo non tiene conto dell'ordinamento, ovvero mi restituisce una sequenza "scrumbled" del tipo:
$r' = \{ (5,1), (1, 4), (6,5), (4,6) \}$
Questo non è un errore di per sè, dipende semplicemente dal fatto che il modello risolutivo sta risolvendo un problema di programmazione matematica in cui non esiste il concetto di "rotta" come lo stiamo discutendo. Mi chiedo allora se esista un modo di adattare un algoritmo di ordinamento efficente (ad esempio un merge-sort) di tali coppie. In fondo se posso ordinare liste di interi, tale potenzialità esce fuori dal fatto che gli interi sono ordinabili, ovvero esiste una relazione d'ordine che mi permette di affermare se $a \leq b$ o meno, $\forall a,b \in N$.
In effetti posso dedurre una relazione d'ordine sulle mie coppie, dato che posso stabilire che:
$a=(i,j)$ "segue strettamente" $b=(h,k)$ sse $j=h$ ovviamente per tutte le rotta,
ma credo che questa relazione sia leggermente più "stringente" della precedente, dato che di fatto impone come debba porre le coppie nella lista.
Avevo tentato come soluzione sbrigativa un mapping che facesse corrispondere ad ogni coppia un numero, ordinasse il vettore "shadow" di numeri e poi riportasse il risultato ordinato nel dominio delle coppie, ma in alcune circostanze questo approccio non andava ed ho lasciato perdere.
Spero di essere stato chiaro e di avere fornito i dettagli sufficenti, magari mi sto complicando la vita...
Domanda: secondo voi è praticabile adattare un merge sort per ordinare coppie? Conoscete un metodo per fare qualcosa anche soltanto di simile?
Risposte
E' possibile passare più volte per uno stesso vertice? Se non è possibile, allora è possibile stabilire ad ogni passo quale vertice debba stare a sinistra e non è necessario ricorrere al mergesort. Sarebbe infatti sufficiente memorizzare le coppie in una mappa associativa in cui la chiave è il nodo a sinistra e il valore è quello a destra. Si inizia prendendo la coppia con 1 a sinistra. A questo punto si legge la destinazione dell'arco e si cerca la coppia con quella chiave.
Io rivedrei un po l'algoritmo che genera le rotte.
Inizierei con le rotte ad una tappa:
1-2 2-1
1-3 3-1
.....
1-6 6-1
Poi con quelle a 2 tappe:
1-2 2-3 3-1
1-2 2-4 4-1
.....
1-6 6-5 5-1
Poi quelle a 3.... e cosi via
In altre parole, farei in modo che l'algoritmo mi generi le tappe gia' ordinate.
Inizierei con le rotte ad una tappa:
1-2 2-1
1-3 3-1
.....
1-6 6-1
Poi con quelle a 2 tappe:
1-2 2-3 3-1
1-2 2-4 4-1
.....
1-6 6-5 5-1
Poi quelle a 3.... e cosi via
In altre parole, farei in modo che l'algoritmo mi generi le tappe gia' ordinate.
Ringrazio entrambi per i contributi.
In verità posso passare più volte per uno stesso vertice, facendo delle visite di "dead-heading". Di fatto, nella pratica, questo capita molto spesso.
Tuttavia riflettendoci sono anche io convinto che le rotte debbano essere generate diversamente, e che il post-processing sia "di troppo", in qualche modo: il problema è che il modello risolutivo è basato sulla programmazione matematica binaria e non ho inserito vincoli che definiscano una rotta in quei termini (ma qui si sfora nell'ottimizzazione e ricerca operativa, in realtà). Probabilmente partendo dalle rotte di lunghezza 2 si riuscirebbe a generalizzare a quelle di lunghezza n>2, ma devo pensarci un po' e formalizzarlo.
Probabilmente la soluzione migliore per adesso è proprio quella di memorizzare le coppie chiave valore come suggerito...
In verità posso passare più volte per uno stesso vertice, facendo delle visite di "dead-heading". Di fatto, nella pratica, questo capita molto spesso.
Tuttavia riflettendoci sono anche io convinto che le rotte debbano essere generate diversamente, e che il post-processing sia "di troppo", in qualche modo: il problema è che il modello risolutivo è basato sulla programmazione matematica binaria e non ho inserito vincoli che definiscano una rotta in quei termini (ma qui si sfora nell'ottimizzazione e ricerca operativa, in realtà). Probabilmente partendo dalle rotte di lunghezza 2 si riuscirebbe a generalizzare a quelle di lunghezza n>2, ma devo pensarci un po' e formalizzarlo.
Probabilmente la soluzione migliore per adesso è proprio quella di memorizzare le coppie chiave valore come suggerito...
Che cosa stai cercando di fare esattamente?
Se si può passare più volte da uno stesso vertice (immagino anche sull'uno?) ho paura che l'ordinamento sia impossibile. Supponiamo che il vertice $a$ compaia più volte, allora ogni sottorotta $\{(a, x) ... (y, a)\}$ che non contiene $a$ si può scambiare con un altra dello stesso tipo. Quindi per un insieme di coppie sono possibili più ordinamenti e quindi più rotte. In questo caso è quindi forse meglio cercare di generare le rotte in modo diverso.
Se si può passare più volte da uno stesso vertice (immagino anche sull'uno?) ho paura che l'ordinamento sia impossibile. Supponiamo che il vertice $a$ compaia più volte, allora ogni sottorotta $\{(a, x) ... (y, a)\}$ che non contiene $a$ si può scambiare con un altra dello stesso tipo. Quindi per un insieme di coppie sono possibili più ordinamenti e quindi più rotte. In questo caso è quindi forse meglio cercare di generare le rotte in modo diverso.
"apatriarca":
Che cosa stai cercando di fare esattamente?
Se si può passare più volte da uno stesso vertice (immagino anche sull'uno?) ho paura che l'ordinamento sia impossibile.
Risolvo un problema di ottimizzazione e vado a parserizzare le variabili del tipo x(i,j,k)={0,1},
e posso quindi sapere con certezza per ogni coppia se in quella rotta k passa da (i,j) o meno.
Il problema è che le variabili che rappresentano il passaggio da un nodo all'altro mi vengono restituite alla rinfusa, non nell'ordine in cui vengono attraversate...credo che il problema che giustamente poni sia una specie di non determinismo, considerando che posso anche avere rotte del tipo:
$r = \{1,2,1,3,4,5,6,4,1\}$
Ma a quel punto credo che basterebbe scegliere anche la prima che trova per risolvere l'ambiguità...
"not4fun":
Ma a quel punto credo che basterebbe scegliere anche la prima che trova per risolvere l'ambiguità...
Non mi sembra così semplice (considerando che hai scritto che i vertici si possono ripetere).
Considera la seguente rotta $\{1, 2, 4, 7, 3, 2, 1 \}$. Se fai la “scelta sbagliata” al secondo passo prendendo la coppia $(2, 1)$ al posto di $(2,4)$ allora ti verrebbe la rotta $\{ 1, 2, 1 \}$ che tralascia molte degli archi del grafo che appartengono alla rotta originale.
Non ho ancora capito comunque qual'è lo scopo finale. Che problema di ottimizzazione stai cercando di risolvere? Secondo me potrebbe essere meglio cercare di trovare una soluzione più diretta al problema di ottimizzazione originale.
Non ho ancora capito comunque qual'è lo scopo finale. Che problema di ottimizzazione stai cercando di risolvere? Secondo me potrebbe essere meglio cercare di trovare una soluzione più diretta al problema di ottimizzazione originale.
"apatriarca":
Considera la seguente rotta $\{1, 2, 4, 7, 3, 2, 1 \}$. Se fai la “scelta sbagliata” al secondo passo prendendo la coppia $(2, 1)$ al posto di $(2,4)$ allora ti verrebbe la rotta $\{ 1, 2, 1 \}$ che tralascia molte degli archi del grafo che appartengono alla rotta originale.
E' esattamente il tipo di eccezione che mi è capitata... hai saputo cogliere il problema meglio di quanto abbia saputo spiegarti!
"apatriarca":
Non ho ancora capito comunque qual'è lo scopo finale. Che problema di ottimizzazione stai cercando di risolvere? Secondo me potrebbe essere meglio cercare di trovare una soluzione più diretta al problema di ottimizzazione originale.
Sto risolvendo un problema di routing generalizzato su grafo misto con domande su link e nodi (il caso più generale che puoi avere di questo tipo di problemi, se vuoi). Abbiamo modellato il problema con CPLEX e sembra funzionare, il mio problema nasce dal fatto che devo mettere in ordine i risultati a mano e pensavo ad una procedura automatica, dato che a manina posso farlo per rotte piccole ma quando ho k rotte su grafi grandi diventa improponibile.
Un esempio del file di output (il risultato che ottengo) che vorrei ordinare (attrav e serve sono le variabili simboliche x,y, quando scrivo attrav(0)(2,1) con 0 indico l'indice della rotta e con (2,1) il link che si sta attraversando, mentre = 1.0 indica semplicemente che quella variabile è attivata):
attrav (0)(2,1) = 1.0 attrav (0)(3,1) = 1.0 attrav (0)(1,4) = 1.0 attrav (0)(4,1) = 1.0 attrav (0)(5,1) = 1.0 attrav (0)(6,1) = 1.0 attrav (0)(1,7) = 1.0 attrav (0)(1,8) = 1.0 attrav (0)(1,9) = 1.0 attrav (0)(1,12) = 1.0 attrav (0)(4,3) = 1.0 attrav (0)(6,4) = 1.0 serve (0)(7,6) = 1.0 attrav (0)(7,6) = 1.0 attrav (0)(8,7) = 1.0 serve (0)(9,5) = 1.0 serve (0)(11,2) = 1.0 attrav (0)(12,11) = 1.0
Se ogni vertice si puo' ripetere piu' volte, non si tratta semplicemente di ordinare le sequenze, ma semmai, di trovare tutte le varie combinazioni possibili che si posso avere, utilizzando TUTTE le sequenze a disposizione.
"Umby":
Se ogni vertice si puo' ripetere piu' volte, non si tratta semplicemente di ordinare le sequenze, ma semmai, di trovare tutte le varie combinazioni possibili che si posso avere, utilizzando TUTTE le sequenze a disposizione.
Anche generandole tutte brute force avrei il problema di sceglierne una...!
"not4fun":
[quote="Umby"]Se ogni vertice si puo' ripetere piu' volte, non si tratta semplicemente di ordinare le sequenze, ma semmai, di trovare tutte le varie combinazioni possibili che si posso avere, utilizzando TUTTE le sequenze a disposizione.
Anche generandole tutte brute force avrei il problema di sceglierne una...![/quote]
Sicuramente SI.
Altro elemento da considerare è quello se hai le varie tappe ordinate, mi spiego:
Se hai le tappe:
1-2 2-3 3-1 potresti avere la rotta:
1-2 --> 2-3 --> 3-1 ma anche la contraria:
1-3 --> 3-2 --> 2-1 (invertendo i termini di ogni singola tappa)
"Umby":
Altro elemento da considerare[...]
Se hai le tappe:
1-2 2-3 3-1 potresti avere la rotta:
1-2 --> 2-3 --> 3-1 ma anche la contraria:
1-3 --> 3-2 --> 2-1 (invertendo i termini di ogni singola tappa)
Sì, anche se in questo caso si tratta della stessa rotta scritta in modo diverso, dato che visita gli stessi nodi (soltanto cambia il verso di percorrenza, non fissato a priori neanche quello)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo