¿Existe un algoritmo bien conocido que complete la cuadrícula debido a un conjunto de puntos?

Question

Vi este juego aquí Flow, se ve bastante interesante.

Conecte los colores correspondientes con la tubería para crear un flujo. Empareje todos los colores, y cubra todo el tablero para resolver cada rompecabezas. Pero cuidado, las tuberías se romperán si se cruzan o se superponen.

Dado un conjunto de pares (x, y), ¿existe un algoritmo para resolver el puzzle, es decir, llenar el total de la rejilla (suponiendo que hay una solución) que no soy consciente de?

Answer 1

Este es un ejemplo muy específico del problema global de enrutamiento. El enrutamiento global es un problema bien estudiado en VLSI CAD (donde uno necesita enrutar millones de redes en un circuito integrado). El problema es NP-completo y puede resolverse de muchas maneras, dependiendo de la compensación que necesite entre el tiempo de ejecución y la calidad. Después de wiki es un buen punto de partida:

http://en.wikipedia.org/wiki/Routing_(electronic_design_automation)

papel que aquí se ofrece un panorama de las diversas técnicas:

http://dropzone.tamu.edu/~jhu/publications/HuIntegration01.pdf

tener en cuenta que los punteros que había dado por lo general tratan de resolver una versión mucho más compleja del problema que usted había declarado. No obstante, los conceptos matemáticos siguen siendo los mismos.