Attraversamento grafico e filtraggio nella navigazione interna e ricerca del percorso

Question

Attraversamento grafico e filtraggio nella navigazione interna e ricerca del percorso

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

2

Quale delle seguenti opzioni impiega meno tempo di elaborazione / è meno costoso in un algoritmo di attraversamento grafico per un sistema di navigazione (interno)?

a) Per produrre tutti i possibili percorsi tra i punti di partenza e di destinazione (nodi sul grafico) quindi applicare un meccanismo di filtraggio per abbinare le capacità e le preferenze dell'utente di navigazione (come trovare tutti i percorsi sul grafico e quindi escludere le scale per sedia a rotelle utenti), o

b) Non appena il profilo dell'utente è disponibile per il sistema, filtra il grafico ed escludi i percorsi che non sono attraversabili per questo utente e quindi esegui un algoritmo di percorso più breve?

algorithms graph-traversal filtering

posta NKK 13.12.2013 - 17:36

fonte

2 risposte

Leggi altre domande sui tag algorithms graph-traversal filtering

Come devo rendere più efficiente la ricerca di un database relazionale? [duplicare] Come valutare CLR / C ++ vs C ++ nativo?

score 1 · Answer 1

Mi sembra che la corrispondenza dell'utente rimuova alcuni nodi dal grafico e cambi il costo degli altri. Cioè, le preferenze rendono alcuni percorsi meno costosi (migliori) e in realtà modificano il grafico stesso (rimozione dei nodi delle scale per gli utenti di sedie a rotelle).

Ciò significa che è necessario eseguire il percorso più breve sul grafico modificato per ottenere il risultato - solo b) funzionerà. La versione precalcata a) non tiene conto dei costi del percorso modificati dalle preferenze e dei nodi rimossi e pertanto fornirà risposte errate.

score 1 · Answer 2

Invece di filtrare il grafico per rimuovere i percorsi, perché non aggiungere pesi ai nodi o ai bordi e quindi implementare l'algoritmo del percorso più breve in modo che sia semplicemente impossibile attraversare i nodi oltre una soglia di peso configurabile.

A seconda di quanto siano complicati i vincoli, puoi anche modificare l'algoritmo per controllare i set di vincoli mentre attraversa il grafico. Fondamentalmente, quello che sto cercando di dire è che puoi filtrare per ignorare i nodi non idonei come parte dell'algoritmo del percorso più breve, non hai davvero bisogno di farlo in due passaggi.