Comment concevoir une solution de chemin approximatif?

Question

Je tente d'écrire (ou de développer un algorithme de recherche de graphes existant) qui me permettra de trouver le chemin le plus proche du nœud de destination, étant donné qu'il n'y a aucune garantie que les nœuds seront connectés.

Pour donner une application réaliste, disons que je dois me rendre de Brampton, en Ontario, à Hamilton, en Ontario. Je sais que mes options possibles à mon point de départ sont le transport local, le bus GO ou la marche. Je sais que marcher est la façon la moins désirée d'arriver à destination, alors je regarde d'abord le bus GO. Je sais que je peux emmener GO à un point proche de Hamilton, mais à ce moment-là, le bus GO tourne et va dans une autre direction au point le plus proche est à un endroit où je n'ai pas d'options. Pour les courtes distances, sinon l'itinéraire sera considéré comme impossible)

En utilisant ce même exemple, si l'algorithme devait trouver que je peux y arriver d'une manière plus longue mais qui me rapproche du nœud de destination (ou possible à la nœud de destination) qui serait un chemin pondéré plus élevé (Les pondérations n'ont pas tellement d'importance pendant la recherche, seulement lorsque les résultats sont délivrés, ils indiqueraient par quel chemin était le plus proche de la destination dans l'ordre croissant). Par exemple, un autobus GO peut me faire 3 km du noeud de destination, alors que 3 bus de transport en commun me faire 500 m

Donc, ma question est double: 1) Quel algorithme dois-je commencer avec ce fait quelque chose similaire 2) Comment puis-je expliquer programmaticly que c'est ok si les nœuds ne se connectent pas qu'il ne saute pas seulement du noeud A au noeud R. Plût à partir de la fin et de travail accomplir en arrière cette

Edit: I oublié de demander comment viser la meilleure solution approximative, car en particulier avec un grand graphique, il y aura probablement des millions de solutions à ce problème.

Merci, Michael

Answer 1

Dans le monde réel, ils sont normalement, c'est-à-dire que vous pouvez toujours marcher ou appeler un taxi, etc.

Dans ce cas, vous pouvez simplement changer votre modèle de la manière suivante: Vous avez un graphique pour chaque méthode de transport. Les noeuds qui se trouvent au même endroit sont connectés avec des arêtes de poids 0 (c'est-à-dire si vous êtes déposé en voiture dans un aéroport ou une gare).

Ensuite, étiquetez chaque sommet et bord avec le type de transport et vous pouvez simplement utiliser les algorithmes de routage existants. Oh, au fait: A * ne s'adapte pas bien aux très gros réseaux. Pour obtenir quelque chose qu'un logiciel comme Yahoo/Google/Microsoft Maps utiliserait, regardez here. Le travail de ce groupe de recherche comprend le gagnant du DIMACS shortest path challenge.

Answer 2

Lire sur le A* algorithm. C'est une généralisation de l'algorithme de plus court chemin de Dijkstra, qui vous permet de spécifier une heuristique, qui fournit une limite inférieure pour les distances entre deux verteces. Dans votre cas, la fonction heuristique retournerait simplement la distance euclidienne.

Exécutez l'algorithme et gardez une trace du sommet avec la meilleure valeur caractéristique, que vous calculez d'une manière ou d'une autre à partir de la distance du graphique de la distance source et euclidienne à la cible. La seule partie délicate est de déterminer quand terminer (sauf si vous voulez traverser le graphe entier).

Answer 3

Cela ressemble beaucoup à un problème travelling salesman avec des caractéristiques de nœud supplémentaires. Juste se méfier que ce type de problème est NP Complete et votre meilleur pari serait d'aller avec une sorte d'algorithme d'approximation. Pourquoi ne pouvez-vous pas supposer que tous les nœuds sont connectés?