créer une fonction de coût dans jgrapht

Question

jgrapht supporte l'idée de mettre un wehight (un coût) sur un front/sommet entre deux nœuds. Cela peut être réalisé en utilisant la classe DefaultWeightedEdge.

Dans mon graphique, j'ai l'obligation de ne pas trouver le chemin le plus court mais le moins cher. Le chemin le moins cher peut être plus long/avoir plus de nœuds de houblon à parcourir que le chemin le plus court. Pour cela, on peut utiliser l'algorithme DijkstraShortestPath.

Cependant, mon cas d'utilisation est un peu plus complexe: il doit également évaluer les coûts des actions qui doivent être exécutées lors de l'arrivée à un nœud. Disons que vous avez un graphique comme un échiquier (8x8 champs, chaque champ étant un noeud). Toutes les arêtes ont un poids de 1. Pour se déplacer dans une voiture du bas à gauche au coin diagonal (en haut à droite), il y a beaucoup de chemins avec le coût de 16. Vous pouvez prendre un chemin en diagonale dans un style zic zac, ou vous peut d'abord parcourir tous les nœuds vers la droite, puis tous les nœuds vers le haut. La différence est la suivante: Lorsque vous prenez un zic zac, vous devez vous tourner dans le sens du déplacement. Vous faites pivoter 16 fois. Lorsque vous déplacez tout d'abord vers la droite puis vers le haut, vous devez effectuer une seule rotation (peut-être deux fois, en fonction de votre orientation de départ). Ainsi, le chemin zic zac est, d'un point de vue Djikstra, parfait. D'un point de vue logique, c'est le pire.

Longue histoire courte: Comment puis-je mettre des coûts sur un nœud ou un bord en fonction du bord/nœud précédent dans ce chemin? Je n'ai rien trouvé dans le code source de jgrapht. Ou y a-t-il un meilleur algorithme à utiliser?

Answer 1

Il ne s'agit pas d'un problème JGraphT mais d'un problème d'algorithme de graphique. Vous devez penser à la façon de coder ce problème et de formaliser cela plus en détail

1. L'intégration des poids sur les sommets est en général facile. Dites que chaque sommet représente la visite d'un client, ce qui prend du temps. Cela peut être codé dans le graphique en ajoutant a_i/2 au coût de chaque arc entrant dans le nœud i, ainsi que a_i/2 au coût de chaque arc sortant.

2. Une fonction de coût où le coût de déplacement de j à k dépendant de l'arc (i, j) que vous aviez l'habitude de parcourir jusqu'à j est plus compliqué.

Approche a .: Utiliser un algorithme de programmation dynamique (étiquetage). C'est peut-être le plus facile. Vous pouvez définir votre fonction de coût comme une fonction récursive, où le coût de la traversée d'un arc dépend du coût de l'arc précédent. Approche b: Avec quelques astuces, vous pouvez encoder les coûts dans le graphique en y ajoutant des nœuds supplémentaires. Voici un exemple:

Étant donné un graphique avec sommets {a, b, c, d, e}, avec des arcs: (a, e), (e, b), (c, e), (e, d). Ce graphique représente un carrefour avec le sommet e étant au milieu. Aller de a-> e-> b (droite) est libre, cependant, un tour de a-> e-> d prend plus de temps. Semblable pour c-> e-> d (droite) est libre et c-> e-> b (virage) devrait être pénalisé. Découple le sommet e dans 4 nouveaux sommets: e1, e2, e3, e4. Ajouter les arcs suivants: (a, e1), (e3, b), (c, e2), (e4, d), (e2, e3), (e1, e3), (e1, e4), (e2, e4). (e1, e4) et (e2, e3) peuvent avoir un poids positif pour pénaliser le virage.