Pourquoi DFS ne peut-il pas être utilisé pour trouver les chemins les plus courts dans les graphiques non pondérés?

16

Je comprends que l'utilisation de DFS "tel quel" ne trouvera pas le chemin le plus court dans un graphique non pondéré.

Mais pourquoi modifier DFS pour lui permettre de trouver les chemins les plus courts dans les graphiques non pondérés est-il une perspective désespérée? Tous les textes sur le sujet indiquent simplement que cela ne peut pas être fait. Je ne suis pas convaincu (sans l'avoir essayé moi-même).

Connaissez-vous des modifications qui permettront à DFS de trouver les chemins les plus courts dans les graphiques non pondérés? Sinon, qu'est-ce qui rend l'algorithme si difficile?

Le chat unfun
la source
1
L'algorithme d'orientation le plus courant sur les graphiques non pondérés est A *, avec la légère modification que les liens sont rompus plus près de la finition. Cela donnera un algorithme similaire à DFS, en ce sens qu'il essaiera d'abord l'itinéraire le plus direct, et ne fera de bulles que s'il en a besoin.
BlueRaja - Danny Pflughoeft
1
Essayez d'utiliser DFS sur certains graphiques (bien choisis); si cela ne fonctionne vraiment pas, vous devriez rencontrer des problèmes. Btw, votre question se lit comme si elle fonctionnait sur des graphiques pondérés.
Raphael
Oui, vous pouvez le faire. Voici la solution
Anmol Middha

Réponses:

12

Le seul élément de la recherche en profondeur que vous modifiez est l'ordre dans lequel les enfants sont examinés. La version normale se déroule dans un ordre arbitraire, c'est-à-dire dans l'ordre dans lequel les enfants sont stockés.

La seule alternative possible (vers les chemins les plus courts) que je peux trouver est une approche gourmande, qui regarde les enfants par ordre de distance par rapport au nœud actuel (de petit à grand). Il est facile de construire un contre-exemple pour cette règle:

contre-exemple pour la règle gourmande
[ source ]

Maintenant, ce n'est pas une preuve qu'il n'existe pas de stratégie de choix du prochain enfant à étudier qui permettra à DFS de trouver les chemins les plus courts.

Cependant, peu importe la règle¹, vous pouvez construire des graphiques qui font que DFS s'engage à faire un long détour au tout premier nœud, comme je l'ai fait pour la règle gourmande. Attribuez des arêtes et telle sorte que la règle choisisse de visiter première, et affectez un poids supérieur à celui de . Par conséquent, il est plausible que DFS ne puisse jamais trouver les chemins les plus courts (dans les graphiques généraux).( s , a ) a ( a , b ) ( s , t )(s,t)(s,a)a(a,b)(s,t)

Notez que puisque vous pouvez exprimer chaque graphique pondéré (entier positif) sous forme de graphique non pondéré - remplacez simplement les arêtes par le coût par une chaîne avec nœuds - les mêmes exemples concernent le DFS sur les graphiques non pondérés. Ici, la situation est encore plus sombre: sans poids, que peut utiliser DFS pour déterminer le prochain enfant à visiter?c - 1cc1


  1. Tant que la règle est déterministe. Si ce n'est pas le cas, il ne peut clairement pas toujours trouver les chemins les plus courts.
Raphael
la source
Corrigez-moi si je me trompe, mais cela signifie-t-il que DFS peut trouver le chemin le plus court dans n'importe quel graphique, mais prendra un temps exponentiel en le faisant?
Anmol Singh Jaggi
@AnmolSinghJaggi Non. DFS ne trouve qu'un seul chemin.
Raphael
10

L'étendue -première-recherche est l'algorithme qui trouvera les chemins les plus courts dans un graphique non pondéré.

Il existe un simple ajustement pour passer de DFS à un algorithme qui trouvera les chemins les plus courts sur un graphique non pondéré. Essentiellement, vous remplacez la pile utilisée par DFS par une file d'attente. Cependant, l'algorithme résultant n'est plus appelé DFS. Au lieu de cela, vous aurez implémenté la recherche en largeur d'abord.

Le paragraphe ci-dessus donne une intuition correcte, mais simplifie un peu trop la situation. Il est facile d'écrire du code pour lequel le simple échange donne une implémentation de la première recherche étendue, mais il est également facile d'écrire du code qui ressemble à première vue à une implémentation correcte mais qui ne l'est pas. Vous pouvez trouver une question connexe cs.SE sur BFS vs DFS ici . Vous pouvez trouver un joli pseudo-code ici.

Joe
la source
3

Vous pouvez!!!

Marquez les nœuds comme visités pendant que vous allez en profondeur et démarquez-vous lorsque vous revenez, tout en revenant lorsque vous trouvez une ou plusieurs autres branches, répétez la même chose.

Enregistrez le coût / chemin pour toutes les recherches possibles où vous avez trouvé le nœud cible, comparez tous ces coûts / chemin et choisissez le plus court.

Le gros problème (et je veux dire GRAND) avec cette approche est que vous visiteriez le même nœud plusieurs fois, ce qui fait de dfs un mauvais choix évident pour l'algorithme de chemin le plus court.

user2407394
la source
1
Vous voudrez peut-être noter que cela change énormément la complexité . Cela pourrait potentiellement explorer tous les chemins possibles de à si je le comprends correctement. tst
ryan
1
@ user2407394 Avez-vous réellement implémenté cette variante de DFS et l'avez-vous exécuté correctement pour un graphique moyennement grand? J'hésiterais à appeler cette variation DFS. J'appellerais cela une recherche épuisant la profondeur d'abord.
John L.
J'ai mis en place ce type d'approche, son fonctionnement est très lent. Je pense à ajouter une mnémonisation pour améliorer les performances.
Mic
@ user2407394 il semble que cela fonctionnerait, mais comment vérifier quand s'arrêter car il n'y aurait pas de liste "visitée" si vous les décochez tous?
Joe Black
0

BFS a une belle propriété qui vérifiera tous les bords de la racine et gardera la distance de la racine aux autres nœuds aussi minime que possible, mais dfs saute simplement au premier nœud adjacent et va en profondeur. Vous POUVEZ modifier DFS pour obtenir le chemin le plus court, mais vous ne vous retrouverez que dans un algorithme de complexité temporelle plus élevée ou finirez par faire la même chose que BFS.

vikkyhacks
la source
-3

IL est possible de trouver le chemin entre deux sommets avec le nombre minimum d'arêtes en utilisant DFS. nous pouvons appliquer une approche de niveau

Abereham Wodajia
la source
2
Veuillez donner plus de détails. Je ne peux pas dire quel algorithme vous essayez de décrire dans cette seule phrase.
David Richerby
-3

Vous pouvez

il suffit de parcourir le graphique de manière dfs et de vérifier

if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

Voici le lien pour une solution complète

Anmol Middha
la source
1
La réponse acceptée affirme que cela n'est pas possible, ce qui contredit votre affirmation. Pouvez-vous expliquer pourquoi vous pensez que cette approche fonctionne néanmoins? (ou expliquez pourquoi cette approche fonctionne en général)
Lézard discret
N'est-ce pas simplement répéter la réponse de user2407394 , uniquement avec du code difficile à comprendre (vous n'avez pas défini ce que signifient ces variables, et ce n'est pas évident pour moi) au lieu d'une explication?
David Richerby
Oui, c'est l'implémentation de la réponse de user2407394. Désolé pour le dérangement. J'ai ajouté des commentaires dans le code. Vous pouvez le vérifier maintenant.
Anmol Middha