Quali algoritmi devo esaminare?

4

Per prima cosa: ho bisogno di scusarmi in anticipo sulla cattiva scelta del titolo per questa domanda, ma davvero non ho potuto trovare qualcosa di significativo. In realtà sto cercando suggerimenti su come chiamare questo tipo di problema, così da poter fare qualche ricerca per conto mio. Cambierò volentieri il titolo una volta che i suggerimenti inizieranno a venire.

Non è nemmeno un problema reale, è solo un esercizio che ho inventato per esplorare algoritmi che non ho mai avuto la possibilità di affrontare.

Diciamo che vogliamo scrivere un programma che ci aiuterà a ottimizzare la logistica di un numero arbitrario di gruppi musicali che devono esibirsi uno dopo l'altro sullo stesso palco durante la stessa notte.

Ecco il problema: le band condividono i giocatori, il che significa che ogni dato giocatore può giocare in più di una band. Se le band fossero tutte composte da giocatori diversi, non avremmo affatto bisogno di un programma, ma dal momento che tutti i musicisti si conoscono, formeranno molte band con diverse combinazioni di esse.

Quello che vogliamo fare è organizzare tutte le band in modo tale che i gruppi che condividono il maggior numero di membri si "raggruppino" insieme e suonino uno dopo l'altro, in modo da ridurre al minimo il numero di musicisti coinvolti ogni cambio di banda. In altre parole, il maggior numero possibile di musicisti dovrebbe essere già sul palco ogni volta che una band finisce il suo set e il prossimo viene sul palco.

Questa è solo un'altra forma del famoso problema di rostering / scheduling dello staff?

O è più semplice?

Devo ammettere che non ho ancora pensato a come si potrebbe risolverlo, è solo un problema a cui ho pensato oggi.

Se dovessi prenderlo a pugni, sembra che il problema si riduce a capire quali gruppi hanno il maggior numero di membri in comune, e ordinarli di conseguenza.

Ma come si chiama questo linguaggio di CS?

E tutto quello che c'è da fare?

Organizzare le bande per numero di musicisti è l'unico requisito che abbiamo. Sento che, se dovessimo prendere in considerazione altri tipi di vincoli come, ad esempio, una particolare band preferirebbe suonare all'inizio e un'altra destra nel mezzo, questo potrebbe trasformarsi in un vero problema di programmazione.

Nella sua forma più semplice, però, questo sembra essere un problema semplice ma, come ho detto, non conosco il nome della famiglia di algoritmi che mi permetterebbe di determinare quali band hanno il maggior numero di musicisti in comune.

    
posta s.m 02.07.2014 - 22:07
fonte

2 risposte

2

Questo problema può essere interpretato come una variante del problema dei venditori ambulanti , come @randomA ha notato in un commento. Le bande formano i nodi di un grafico da visitare, la "distanza" tra due bande è il numero di musicisti che non hanno in comune (il numero di musicisti che deve cambiare per un cambio di banda). L'obiettivo è ridurre al minimo il costo totale di un tour attraverso questo grafico.

Trovare il numero di membri non comuni è facile: trova il numero di membri comuni usando l'intersezione standard impostata (vedi qui ) e sottrarre il numero 2 volte dalla somma del numero di membri delle 2 bande.

Alla domanda per la classe di algoritmi: TSP è stato attaccato da diverse decine di tipi di algoritmi, vedi l'articolo di Wikipedia per alcuni suggerimenti. Alcuni di essi forniscono una soluzione esatta (ma poiché il problema generale è NP-difficile, non esistono algoritmi "efficienti" funzionanti per tutti i casi). Altri offrono una soluzione "buona", che non è necessariamente l'optimium; tale euristica può essere molto più veloce.

    
risposta data 03.07.2014 - 12:58
fonte
0

Questo mi viene in mente mentre stavo lavorando con un problema diverso. Quando sono tornato mi sono reso conto che Falk Huffner ha già menzionato il suggerimento.

Comunque, non più diteggiatura, si può mostrare la riduzione come segue alla versione decisionale del problema (se esiste un ordinamento di bande in modo da avere un valore x)

  • Per prima cosa usa una versione modificata del percorso hamiltoniano, in cui ti vengono dati i vertici di inizio e fine.

Rendi ciascun vertice una banda e ogni spigolo di una persona. Se c'è un percorso hamiltoniano modificato, ovviamente, c'è un ordinamento che ti dà il valore che è il numero di bande - 1. Anche la dimostrazione dell'inverso non è difficile da vedere.

  • La seconda parte riguarda la dimostrazione della riduzione tra l'Hamiltoniana modificata e quella normale. L'idea è che si usi semplicemente un vertice come candidato iniziale. Dividi questo vertice in 2 vertici chiamati inizio e fine. Per i vertici iniziale e finale, dividere nuovamente in nodi esterni e nodi interni. Il nodo esterno si connetterà con tutti gli altri nodi come nel grafico originale, il nodo interno si connetterà solo con i corrispondenti nodi esterni. Ciò garantisce che, una volta che un percorso entra nel nodo di inizio o di fine, il nodo candidato nel grafico originale venga visitato una sola volta. Quindi hai un percorso hamiltoniano se c'è un percorso hamiltoniano modificato.
risposta data 29.08.2014 - 12:10
fonte

Leggi altre domande sui tag