Chemin de longueur fixe entre deux nœuds de graphe

Question

Existe-t-il un algorithme permettant, si deux nœuds d'un graphe sont représentés, de trouver une route entre eux prenant le nombre de sauts spécifié? Tout nœud peut être connecté à n’importe quel autre.

Les points en ce moment sont situés dans un espace 2D, je ne suis donc pas sûr qu'un graphique soit la meilleure approche.

Answer 1

Si vous avez des nœuds qui cherchent des routes en termes de sauts, alors un graphe est probablement la bonne approche. Je ne suis pas sûr de comprendre ce que vous essayez de faire et quelles sont les contraintes, en particulier en ce qui concerne "Tout nœud peut être connecté à un autre". .. qui semble un peu ouvert.

En ignorant cela, cependant; avec une représentation graphique:

Cela semble commencer à partir du premier nœud, puis effectuer une première recherche en profondeur à partir de là et terminer une recherche si (a) le nombre de sauts pris est supérieur au nombre spécifié ou (b) nous sommes arrivés au deuxième nœud; cela déterminera le premier (non seulement) chemin reliant les deux nœuds dans (au plus) autant de sauts.

S'il doit s'agir exactement des sauts spécifiés, mettez fin à toute branche de la recherche si les sauts ont été dépassés, et terminez avec succès si vous êtes également arrivé au deuxième noeud.

Answer 2

Avez-vous essayé DFS à approfondissement itéré ?

Answer 3

Approche muette: (la structure de données est un tableau de piles). Cela consiste essentiellement à effectuer une première recherche en largeur (BFS) jusqu'à la profondeur N, sauf que si les boucles sont autorisées (vous n'avez pas précisé, mais je suppose qu'elles le sont), vous n'excluez pas les nœuds visités d'une recherche ultérieure.

1. Poussez le noeud de départ sur une pile stockée dans le tableau à l'index 0 (index = profondeur)

2. Pour chaque niveau / indice "l" 0-N:

   Pour chaque nœud d’une pile stockée au niveau "l", trouvez tous ses voisins et placez-les dans une pile stockée au niveau "l + 1".

   Important: si votre tâche vous permet de rechercher des chemins contenant des boucles, ne vérifiez PAS si vous avez déjà visité le nœud que vous avez ajouté. S'il n'autorise pas les boucles, utilisez un hachage de noeuds visités pour ne pas ajouter deux fois de noeud **

3. Arrêtez-vous lorsque vous terminez le niveau "N-1".

4. Boucle sur tous les noeuds que vous venez d'ajouter pour empiler à l'index "N". et trouvez votre noeud de destination. Si trouvé: succès, sinon, pas de tel chemin.

Veuillez noter que si vous pouvez connecter tous les nœuds, vous devez " vous impliquez un graphe ENTIÈREMENT CONNECTÉ, alors il existe une réponse mathématique n'impliquant pas les nœuds réellement en visite

(cependant, la formule est trop longue pour écrire dans le champ de saisie de texte de StackOverflow)