algorithme de correspondance

Question

question Odd ici pas de code vraiment mais la logique, espère son ok pour poster ici, ici il est

J'ai une structure de données qui peut être considéré comme un graphique. Chaque nœud peut prendre en charge de nombreux liens, mais est limitée à une valeur pour chaque noeud. Tous les liens sont bidirectionnels. et chaque lien a un coût. le coût dépend de la différence euclidienne entre les noeuds, la valeur minimum de deux paramètres dans chaque noeud. et un modificateur global.

Je souhaite trouver le coût maximal pour le graphique.

se demander s'il y avait un moyen intelligent de trouver une telle correspondance, plutôt que de passer par la force brute en ... ce qui est laid ... et je ne sais pas comment je dirais même le faire sans dépenser 7 millions d'années l'exécuter.

Pour préciser:

Global variable = T
many nodes N each have E,X,Y,L
L is the max number of links each node can have.
cost of link A,B = Sqrt(  min([a].e | [b].e)  ) x 
     ( 1 + Sqrt( sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10 )


total cost =sum all links.....and we wish to maximize this.

valeurs moyennes pour les noeuds est de 40-50 peut aller à (20..600) noeud moyen facteur de liaison est 3 gamme de 0-10.

Answer 1

Si je comprends bien le problème, il n'y a probablement pas de solution polynomiale. Par conséquent, je mettre en œuvre l'algorithme suivant:

1. Trouver une solution par Beng gourmand . Pour ce faire, vous trier tous bords par le coût, puis passez par les en commençant par le plus haut, en ajoutant un bord à votre graphique tout possible, et à sauter lorsque le noeud ne peut pas accepter plus arêtes.
2. Regardez vos bords et essayer de les changer pour archiver des coûts plus élevés en utilisant un heuristiques . Le premier qui me vient à l'esprit: vous faire défiler les 4 triplets de noeuds (A, B, C, D) et si votre graphique actuelle a des bords AB, CD, mais AC, BD serait mieux, vous faire le changement.
3. En option, la même chose avec 6 triplets, ou d'autres (ils sont appelés ainsi parce qu'ils travaillent par des mutations) algorithmes génétiques .

Answer 2

Par souci d'exhaustivité pour toute autre personne qui regarde cet article, je vous suggère de revoir vos algorithmes de la théorie des graphes:

• Dijkstra
• Astar
• Greedy
• Profondeur / largeur d 'abord
• Même la programmation dynamique (dans certaines situations)
• ect. ect.

il y a quelque part la bonne solution pour votre problème. Je suggère regarder Dijkstra d'abord.

J'espère que cela aide quelqu'un.

Answer 3

Ceci est équivalent au problème du voyageur de commerce (et est donc NP-complet) car si vous pouvez résoudre ce problème efficacement, vous pouvez résoudre TSP simplement en remplaçant chaque coût par sa réciproque.

Cela signifie que vous ne pouvez pas résoudre exactement. D'autre part, cela signifie que vous pouvez faire exactement comme je l'ai dit (remplacer chaque coût par sa réciproque) et ensuite utiliser l'une des méthodes d'approximation TSP connues sur ce problème.

Answer 4

On dirait un problème de débit max pour moi.

Answer 5

Est-il possible qu'en choisissant avidement l'option suivante le plus cher de tout point de départ donné (sauts à nœuds en omettant visités) et arrêter une fois tous les noeuds sont visités? Si vous arrivez à un retour en arrière d'impasse à l'endroit précédent, où vous n'êtes pas dans une impasse et que vous sélectionnez avidement. Il faudrait un peu de travail et probablement quelque chose comme une pile pour garder vos chemins. Je pense que cela fonctionnerait de façon très efficace à condition que les coûts sont bien commandés et non négatif.

Answer 6

Utiliser les algorithmes génétiques. Ils sont conçus pour résoudre le problème, vous déclarez réduire rapidement la complexité du temps. Vérifiez la bibliothèque AI dans votre langue de choix.