Percorso / strada recante problema

Question

Oggi abbiamo ottenuto un incarico di completare in laboratorio (in due ore). La domanda era:

• Si è dato una m * n matrice.
• La matrice ha 'h' sale residenziali e 'b' principali ingressi degli edifici.
• La posizione di queste sale H e 'b' ingresso è nota (in termini di (x, y) le coordinate).
• È necessario porre le vie in modo tale che ogni padiglione residenziale ha almeno un modo per raggiungere uno degli ingressi 'B'.
• Non ci può essere al massimo 'b' tali percorsi sconnessi.
• La lunghezza del percorso deve essere minimo.
• È possibile spostare solo su, giù, sinistra o destra.
• La soluzione non deve essere un tentativo di forza bruta.

L'assegnazione è finita. Ma sto ancora pensando come questo possa essere risolto. Esiste un termine standard per questo tipo di problemi? Cosa devo leggere?

Le persone usano questi algoritmi per la posa strade in città come bene?

Answer 1

Ecco una soluzione mi è venuta. Non genera percorsi sconnessi 'B'. Esso genera un percorso che passa attraverso tutti i padiglioni residenziali e gli ingressi.

• Calcolare la distanza tra ogni coppia di nodi (differenza di coordinate X + differenza di coordinate Y). Ora avete un grafico completo.
• Trova il MST per questo grafico completo
• Ogni bordo inclinato del MST (quelli che non sono verticale o orizzontale) può essere diviso in due parti -. Orizzontale e verticale
• Ogni separazione può essere fatta in due modi -. Sia orizzontale prima seguita da verticale o viceversa
• passare attraverso ogni tale permutazione e calcolare il percorso con il minor lunghezza. Questa è la risposta.

Answer 2

Impossibile dire quale sia la soluzione (una sorta di minimo percorso di analisi dei costi, a occhio e croce), ma ho una certa esperienza con il software di modellazione strada.

Ad un'estremità della scala si dispone di sistemi di modellazione strategica che utilizzano un approccio simile (in senso lato). Essi possono essere considerati come un modello gravitazionale - userà stime di generazione di traffico e la domanda di fare previsioni di alto livello dei flussi di traffico tra, ad esempio, le città, o aree industriali a residenziali, ecc Questo è particolarmente utile per la ricerca gli effetti macro di importanti sviluppi pianificati, i cambiamenti nelle zone di distribuzione della popolazione o di uso del suolo .. questo genere di cose.

All'altra estremità si dispone di modelli di simulazione di aree specifiche di una città, paese, di interscambio, ecc Si tratta di modelli numerici che trattano ogni macchina come un agente autonomo con fattori come l'aggressività, la conoscenza su strada, e così via. Questo è molto più di un approccio bruta stile la forza, ma è l'unico modo per fornire statistiche utili sul comportamento del traffico reale in una rete complessa con le caratteristiche come i semafori, gli autobus, ecc Un traffico modellatore può, ad esempio, inserirlo nella dati di controllo del traffico effettivo, eseguire il modello per un determinato periodo per uno specifico soluzioni progettuali e impostare l'esecuzione 6 o 7 volte. I dati risultanti si dà una buona valutazione delle prestazioni di una soluzione particolare contro un altro (o lo status quo).

Spero che questo fornisce un contesto utile.

Answer 3

C'è un aspetto della descrizione problema che non mi è chiaro:

• Quando si dice: "È necessario porre un percorso", lo fa " solo percorso collegato?" Media Oppure ci può essere più percorsi sconnessi? (Ad esempio, un percorso da sala H1 a costruzione di ingresso B1 e un percorso separato dalla sala H2 alla costruzione di ingresso B2)

Ma comunque si risposto alla mia domanda, si tratta di un problema estremamente difficile: è NP-difficile in quanto comprende il rettilinea Steiner problema albero come un caso particolare (quando c'è un solo ingresso principale dell'edificio).

Quindi, nessuno sa come risolvere in modo efficiente nel caso generale!

Answer 4

Credo che il problema è più semplice e non Steiner albero o nemmeno albero di copertura minimo.

1. rappresentano la matrice M come un grafo G con V = {Mij | i <= m, j <= n}, E = {(Mi1j1, Mi2j2): I1, I2 <= m, J1, J2 <= n, | i1-i2 | = 1-OR esclusivo | j1-j2 | = 2}

2. Prendere serie B di ingressi, insieme H di sale

3. H '= H / B, B' = B / H (contrassegnare le sale che sono entrate, si raggiungono in profondità 0, eliminasse tutti questi ingressi come quelli sono sale)

4. Fare un attraversamento in ampiezza. A ciascuna profondità segnare le sale che possono essere raggiunte da B fino a quando tutti i padiglioni sono contrassegnati. Scegliere percorsi corrispondenti.

Answer 5

Si tratta di un problema di ricerca. Ci si aspettava di farlo in 2 ore, giusto? Vorrei DFS e prugna . Si potrebbe utilizzare euristiche per arrivare alle soluzioni migliori più veloci. Ma tenere a mente euristica non può garantire soluzioni ottimali in modo da avere a cercare tutte le possibilità . Sembra essere NP-hard.