Quel est le chemin de la solution a donné un DFS sur ce graphique

Question

L'utilisation d'un DFS sur ce graphique, les noeuds sont visités dans l'ordre suivant (pour plus d'un nœud successeur, les noeuds sont poussés à la « frontière "dans l'ordre alphabétique):

S> A> E> D> F-> G

est cette séquence de visite le chemin de la solution aswell? Si oui, pourquoi n'est-ce pas S-> A-> E-> G, puisque G est aussi un nœud successeur de E?

PS: Im nouveau à des algorithmes, donc si je comprends clairement pas le concept, s'il vous plaît laissez-moi savoir.

Answer 1

Si vous visitez les nœuds, l'approche DFS traversera le graphique en fonction de l'ordre de création de la liste de contiguïté.

Par exemple, l'ordre d'insertion « s successeurs noeud E peut être de la manière suivante:

1- E-> D, G 
2- E-> G, D 

la première manière, vous parcourrez D->F->G ou D->G directement et dans les deux cas, vous visiterez noeud G avant de traverser l'un des nœuds E autres successeurs, de sorte que vous ne serez pas en mesure de parcourir le chemin S->A->E->G car le nœud G sera déjà visité auparavant à partir du nœud D ou F.

Dans la deuxième façon, vous parcourrez E->G directement, donc cela se traduira en traversant le chemin S->A->E->G, mais aussi vous ne serez pas en mesure d'accéder noeud G à partir du noeud D ou F, car il sera déjà visité du noeud E . Le scénario précédent se produira si vous visitez avec true ou false, mais si vous essayez de trouver le chemin le plus court en utilisant les coûts sur les bords, alors vous devrez utiliser l'algorithme de Dijkstra pour trouver le chemin le plus court sur un graphique, et vous pouvez en lire davantage here si vous n'êtes pas familier avec elle.

Answer 2

Je suppose la prise en compte à la fois le coût heuristique et le bord pour déterminer le nœud suivant à visiter.

À partir de S, il regarde ses trois possibilités:

A = 9 + 13 = 21 
B = 14 + 14 = 28 
C = 15 + 15 = 30 

Il choisit alors A et regarde son chemin uniquement disponible de A et se dirige vers E.

De E nous avons deux possibilités:

D = 2 + 8 = 10 
G = 19 + 0 = 19 

il sera alors choisir D et maintenant il a deux possibilités:

F = 11 + 5 = 16 
G = 16 + 0 = 16 

Son une cravate si en fonction de la façon dont l'algorithme a été mis en place et la solution que vous avez donné il va à F qui a alors deux possibilités:

E = 6 + 7 = 13 
G = 6 + 0 = 6 

Il se dirige ensuite vers G et enfin il voit que cette est le noeud de l'objectif et renvoie la séquence d'état.