Dev Faq
9
votes

Algorithme de chemin K-shordest (alternative), implémentations Java

Pourriez-vous recommander une bibliothèque Java qui implémente l'algorithme K-Shi-shirt -> Recherche de manière alternative, pas la seule la seule la plus courte dans MultiCraph?

Je n'ai trouvé que JGRAPHT, mais il y a en réalité un bug (que j'ai soumis) mais il faudra beaucoup de temps pour le réparer, je suppose, y a-t-il d'autres implémentations disponibles? Sauf jgrapht je n'ai trouvé que de petits projets uniques: /

ou serait difficile de modifier Disjktra Le chemin le plus court alg pour afficher des chemins alternatifs?

merci

1 commentaires

Êtes-vous intéressé par k -Shortest Edge Disjoint ou nœud disjoint chemins? Pour la première fois, regardez dans les algorithmes de flux MIN coûteux.

3 Réponses :

0
votes

Il y a eu une demande similaire auparavant, mais à la recherche de tous les chemins sur Stackoverflow. Trouvez tous les chemins dans un graphique avec DFS

J'espère que cela aide, il a été répondu mais non avec la solution exacte, mais plus d'un guide

0 commentaires
5
votes

2 options possibles:

Option 1. Le Classe KshortestPath de Le paquet MASCOPT est une bonne option pour une implémentation Java de chemins K-Les plus courts.

Option 2. Vous pouvez également essayer ceci à partir de code.google.com Cela semble être un effort d'une personne, mais la bonne chose est que l'algorithme est partagé: le classement de Yen - les détails sont ici. ( http://www.ohloh.net/p/k-shortest-Paths )

note : la recherche des chemins les plus courts entre toutes les paires de nœuds dans un graphique donné est un problème différent. Voir cette question sur Dijkstra vs. Floyd-Warshall .

Notez également que les chemins K-K-shordest pour des graphiques riches ont tendance à être légères variations du chemin le plus court (DIJKSTRA) - des chemins alternatifs entre les sommets sur le chemin le plus court avec des coûts légèrement supérieurs.

Je sais que l'OP a demandé l'OP pour les implémentations Java, mais si les gens ont un choix et que R est une option, alors le kbestshortestpaths paquet de Cran est une très bonne option également.

espère que cela aide.

1 commentaires

Je viens d'essayer l'option 2: l'algorithme de Yen et ça fonctionnait des merveilles! Heure d'exécution pour un graphique avec ~ 400 nœuds ~ 1000 liaisons est descendue de 3000 ms (pour la mise en œuvre de JGRAPHT) à 0,3 ms pour la mise en œuvre de l'algorithme d'yen. Ouais, 3000 -> 0.3. Ce n'est pas une faute de frappe.

2
votes

Rechercher les chemins K-shordest sont liés mais pas le même problème que les chemins alternatifs. Les bons chemins alternatifs sont plus compliqués. avoir une lecture où d'autres approches similaires sont décrites:

  • Les chemins K-shordest K / Li>
  • Pareto Optimalité
  • Méthode Plateau
  • approche de pénalité

    La méthode Plateau est un peu illustrée ici .

    S'il vous est possible de lire l'allemand, alors Cette conférence est belle :

    • E.g. Optimisation concernant le temps ou la distance => Problème: Les alternatives intéressantes sont manquantes
    • chemins dijuncts => même problème
    • k-paths k-shordest => Problème: la vraie alternative n'est probablement pas sous les 1000 premiers chemins

      Page 5

      Si l'intuition nous dit: une alternative doit avoir une distance ou une durée presque identique. mais devrait être différent significatif. Donc, la première idée: Trouvez un chemin qui minise la longueur et la similarité. Problème: Il pourrait y avoir des détours locaux.

      Page 6

      Nous introduisons un 3ème critère: optimumité locale : chaque sous-path court doit être un chemin le plus court.

0 commentaires

Articles qui pourrait vous intéresser :

Comment envoyer une liste vide à la clause IN
Code de réponse 403 inattendu lors de la récupération des données des API
Impossible de trouver la classe UnityPlayerActivity dans com.unity3d.player
Comment définir un tableau dans jsonobject