Problema de tendido del camino/camino

Question

Hoy recibimos una tarea para completar en el laboratorio (en dos horas). La pregunta era:

• Te dan una matriz m * n.
• La matriz tiene 'h' salas residenciales y 'b' entradas principales del edificio.
• La ubicación de estas 'h' salas y 'b' entradas es conocida (en términos de coordenadas (x, y)).
• Necesita establecer vías para que cada sala residencial tenga al menos una forma de llegar a una de las 'b' entradas.
• Puede haber como máximo 'b' tales vías desconectadas.
• La longitud de la ruta debe ser mínima.
• Solo puede moverse hacia arriba, abajo, izquierda o derecha.
• La solución no debe ser un intento de fuerza bruta.

La tarea ha terminado. Pero todavía estoy pensando cómo se resolvería esto. ¿Hay un término estándar para tales problemas? ¿Qué debería leer?

¿La gente usa tales algoritmos para colocar carreteras en las ciudades también?

Answer 1

Aquí hay una solución que se me ocurrió. No genera 'b' rutas desconectadas. Genera un camino que pasa por todas las salas y entradas residenciales.

• Calcule la distancia entre cada par de nodos (diferencia de coordenadas X + diferencia de coordenadas Y). Ahora tienes un gráfico completo.
• Encuentra el MST para este gráfico completo
• Cada borde inclinado del MST (los que no son verticales u horizontales) se puede dividir en dos partes: la horizontal y la vertical.
• Cada división se puede hacer de dos maneras: horizontal primero seguido de vertical o viceversa.
• Pase a través de cada permutación y calcule la ruta con la menor longitud. Esta es la respuesta.

Answer 2

No pude decirle cuál es la solución (algún tipo de análisis de ruta de menor costo, supongo), pero tengo cierta experiencia con el software de modelado de carreteras.

En un extremo de la escala tiene sistemas de modelado estratégico que utilizan un enfoque similar (en términos generales). Pueden considerarse como un modelo de gravedad: utilizará estimaciones de la generación y demanda de tráfico para hacer predicciones de alto nivel de los flujos de tráfico entre, por ejemplo, pueblos y ciudades, o áreas industriales a residenciales, etc. Esto es principalmente útil para buscar en los efectos macro de grandes desarrollos planificados, cambios en la distribución de la población o zonas de uso de la tierra ... ese tipo de cosas.

En el otro extremo tiene modelos de simulación de áreas específicas de una ciudad, ciudad, intercambio, etc. Estos son modelos numéricos que tratan a cada automóvil como un agente autónomo con factores como agresión, conocimiento de caminos, etc. Este es un enfoque de estilo de fuerza bruta, pero es la única forma de proporcionar estadísticas útiles sobre el comportamiento real del tráfico en una red compleja con características como semáforos, autobuses, etc. Un modelador de tráfico puede, por ejemplo, conectarlo al datos reales de control de tráfico, ejecute el modelo por un período específico para soluciones de diseño específicas y configúrelo para que se ejecute 6 o 7 veces. Los datos resultantes le dan una muy buena evaluación del rendimiento de una solución particular frente a otra (o el status quo).

Espero que esto proporcione un contexto útil.

Answer 3

Hay un aspecto de la descripción del problema que no está claro para mí: "? ruta sólo una conectado"

• Cuando dice, "Era necesario colocar una vía", quiere decir eso ¿O puede haber múltiples caminos desconectados? (Por ejemplo, un camino de pasillo H1 a la entrada del edificio B1 y un camino separado de sala de H2 a la construcción B2 entrada)

Pero por su respuesta a mi pregunta, esto es un problema extremadamente complicado: es NP-difícil, ya que incluye el problema rectilinear Steiner tree como un caso especial (cuando solo hay una entrada principal del edificio).

¡Así que nadie sabe cómo resolverlo eficientemente en el caso general!

Answer 4

Creo que el problema es más simple y no es el árbol de Steiner ni siquiera el mínimo árbol de expansión.

1. Representar matrix M como un gráfico G con V = {Mij | i < = m, j < = n}, E = {(Mi1j1, Mi2j2): i1, i2 < = m, j1, j2 < = n, | i1-i2 | = 1 exclusivo O | j1-j2 | = 2} conjunto

2. Take B de entradas, establezca H de las salas de

3. H '= H/B, B' = B/H (marcar los pasillos que son entradas, que se alcancen en la profundidad 0 , elimine todas estas entradas, ya que esas son salas)

4. Haga un recorrido transversal de ancho. En cada profundidad, marque los pasillos a los que se puede acceder desde B hasta que todos los pasillos estén marcados. Elija las vías correspondientes.

Answer 5

Es un problema de búsqueda. Se esperaba que lo hicieras en 2 horas, ¿verdad? Me gustaría DFS y podar. Puede usar heuristics para obtener las mejores soluciones más rápido. Pero tenga en cuenta que la heurística no puede garantizar soluciones óptimas, por lo que tendrá que probar todas las posibilidades. Parece ser NP-difícil.