Ottimizzare un parcheggio problema. Cosa algoritmi dovrei usare per adattarsi alla maggior quantità di auto nel?

Question

Quali algoritmi (forza bruta o no) dovrei usare per mettere in altrettante automobili (assumono tutte le vetture sono le stesse dimensioni) in un parcheggio in modo che vi sia almeno un'uscita (dal contenitore) e una macchina non può essere bloccato. O può qualcuno mi mostrano un esempio di questo problema risolto a livello di codice.

Il parcheggio varia in forma sarebbe bello, ma se si vuole assumere che sia una forma invariante che va bene.

Un altro Modifica: Si supponga che la guida a distanza nel parcheggio non è un fattore (anche se sarebbe completamente impressionante se fosse fattore ponderato per numero di automobili in sacco).

Un altro Modifica: Assumere 2 dimensionali (senza gru o di guida rispetto alle autovetture).

Un altro Modifica: Non è possibile spostare le auto in giro una volta che sono parcheggiati (non è un sacco parcheggiatore).

Answer 1

Bene, vediamo di semplificare / concreteify un po '. Si supponga che le nostre macchine sono unità piazze, il parcheggio è N x N, e abbiamo bisogno di entrare / uscire dall'angolo in basso a sinistra. Un modello semplice ottiene il sacco quasi 2/3 con le auto (indicato per N = 12):

+------------+
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
|C CC CC CC C|
             |
  -----------+

posso dimostrare che il meglio che può eventualmente fare è quello di ottenere il lotto 2/3. Immaginate di costruire gli spazi vuoti partendo da un garage completamente pieno e scacciando un (attualmente raggiungibile) macchina uno alla volta. Ogni volta che si rimuove una macchina, è produrre fino a 3 auto di nuova raggiungibili, e rimuovere una macchina una volta raggiungibile (ora uno spazio vuoto). Così, per ogni spazio si fanno, si crea al massimo 2 auto più raggiungibili. Per rendere 2/3 N ^ 2 automobili raggiungibili, è necessario fare almeno 1/3 N ^ 2 spazi, e questo è tutte le piazze che avete. Così si può riempire il garage al massimo 2/3.

Il modello semplice sopra è asintoticamente ottimale, la sua densità avvicina 2/3 come N -> infinito. (Kinda noioso, speravo un po 'di albero modello dall'aspetto farebbe meglio.)

Answer 2

Questo è fondamentalmente equivalente a bin-imballaggio , con il requisito ha aggiunto che l'uscita sia in un determinato luogo e tutte le auto possono uscire - che è essa stessa un problema difficile

Quindi, il problema è di almeno NP-hard.

Answer 3

è la vostra definizione di efficienza il maggior numero di posti auto in un sacco di una data dimensione e la forma (assumendo che ogni vettura può essere guidata via senza spostare alcuna altra macchina)? Se è così, si tratta di un problema di imballaggio, non è un problema di zaino, e suona NP a me, ma la gamma di soluzioni per qualsiasi lotto del mondo reale di essere così piccola che potrebbe essere risolto con un pratico ricerca esaustiva.

Answer 4

Penso che può essere tecnicamente NP completo. Ma penso che si potrebbe sviluppare un insieme intelligente di soluzioni, ognuna costruzione fuori dell'esperienza con l'ultimo, e algoritmicamente scegliere una soluzione migliore dal set calcolata. Potrebbe non essere in grado di dimostrare che è la migliore soluzione possibile. Ma da un punto di vista pratico, si dispone di un parcheggio ottimizzato, quindi è veramente importante che, data una quantità infinita di tempo che avrebbe spremuto altre 3 vetture in là?