Traiter les graphiques massifs - Vendeur itinérant

Question

Je suis en train d'apprendre à programmer des algorithmes impliquant des TSP (Djikstra, Kruskal) et je cherche des conseils pour démarrer. Je travaille avec C# et SQL. Idéalement, j'aimerais pouvoir faire cela strictement en SQL, mais je ne suis pas sûr que cela soit possible (je suppose que le temps d'exécution serait terrible après 50 sommets).

Je suppose donc que la question est la suivante : puis-je faire cela avec seulement SQL et si oui, quelle est la meilleure approche ? Si ce n'est pas le cas, et que je dois faire appel à C#, quelle serait la meilleure approche ?

Answer 1

Il est seulement conseillé d'effectuer des calculs simples en SQL, comme le calcul de sommes. Les sommes sont plus rapides en SQL, car seules les sommes sont retournées au lieu de tous les enregistrements. Les algorithmes compliqués comme ceux que vous avez en tête doivent être réalisés dans votre code c# ! Premièrement, le langage SQL n'est pas adapté à de tels problèmes, deuxièmement, il est optimisé pour les accès aux bases de données, ce qui le rend très lent pour d'autres types d'utilisations.

Lisez vos données à partir de votre base de données avec SQL dans une structure de données appropriée dans votre programme c#. Faites toute la logique liée au TSP et, si vous le souhaitez, stockez le résultat dans la base de données, une fois terminé.

Answer 2

Je ne suis pas sûr que SQL soit la meilleure option pour y parvenir, mais vous pouvez essayer d'utiliser une matrice d'adjacence comme entrée. De nombreux algorithmes publiés sont conçus pour ce type d'entrée, et après cela, le seul problème est de mettre le pseudocode en C#. Jetez un coup d'œil à ceci : http://en.wikipedia.org/wiki/Adjacency_matrix .

Vous utiliseriez un tableau à deux dimensions pour représenter la matrice.

Answer 3

Je vais intervenir pour SQL. Bien qu'il ne soit pas vraiment mon premier choix pour travailler sur TSP, il peut facilement faire ce genre de choses - en supposant bien sûr que le modèle de données est optimal pour vos efforts.

La première tâche consistera à définir un modèle de données contenant les informations dont votre algorithme a besoin, puis à l'alimenter avec des échantillons de données, et enfin à élaborer une requête capable de récupérer les tableaux selon les besoins.

Enfin, vous pouvez décider si un simple SQL dans cette requête vous conviendrait, ou peut-être une extension sous la forme d'une procédure stockée.

enfin, vous pouvez choisir de l'extraire vers la langue alternative de votre choix.