Risolto il percorso di lunghezza tra due nodi del grafico

Question

Esiste un algoritmo che, se dati due nodi su un grafico, troveranno un percorso tra loro che prende il numero specificato di salti? Qualsiasi nodo può essere collegato a qualsiasi altro.

I punti al momento si trovano nello spazio 2D, quindi non sono sicuro che un grafico sia l'approccio migliore.

Answer 1

Se hai nodi che cercano di trovare percorsi in termini di salti, un grafico è probabilmente l'approccio giusto. Non sono sicuro di aver capito cosa stai cercando di fare e quali sono i vincoli, soprattutto per quanto riguarda "Qualsiasi nodo può essere collegato a qualsiasi altro" .. che sembra un po 'aperto.

Ignorando ciò, comunque; con una rappresentazione grafica:

Sembra come iniziare dal primo nodo e fare una prima ricerca approfondita da lì, e terminare una ricerca se (a) il luppolo preso è più grande del numero specificato o (b) siamo arrivati ??al secondo nodo; questo determinerà il primo (non solo) percorso che collega i due nodi (al massimo) in molti hop.

Se deve essere esattamente il luppolo specificato, termina qualsiasi ramo della ricerca se il luppolo è andato oltre e termina con successo se sei arrivato anche al secondo nodo.

Answer 2

Hai provato DFS approfondito iterato ?

Answer 3

Approccio stupido: (la struttura dei dati è una matrice di pile). Questo sta fondamentalmente facendo Breadth First Search (BFS) fino alla profondità N, tranne per il fatto che se i loop sono consentiti (non hai chiarito ma suppongo che lo siano), non escluderai i nodi visitati da ulteriori ricerche.

1. Push nodo iniziale su uno stack memorizzato nell'array con indice 0 (indice = profondità)

2. Per ogni livello / indice "l" 0-N:

   Per ciascun nodo su uno stack memorizzato al livello "l", trova tutti i suoi vicini e spingili su uno stack memorizzato nel livello "l + 1".

   Importante: se l'attività consente di trovare percorsi che contengono loop, NON verificare se hai già visitato un nodo aggiunto. Se non consente i loop, utilizzare un hash di nodi visitati per non aggiungere alcun nodo due volte **

3. Ferma quando finisci il livello " N-1 " ;.

4. Scorri su tutti i nodi appena aggiunti per impilarli all'indice " N " e trova il tuo nodo di destinazione. Se trovato: successo, in caso contrario, nessun percorso simile.

Nota che se per " ogni nodo può essere collegato " stai insinuando un grafico COMPLETAMENTE CONNESSO, quindi esiste una risposta matematica che non coinvolge effettivamente i nodi in visita

(tuttavia, la formula è troppo lunga per scrivere nel campo di immissione testo di StackOverflow)