Recientemente, mientras hacía mi diploma, surgieron algunas preguntas 1) ¿Se puede usar mi solución en el diseño de chips? Como se sabe, es importante conectar diferentes capas de manera efectiva, así que ¿puede mi problema encontrar MSF (bosque de expansión mínima) útil para reducir el costo del metal, aumentar el tiempo de flujo de la corriente y quizás para otros problemas? 2) ¿Pueden las vías, que conectan diferentes capas, ser horizontales?
Aquí está el problema de py La ciudad se presenta como una cuadrícula de cuadrados. Cada edificio ocupa un conjunto conectado de una o más plazas. Dos plazas ocupadas cuyas esquinas se tocan se consideran un solo edificio y no necesitan un puente. Los puentes se pueden construir solo en las líneas de la cuadrícula que forman los bordes de los cuadrados. Cada puente debe construirse en línea recta y debe conectar exactamente dos edificios. Para un conjunto dado de edificios, necesitamos encontrar el número mínimo de puentes necesarios para conectar todos los edificios, minimizar la suma de las longitudes de los puentes y el número de grupos de edificios desconectados. Dos puentes pueden cruzarse, pero en este caso se considera que están en niveles separados y no proporcionan una conexión de un puente a otro.
