Comment puis-je trouver le chemin le plus court dans un graphique, en ajoutant le moins de nouveaux nœuds?

Question

J'ai besoin de trouver le chemin le plus court dans un graphique avec le plus petit nombre de nœuds ajoutés. Les nœuds de début et de fin ne sont pas importants. S'il n'y a pas de chemin dans un graphe juste entre les nœuds n spécifiés, je peux ajouter quelques nœuds pour compléter l'arbre le plus court mais je veux ajouter le moins de nouveaux nœuds possible.

Quel algorithme puis-je utiliser pour résoudre ce problème?

Answer 1

Commencez par le noeud de départ.

Si c'est le noeud cible, vous avez terminé.

Vérifiez chaque nœud connecté, s'il s'agit du nœud cible. Si la valeur est true, vous avez terminé

Vérifiez si l'un des noeuds connectés est connecté au noeud cible. Si c'est vrai, vous avez terminé.

Sinon, ajoutez un noeud connecté au noeud de début et de fin. terminé.

Answer 2

Je vous recommande d'utiliser un algorithme génétique. Plus d'informations here et here. En l'expliquant rapidement, GA est un algorithme qui permet de trouver des solutions exactes ou approximatives aux problèmes d'optimisation et de recherche.

Vous créez une population initiale de solutions possibles. Vous les évaluez avec la fonction de remise en forme afin de savoir lesquels sont les plus appropriés. Après cela, vous utilisez des algorithmes évolutifs qui utilisent des techniques inspirées par la biologie de l'évolution telles que l'héritage, la mutation, la sélection et le croisement.

Après plusieurs générations, vous trouverez la solution la plus adaptée (la plus courte) au problème.

Answer 3

Vous souhaitez minimiser le nombre de nœuds dans le chemin (au lieu de la somme des poids comme dans les algorithmes généraux).

Si c'est le cas, assignez un poids égal à tous les bords et trouvez le chemin le plus court (en utilisant les algorithmes génériques). Vous aurez ce dont vous avez besoin.

Et s'il n'y a pas de chemin, ajoutez simplement ce bord au graphique.

Sables.

PS: Si vous donnez une valeur de 1 pour chaque bord, le nombre de noeuds dans le chemin serait le poids-1 (à l'exclusion des noeuds source et destination)