Théorie des graphes - Remplir des nœuds avec un nombre limité de routes

Question

D'abord, je dois dire que ce n'est pas un devoir ou quelque chose lié, c'est un problème d'un jeu nommé (freeciv). Ok, dans le jeu, nous avons généralement un nombre de villes (8-12), chaque ville peut avoir un nombre maximum de routes commerciales de k (4), et ces routes commerciales ont besoin être 'd' distance ou plus loin (8 tuiles Manhattan). Le problème consiste à trouver les k * n trade-routes avec (distances max ou distances min), évidemment ce problème peut être résolu avec un algorithme de force brute mais il est vraiment lent quand vous avez plus de 10 villes parce que le programme doit faire plusieurs itérations; J'ai essayé de le résoudre en utilisant la théorie des graphes, mais je ne suis pas un expert, j'ai même demandé à certains de mes professeurs et aucun ne pouvait m'expliquer un algorithme intelligent, donc je ne suis pas venu ici pour trouver la solution exacte. fait pour avoir l'idée ou les étapes pour analyser cela.

Answer 1

Le problème comporte deux parties:

1. Calculer des distances par paire entre les villes
2. Sélectionnez les paires devraient devenir le commerce route

Je ne pense pas que la première partie peut être calculée plus rapidement que O (n · t) où t est le nombre de tuiles, car chaque exécution de l'algorithme de Dijkstra vous donnera des distances d'une ville à toutes les autres villes. Cependant si je comprends bien, la distance entre deux villes ne change jamais et est symétrique. Donc, chaque fois qu'une nouvelle ville est construite, il suffit d'exécuter l'algorithme de Dijkstra et de mettre en cache les distances.

Pour la deuxième partie je m'attendrais à ce que l'algorithme glouton fonctionne. Ordonner toutes les paires de villes par pertinence et à chaque étape choisir le premier qui ne viole pas la contrainte de k itinéraires par ville. Je ne suis pas sûr que cela puisse être prouvé (la preuve devrait être similaire à celle pour Kruskal's minimal spanning-tree algorithm si elle existe.) Mais je suppose que cela fonctionnera bien dans la pratique même si vous trouvez que cela ne fonctionne pas en théorie (je n'ai pas essayé . prouver ou réfuter, il est à vous)

Answer 2

continuent @Jan Hudec chemin:

Init étape:
permet de dire que vous avez des villes N (c1, c2, ... cN) vous devriez Construire une liste de connexions lorsque chaque entité de la liste aura un format de (cX, cY, Distance) (tandis que X < Y, c'est n^2/2 temps) et l'ordonner par distance (décroissant pour la distance maximale ou ascendante pour min distance), et vous devriez également avoir un tableau/liste qui tiendra le numéro de connexion ion par ville (cZ = W) qui a initialisé pour chaque ville à N-1 car ils se sont tous connectés au début.

Itérations: itérer sur les listes de connexions pour chaque (cx, cy, D) si le nombre de connexion (dans la matrice de numéro de connexion) de cX> k et Cy> k puis supprimer (cx, cy, D) à partir de la liste de connexion et décrète également par une la valeur de cX et cY dans le tableau de connexion. En fin de compte, vous aurez la liste de connexion avec la valeur que vous souhaitez.