2016-07-18 72 views
9

Mi sono imbattuto in questo problema che sembra piuttosto interessante. Ci sono alcuni film che vogliamo vedere tutti loro, ma mostrano solo nei seguenti orari:Algoritmo di tutti i filmati

movieA : 15 
movieB : 14, 15, 17 
movieC : 15, 17 
movieD : 15, 20 

possiamo guardare A a 15, B a 14, C a 17 e D a 20, quindi è possibile guardarli tutti Nota che non puoi guardare C a 15, non fattibile.

Il problema, come avete intuito, è se possiamo guardarli tutti.

Ovviamente possiamo risolverlo con il backtracking, provando tutte le possibilità. C'è un modo migliore per farlo? Ho un'idea di iniziare con i film con il minor numero di volte disponibili prima, in questo modo possiamo trovare la soluzione più veloce se c'è una soluzione, la complessità temporale nel caso peggiore è sempre la stessa.

Esiste un algoritmo migliore per questo problema?

P.S. Come ho chiesto @gen, ho dimenticato di indicare che ogni film è di 1 ora, quindi se ne guardi uno alle 14:00, non ti mancherà quello alle 15:00. Grazie per avermelo chiesto

+1

quanto è lungo un film? – gen

+0

@gen ogni film è un'ora, quindi non devi preoccuparti se guardi un film alle 14:00, potresti perdere quello alle 15:00. Ottima domanda! – Arch1tect

+0

Sembra un problema di corrispondenza massimo su un grafico bipartito. –

risposta

7

A seconda dei limiti del numero di film e del numero di possibili orari diversi per ciascun film, è possibile creare un grafico bipartito con i filmati su un lato e le volte nell'altro lato ed eseguire un algoritmo di flusso massimo per determinare la corrispondenza massima. Se è possibile guardare il filmato i all'ora j, aggiungere un bordo tra i nodi corrispondenti nel grafico.

+0

Mi piace questo approccio, ma ancora - l'algoritmo di flusso massimo ha un'enorme complessità. – xenteros

+0

@xenteros Cosa intendi per "enorme complessità"? Se usi Hopcroft-Karp puoi ottenere il caso peggiore 'O (M * sqrt (N))' dove 'M' è il numero di fronti e' N' è il numero di nodi (in questo caso, numero di film + numero di tempi diversi); questo verrà eseguito sotto un secondo per migliaia di film + volte. Inoltre, molti algoritmi di flusso sono fortemente influenzati dalla struttura della rete e possono essere eseguiti molto più velocemente in molti casi. Infine, l'OP ha chiesto qualcosa di meglio del backtracking. – ale64bit

+0

Non ho molta familiarità con l'algoritmo di flusso massimo, quindi avrò bisogno di dedicare un po 'più di tempo per impararlo prima di rispondere.Ma è bello sapere che esiste questo algoritmo con una maggiore complessità. Grazie! – Arch1tect

0
WHILE list of movie times isn't empty 
    1. Sort movie showtime list in order of the number of showtimes. 
    2. Watch next movie according to this sort at the first available time. 
    3. Remove respective time from each movie showtime list and movie 
     from the movie list. 

Python tentativo:

A=[15,'A'] 
B=[14,15,17,'B'] 
C=[15,17,'C'] 
D=[15,20,'D'] 

movies=[A,B,C,D] 


watchOrder = [] 

def f(x): 
    while x: # while x isnt empty 
     x=sorted(x, key=len) 
     watchOrder.append(x[0]) 
     r = x[0][0] 
     x.remove(x[0]) 
     for l in x: 
      if r in l: 
       l.remove(r) 
f(movies) 
print(watchOrder) 
+1

Purtroppo questo non riesce a trovare una soluzione anche se ne esiste una. Per un controesempio, vedere il controesempio che fornisco a una soluzione molto simile a un problema equivalente qui: http://stackoverflow.com/a/37864372/47984 –

1

Sembra un problema massima corrispondente su un grafo bipartito. I vertici del grafico sono i due set indipendenti "ore del giorno" e "titoli dei film". I bordi del grafico sono le proiezioni di un particolare film in un momento particolare.

Secondo il Manuale di progettazione dell'algoritmo di Steven Skiena, l'algoritmo più noto è l'algoritmo di Hopcroft-Karp che viene eseguito in O (E * sqrt (V)). E è il numero di spigoli, es. il numero di spettacoli. V è il numero di vertici, es. il numero di film più il numero di ore distinte durante le quali vengono mostrati i film. Negli esempi, E = 8 proiezioni, V = 4 + 4 film distinte volte = 8.

https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

Note formulazione corrispondente è possibile solo perché i film iniziano tutti sull'ora e durano esattamente un'ora. Esse coincidono esattamente o non si sovrappongono affatto.

Problemi correlati