Problème de pose de chemin/route

Question

Aujourd'hui, nous avons eu une tâche à accomplir en laboratoire (en deux heures). La question était:

• On vous donne une matrice m * n.
• La matrice a des halls résidentiels «h» et des entrées de bâtiment principal «b».
• L'emplacement de ces halls 'h' et 'b' est connu (en termes de coordonnées (x, y)).
• Vous devez aménager des voies de sorte que chaque hall résidentiel ait au moins un moyen d'atteindre l'une des entrées «b».
• Il peut y avoir au plus «b» de telles voies déconnectées.
• La longueur de la voie doit être minimale.
• Vous ne pouvez déplacer que vers le haut, le bas, la gauche ou la droite.
• La solution ne doit pas être une tentative de force brute.

L'affectation est terminée. Mais je pense toujours à la façon dont cela serait résolu. Existe-t-il un terme standard pour de tels problèmes? Que devrais-je lire?

Est-ce que les gens utilisent de tels algorithmes pour poser des routes dans les villes?

Answer 1

Voici une solution que j'ai trouvée. Il ne génère pas de 'b' chemins déconnectés. Il génère un chemin qui traverse toutes les salles résidentielles et les entrées.

• Calculez la distance entre chaque paire de nœuds (différence de coordonnées X + différence de coordonnées Y). Maintenant, vous avez un graphique complet.
• Trouver le MST pour ce graphique complet
• Chaque bord incliné du MST (ceux qui ne sont pas verticaux ou horizontaux) peut être divisé en deux parties - l'horizontale et la verticale.
• Chaque division peut être faite de deux manières - soit d'abord d'abord horizontalement puis verticalement ou vice versa. Parcourez chacune de ces permutations et calculez le chemin de moindre longueur. C'est la réponse.

Answer 2

Je ne peux pas vous dire quelle est la solution (une sorte d'analyse de chemin de moindre coût, à supposer), mais j'ai une certaine expérience avec le logiciel de modélisation routière. À une extrémité de l'échelle, vous disposez de systèmes de modélisation stratégiques qui utilisent une approche similaire (au sens large). Ils peuvent être considérés comme un modèle gravitaire - ils utiliseront des estimations de la génération et de la demande de trafic pour faire des prédictions de haut niveau des flux de trafic entre, par exemple, les villes et les villes, ou résidentielles, etc. aux effets macro-économiques des grands aménagements planifiés, aux changements dans la répartition de la population ou dans les zones d'utilisation des terres ... ce genre de choses. À l'autre extrémité, vous avez des modèles de simulation de zones spécifiques d'une ville, d'une ville, d'un échangeur, etc. Ce sont des modèles numériques qui traitent chaque voiture comme un agent autonome avec des facteurs comme l'agression, la connaissance routière, etc. C'est une approche de type force brute, mais c'est la seule façon de fournir des statistiques utiles sur le comportement de trafic réel dans un réseau complexe avec des fonctionnalités telles que feux de circulation, bus, etc. Un modélisateur de trafic peut, par exemple, données réelles de contrôle du trafic, exécutez le modèle pour une période spécifique pour des solutions de conception spécifiques et réglez-le pour exécuter 6 ou 7 fois. Les données qui en résultent vous donnent une très bonne évaluation de la performance d'une solution particulière par rapport à 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: « juste un chemin connecté »

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

Mais si vous répondez à ma question, c'est un problème extrêmement délicat: il est NP-difficile que cela comprend le problème rectilinear Steiner tree comme cas spécial (quand il n'y a qu'une seule entrée principale du bâtiment).

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

Answer 4

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

1. Représentez 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-exclusif OU | j1-j2 | = 2}

2. Take ensemble B d'entrées, ensemble H des salles

3. H '= H/B, B' = B/H (marquer les salles qui sont entrées, elles sont atteintes à la profondeur 0 , supprimez toutes ces entrées car ce sont des halls)

4. Effectuez une traversée en largeur. À chaque profondeur, marquez les halls qui peuvent être atteints de B jusqu'à ce que toutes les salles soient marquées. Choisissez les voies correspondantes.

Answer 5

Il s'agit d'un problème de recherche. Vous étiez censé le faire en 2 heures, non? Je voudrais DFS et élague. Vous pouvez utiliser heuristiques pour obtenir les meilleures solutions plus rapidement. Mais gardez à l'esprit que les heuristiques ne peuvent pas garantir des solutions optimales, donc vous devrez essayer toutes les possibilités . Semble être NP-difficile.