Esiste un algoritmo ben noto che inserisce nella griglia un insieme di punti?

Question

Ho visto questo gioco qui Flow, sembra piuttosto interessante.

Collegare i colori corrispondenti con il tubo per creare un flusso. Accoppia tutti i colori, e per coprire l'intera scheda per risolvere ogni enigma. Ma attenzione, i tubi si interromperanno se si incrociano o si sovrappongono.

Dato un insieme di coppie (x, y), c'è un algoritmo per risolvere il puzzle, cioè riempire l'intera griglia (supponendo c'è una soluzione) che non sono a conoscenza di?

Answer 1

Questo è un esempio molto specifica del problema di routing globale. Il routing globale è un problema ben studiato in VLSI CAD (dove è necessario instradare milioni di reti in un circuito integrato). Il problema è NP-completo e può essere risolto in molti modi a seconda del compromesso necessario tra runtime e qualità. A seguito di wiki è un buon punto di partenza:

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

carta qui fornisce una panoramica delle diverse tecniche:

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

Tenete a mente che i puntatori avevo dato in genere cercano di risolvere un versione molto più complessa del problema che hai dichiarato. In ogni caso, i concetti matematici rimangono gli stessi.