Pathway / problème pose route

Question

Aujourd'hui, nous avons eu une mission à remplir dans le laboratoire (en deux heures). La question était:

• Vous avez donné une m * n matrice.
• La matrice a 'h' salles d'habitation et 'b' entrées principales du bâtiment.
• La localisation de ces salles 'h' et 'b' entrées est connue (en termes de (x, y) les coordonnées).
• Vous avez besoin de poser des voies telles que chaque salle d'habitation a au moins un moyen d'atteindre l'une des entrées « b ».
• Il peut y avoir au plus 'b' ces voies déconnectées.
• La longueur de la voie doit être au minimum.
• Vous ne pouvez déplacer vers le haut, vers le bas, à gauche ou à droite.
• La solution ne doit pas être une tentative de force brute.

L'affectation est terminée. Mais je pense encore comment cela serait résolu. Y at-il un terme standard pour de tels problèmes? Que dois-je lire?

Les gens n'utilisent ces algorithmes pour la pose des routes dans les villes aussi bien?

Answer 1

Voici une solution je suis venu avec. Il ne génère pas « b » chemins déconnectés. Il génère un chemin qui passe par toutes les salles d'habitation et les entrées.

• Calculer la distance entre chaque paire de noeuds (différence de coordonnées X + de différence de coordonnées Y). Maintenant, vous avez un graphique complet.
• Trouvez le MST pour ce graphe complet
• Chaque bord incliné de la MST (ceux qui ne sont pas vertical ou horizontal) peut être divisé en deux parties -. L 'horizontale et la verticale
• Chaque séparation peut se faire de deux façons -. Soit horizontale d'abord suivie verticale ou vice versa
• Go par chaque permutation et calculer le chemin le moins long. Ceci est la réponse.

Answer 2

Impossible de vous dire quelle est la solution (une sorte de moindre analyse du chemin des coûts, à une estimation), mais j'ai une certaine expérience avec le logiciel de modélisation de la route.

À une extrémité de l'échelle que vous avez des systèmes de modélisation stratégique qui utilisent une approche similaire (au sens large). Ils peuvent être considérés comme un modèle de gravité - il utilisera les estimations de génération de trafic et de la demande de faire des prévisions de haut niveau des flux de trafic entre, par exemple, les villes ou les zones industrielles à résidentiel, etc. Cela est surtout utile pour la recherche les effets macro des grands développements prévus, les changements dans la répartition de la population ou des zones d'utilisation des terres .. ce genre de chose.

À l'autre extrémité, vous avez des modèles de simulation de zones spécifiques d'une ville, l'échange, etc. Ce sont des modèles numériques qui traitent chaque voiture comme agent autonome avec des facteurs tels que l'agression, la connaissance de la route, et ainsi de suite. Ceci est très bien une approche de style force brute, mais il est le seul moyen de fournir des statistiques utiles sur le comportement du trafic réel dans un réseau complexe avec des fonctionnalités telles que les feux de circulation, les autobus, etc. Un trafic modélisateur peut, par exemple, branchez-le sur la les données de contrôle de la circulation réelle, exécutez le modèle pour une période spécifique pour une des solutions de conception spécifiques et le mettre à courir 6 ou 7 fois. Les données résultantes vous donne une très bonne évaluation de la performance d'une solution particulière contre une autre (ou le statu quo).

Espérons que cela fournit un contexte utile.

Answer 3

Il y a un aspect de la description du problème qui n'est pas clair pour moi:

• Lorsque vous dites: « Vous avez besoin de mettre une voie », que cela veut dire « un seul chemin connecté ? » Ou peut-il y avoir plusieurs chemins déconnectés? (Par exemple, un chemin de couloir H1 à la construction B1 d'entrée et un trajet séparé de la salle à l'entrée H2 construction B2)

Mais cependant vous avez répondu à ma question, cela est un problème extrêmement délicat: il est NP-difficile que cela inclut le rectiligne problème arbre Steiner comme un cas particulier (quand il y a juste une entrée du bâtiment principal).

Alors, personne ne sait comment résoudre efficacement dans le cas général!

Answer 4

Je pense que le problème est plus simple et non l'arbre de Steiner ou même pas l'arbre minimum spanning.

1. représenter la matrice M comme un graphe G avec V = {Mij | i <= m, j <= n}, E = {(Mi1j1, Mi2j2): i1, i2 <= m, j1, j2 <= n, | i1-i2 | = 1 OU exclusif | j1-j2 | = 2}

2. Prendre ensemble B d'entrées, série H de salles

3. H '= H / B, B' = B / H (marquer les salles qui sont entrées, elles sont atteints à la profondeur 0, élimine tous ces entrées comme ce sont des halls)

4. Faites un parcours en largeur. A chaque marque profondeur les salles qui peuvent être accessibles depuis le B jusqu'à ce que toutes les salles sont marqués. Choix des voies correspondantes.

Answer 5

Il est un problème de recherche. Vous étiez censé le faire en 2 heures, non? Je voudrais DFS et élaguer . Vous pouvez utiliser heuristiques pour obtenir les meilleures solutions plus rapides. Mais gardez à l'esprit heuristiques ne peut pas garantir des solutions optimales pour que vous aurez à essayer toutes les possibilités . Semble être NP-dur.