Vía / carretera por la que un problema

Question

Hoy tenemos una misión para completar en el laboratorio (en dos horas). La pregunta era:

• Que le den una m * n matriz.
• La matriz tiene 'h' salas residenciales y 'b' principales entradas de los edificios.
• se conoce la ubicación de estas salas 'H' y entradas 'b' (en términos de (x, y) coordenadas).
• Es necesario establecer vías de tal manera que cada sala residencial tiene al menos una forma de llegar a una de las entradas 'b'.
• No puede haber a lo sumo 'b' tales vías desconectados.
• La longitud de la vía debe ser mínimo.
• Sólo puede mover hacia arriba, abajo, izquierda o derecha.
• La solución no debe ser un intento de fuerza bruta.

La asignación ha terminado. Pero todavía estoy pensando en cómo podría ser resuelto. ¿Hay un término estándar para este tipo de problemas? ¿Qué debo leer?

qué la gente usa este tipo de algoritmos para sentar las carreteras en las ciudades así?

Answer 1

Esta es una solución que se me ocurrió. No genera caminos desconectados 'b'. Genera un camino que pasa por todos los pasillos residenciales y entradas.

• Calcular la distancia entre cada par de nodos (diferencia de coordenadas X + de diferencia de coordenadas y). Ahora usted tiene un grafo completo.
• Para el MST para esta gráfica completa
• Cada borde inclinado de la MST (aquellos que no son vertical u horizontal) puede ser dividida en dos partes -. La horizontal y la vertical
• Cada división puede hacerse de dos maneras -. Ya sea horizontal primero seguido por verticales o viceversa
• Ir a través de cada uno de tales permutación y calcular la ruta con la menor longitud. Esta es la respuesta.

Answer 2

No se pudo decirle lo que la solución es (una especie de análisis de ruta de coste mínimo, a ojo), pero tengo algo de experiencia con el software de modelado de carreteras.

En un extremo de la escala tiene sistemas de modelado estratégicos que utilizan un enfoque similar (en términos generales). Ellos pueden ser considerados como un modelo de gravedad - que usará las estimaciones de generación de tráfico y demanda para hacer predicciones de alto nivel de los flujos de tráfico entre, por ejemplo, pueblos y ciudades o zonas industriales a residenciales, etc. Esto es sobre todo útil para buscar a los efectos macro de los principales acontecimientos planificados, los cambios en las zonas de distribución de la población o de uso del suelo .. ese tipo de cosas.

En el otro extremo tiene modelos de simulación de áreas específicas de una ciudad, pueblo, intercambio, etc. Estos modelos numéricos se que tratan a cada vehículo como un agente autónomo con factores como la agresividad, el conocimiento de carreteras, y así sucesivamente. Esto es en gran medida un enfoque de estilo de la fuerza bruta, pero es la única manera 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 tráfico modelista puede, por ejemplo, enchufarlo en el datos reales de control de tráfico, corren el modelo para un período específico para un soluciones de diseño específicas y establecen que se ejecute 6 o 7 veces. Los datos resultantes se da una muy buena evaluación de la actuación de una solución particular contra otro (o el status quo).

Espero que esto proporciona un contexto útil.

Answer 3

Hay un aspecto de la descripción del problema que no está claro para mí:

• Cuando dice, "Era necesario colocar una vía", hace que " sólo un ruta conectado?" Media O puede haber múltiples caminos desconectados? (Por ejemplo, un camino de pasillo H1 a la construcción de entrada B1 y un camino separado de sala de H2 a la construcción de B2 entrada)

Pero por su respuesta a mi pregunta, esto es un problema extremadamente complicado: es NP-difícil, ya que incluye la rectilínea Steiner problema árbol como un caso especial (cuando sólo hay una entrada del edificio principal).

Así que nadie sabe cómo resolver de manera eficiente en el caso general!

Answer 4

Creo que el problema es más simple y no el árbol de Steiner o ni siquiera árbol recubridor mínimo.

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

2. Tome conjunto B de las entradas, de las salas de juego de H

3. H '= H / B, B' = B / H (marcar los pasillos que son entradas, que se alcanzan en la profundidad 0, eliminar todas estas entradas como las que son pasillos)

4. Haga un recorrido primero en amplitud. En cada profundidad marcar los pasillos que se puede llegar desde B hasta que todas las salas están marcados. Escoja vías correspondiente.

Answer 5

Se trata de un problema de búsqueda. Se esperaba que hacerlo en 2 horas, ¿verdad? Lo haría DFS y ciruela . Se podría utilizar heurística para llegar a las mejores soluciones rápidas. Pero hay que tener en mente heurística no puede garantizar soluciones óptimas por lo que tendrá a probar todas las posibilidades . Parece ser NP-duro.