Come eseguire iterazioni su tutte le permutazioni di collegamenti validi tra i nodi

Question

Come eseguire iterazioni su tutte le permutazioni di collegamenti validi tra i nodi

#1 da (2 voti)
#2 da (1 voti)

3

Immagina un'area 2D, con un numero (array) di nodi (o punti) definiti al suo interno, in posizioni arbitrarie (ma note) (numero intero x, coordinate y), come questo:

Dalìvoglioessereingrado,programmaticamente,diaggiungereilmaggiornumeropossibiledi"link". Un "collegamento" è una linea retta tra due nodi qualsiasi, ma un collegamento non può attraversare un altro collegamento. Ho già creato un metodo che può verificare se due link si incrociano. ad esempio

Con un dato insieme di nodi, esiste un numero limitato di modi in cui i collegamenti possono essere disposti e voglio essere in grado di generare tutte quelle possibili combinazioni (valide).

Tuttavia, non ho assolutamente idea da dove cominciare. Potrei riempire casualmente i nodi con link validi, ma non so come generare iterativamente ogni possibile permutazione.

Suppongo che esista un qualche tipo di algoritmo per problemi come questo, probabilmente basato sulla ricorsione, ma le mie ricerche finora sono state infruttuose.

Non sto cercando una soluzione codificata, posso fare quella parte. Quello di cui ho bisogno è il processo di progettazione di alto livello, o algoritmo, che può essere seguito per risolvere questo problema.

c++ algorithms

posta Dave 18.02.2015 - 14:54

fonte

2 risposte

Leggi altre domande sui tag c++ algorithms

Il caching degli oggetti in questo codice è troppo costoso? Le modifiche all'entrata di FNV-1A mostrano l'effetto valanga?

score 2 · Answer 1

Qui hai un problema piuttosto difficile.

Penso a un metodo che assomiglia a Setaccio di Eratostene .

In primo luogo, puoi "nominare" o "numerare" ciascun link. Supponiamo di avere solo 5 nodi, quindi avremo 10 link. Numero ciascuno da 1 a 10.

Ora possiamo inserirli tutti in un array.

Supponiamo di avere questa lista che rappresenta due link che si intersecano tra loro:

1 - 3
1 - 4
1 - 7
1 - 10
2 - 4
2 - 8
3 - 4
6 - 9
6 - 10

Ora visualizziamo questo. Per prima cosa, scelgo di disegnare il link 1.

* Per le immagini sottostanti, verde significa che ho scelto di disegnare il collegamento, rosso significa che il collegamento non può essere disegnato (perché interseca un link selezionato), e bianco significa che il link può essere disegnato.

Quindi,controllaciascunelementodallinkn.2allinkn.10:intersecaillinkn.1?Sesì,dovremmoeliminarli(significachenondobbiamodisegnarli).Inquestocaso:link#3,#4,#7,#10(dall'elencosopra)

Ora puoi scegliere qual è il prossimo a disegnare: o # 2, # 5, # 6, # 8 o # 9? Supponiamo che tu scelga # 2, quindi esegui la stessa procedura. Controlla il resto dell'elemento: se è già rosso, puoi saltarlo, ma se è bianco (può ancora essere disegnato), controlla se interseca il collegamento n. 2. Il link n. 2 si interseca con n. 4 e n. 8, ma poiché il n. 4 è già stato eliminato, eliminiamo solo il n. 8.

Quindi,scegliunaltrolinkecosìvia.Notachepossiamofareusodiduearray:unarrayinterocontenenteilinkel'altrounarraybooleanoperverificareseèeliminatoomeno.

Puoifarloiniterazione:sceglierequalelinkperdisegnareedeliminarequellicheliintersecano.Inquestomodo,puoievitaredidisegnarelinknonnecessari.

Beh,èsoloun'ideachepotrebbefunzionare.Manonpensochesiafaciledaimplementare,népensochepossaessereconsiderato"efficiente" in termini di complessità.

score 1 · Answer 2

Per ridurre il numero di chiamate ricorsive ho pensato di introdurre un rigoroso ordinamento di collegamenti per poter eliminare i duplicati nella fase di inizializzazione (prima di qualsiasi ricorsione):

sui link definiscono qualsiasi ordinamento rigoroso (arbitrario) order
sui link definiscono un metodo doesNotCrossWith() che restituisce l'insieme di collegamenti di ordine superiore che questo collegamento non attraversa (in grado di eseguire in tempo costante dopo l'inizializzazione)
sui collegamenti definiscono un metodo doesNotCrossWithIntersectionOf(Set<Link>) che restituisce l'intersezione del parametro e doesNotCrossWith()

definisce il metodo ricorsivo principale getValidPermutations(Link link, Set<Link> linksNotForbidden) (Pseudocode):

Set<Set<Link>> validPermutationsIncludingLink;

// add the current link (alone) itself to the possible permutations (to be added to):
validPermutations.add(new Set(link));

Set<Link> linksStillAllowed = link.doesNotCrossWithIntersectionOf(linksAllowed);

for (Link otherLink : linksStillAllowed) {
    Set<Set<Link>> validPermutationsOfOther;

    //recursive call:
    for (Set<Link> validPermutation : getValidPermutations(otherLink, linksStillAllowed)) {
        validPermutation.add(otherLink);
        validPermutationsOfOther.add(validPermutation);
    }
    validPermutations.addAll(validPermutationsOfOther);
}

return validPermutations;

chiama getValidPermutations per ogni link e crea un'unione dei risultati.

La profondità massima ricorsiva è il numero di (possibili) link n .

P.S .: Con 7 nodi disposti approssimativamente come nel tuo esempio ottengo ~ 150 ms di tempo di esecuzione con questa implementazione sulla mia macchina che porta a 37055 possibili permutazioni, per un gran numero di nodi potrebbero essere necessarie ulteriori ottimizzazioni.