Progetta un parcheggio 1D in grado di parcheggiare un veicolo a due ruote (1 slot), un'automobile (2 slot) o un autobus (4 slot)

0

Questa domanda è un'estensione di questa domanda . Sto anche trattando di un brainstorming sull'affermazione di questo problema in cui un parcheggio 1-dimensionale con N slot avrà parcheggi di dimensioni variabili da fare. Una due ruote occupa 1 slot, una macchina occupa 2 slot e un bus occupa 4 slot.

Dobbiamo progettare un sistema che assegni in modo efficiente lo spazio per questi. La metrica dell'efficienza è che dovremmo essere in grado di ospitare i veicoli massimi e allocarli vicino all'ingresso (supponendo che lo slot 1 sia il più vicino a 2, quindi 3 e così via ..)

Diversamente dal post indicato, cerco un consiglio su quale algoritmo possiamo utilizzare per effettuare l'allocazione. Possiamo tracciare un parallelo tra questo problema e l'allocazione di memoria che si verifica nel sistema operativo. Questo potrebbe essere considerato come se ci fossero molti processi di varie dimensioni (1, 2 e 4) che devono essere allocati nello spazio della memoria principale (il nostro parcheggio) In caso di allocazione di memoria di dimensioni variabili, ci sono 3 algoritmi:

 1. Best fit: allocate the most optimum space 
 2. Worst Fit: allocate the least optimum space
 3. First Fit: allocate the first available space 

La migliore vestibilità potrebbe essere una buona opzione da considerare, ma ha un tempo di lavoro più elevato. First Fit è una buona opzione da considerare, ma potrebbe causare uno spreco di spazio.

C'è qualche altro algoritmo / struttura dati che potrebbe essere usato per un'allocazione come questa?

    
posta user248884 13.10.2018 - 11:28
fonte

1 risposta

1

Si desidera assegnare i veicoli il più vicino possibile all'ingresso. Suppongo che ogni veicolo conta, quindi invece di allocare 4/1/1/1/1, preferirai 1/1/1/1/4 che muove quattro veicoli in avanti e sposta indietro un veicolo.

Suppongo anche che arrivino i veicoli, gli assegni uno slot e alla fine se ne vadano. Nessun veicolo viene spostato una volta parcheggiato.

Per prima cosa raccogli alcune statistiche: quanti veicoli a due ruote, auto e autobus arrivano di solito? Quindi riservate lo slot 1-4k per le due ruote, 4k + 1 a 4l per le auto, 4l + 1 a n per gli autobus in modo che di solito si adattino.

Ogni veicolo entra nel primo slot disponibile nella sua area. Se l'area è piena, si passa all'area o alle aree precedenti. Se sono pieni, si sposta il veicolo nell'area successiva. Per semplificare le cose, i bus passano solo alle slot da 4j + 1 a 4j + 4 per alcuni j, le auto passano a 2j + 1 a 2j + 2 per alcuni j.

Questo fa sì che i due carrelli tendono a venire prima, poi le macchine, il che rende il costo minimo.

    
risposta data 14.10.2018 - 01:40
fonte

Leggi altre domande sui tag