Vous pourriez commencer par l'exécution d'un algorithme de Dijkstra normale si vous savez ce que l'itinéraire le plus rapide est que vous savez quand la route la plus sûre dépasse ce coût par un facteur.
Vous pouvez ensuite l'exécuter à nouveau avec la sécurité comme fonction de coût principale, mais également calculer les distances pour exclure certaines routes. Au début, j'ai pensé que cela pourrait être fait comme l'algorithme de Dijkstra normal mais en stockant une liste ordonnée pour chaque nœud (nœud précédent, coût, et valeur de sécurité). Le problème avec ceci est que la distance et la sécurité sont apparemment indépendantes (en réalité il y a une sorte de corrélation mais pas une que nous savons modéliser). C'est un problème car vous devez éviter de longues distances au début de la route, ce qui vous conduit à rejeter les options plus tard dans la route.
Cela ne pose pas de problème si vous pouvez appliquer la limite de distance sur des routes partielles. C'est-à-dire que vous n'acceptez pas de route vers un nœud intermédiaire s'il est plus long que deux fois l'itinéraire le plus court depuis le début jusqu'à ce nœud. Je sais que ce n'est pas exactement comme vous l'avez dit parce que vous avez demandé de limiter la longueur de la route au nœud final, mais peut-être que cela vous aide encore à réfléchir à la solution globale. Pour ce que cela vaut, il pourrait aussi être plus réaliste. N'oubliez pas de combiner la probabilité de collision correctement, vous ne pouvez pas simplement l'ajouter. Si nous supposons que le voyage s'arrête au premier crash, alors vous calculeriez la probabilité de l'accident comme probabilité de crash sur la route 1 plus (probabilité de ne pas s'écraser sur la route 1 * probabilité de s'écraser sur route 2) plus (probabilité d'obtenir à la route 3 en toute sécurité * probabilité d'accident sur la route 3) etc (désolé si c'est évident).
Compte tenu de votre commentaire, je vais vous expliquer plus sur la probabilité (et il est probable et non chances que vous seriez mieux regardant)
Si vous voulez une mesure globale de la sécurité qui a permis Continuant après un crash, il devient plus complexe. Si vous arrêtez quand il y a un accident, il s'agit de calculer la probabilité de s'écraser exactement une fois. Ainsi, un itinéraire a un accident si:
vous avez un accident sur la première route (probabilité p1) OU
vous ne brisez pas sur la première route (probabilité 1-p1), mais vous ne heurtez au deuxième (probabilité p2). OU
... vous ne tombe pas en panne sur les routes n-1 (1 total cumulé comme ci-dessus) mais vous accident sur la route n (pn probabilité)
Cette façon, vous ne recevez pas les cas où une probabilité de 50% de s'écraser sur les routes 1 & 2 ne donne pas 100% de chances - et vous ne pourriez jamais obtenir plus que cela non plus. En réalité, de nombreux accidents se produisent aux carrefours, et la probabilité de collision varie selon que vous tournez à gauche ou à droite, de sorte que la probabilité n'est pas (en réalité) simplement dépendante du facteur de sécurité des routes entre ces deux carrefours. les jonctions mais aussi comment la route les combine. Les probabilités devraient être pondérées en fonction de l'utilisation (probabilités conditionnelles de recherche), donc s'il y avait 20 accidents sur une route rarement utilisée, il pourrait être nécessaire de modéliser une probabilité d'accident plus élevée en tant que route occupée avec 50 accidents dans la même route. période de temps.
Pouvez-vous utiliser le pourcentage de crash pour ajuster les poids de l'algorithme de Dijkstra? Je veux dire une modification comme la simple multiplication de ce pourcentage en poids pour obtenir un nouveau poids. –
Hmm je suppose que cela fonctionnerait. Supposons que le chemin le plus rapide entre deux nœuds a une distance de 200. Supposons que la distance entre les routes les plus sûres soit 300, mais que le pourcentage d'accident est de 0,6%, 300 * 0,6 le fera 180 de distance. Cela a du sens pour moi si c'est ce que vous avez trouvé – squish
oui, et avant de changer les poids, vous pouvez exécuter Dijkstra de sorte que plus tard, vous pouvez vérifier par rapport à l'exigence de temps doublé. –