Algoritmo di pianificazione Adattamento ottimale

Question

Sto scrivendo un programma di pianificazione con un problema di programmazione difficile. Ci sono diversi eventi, ciascuno con più orari di riunione. Devo trovare una disposizione degli orari delle riunioni in modo tale che ogni pianificazione contenga un determinato evento una sola volta, utilizzando uno dei diversi orari di riunione di ciascun evento.

Ovviamente potrei usare la forza bruta, ma raramente è la soluzione migliore. Immagino che questo sia un problema di informatica relativamente di base, che imparerò una volta che sarò in grado di iniziare a prendere lezioni di informatica. Nel frattempo, preferirei qualsiasi link in cui potrei leggere su questo, o anche solo un nome che potrei Google.

Answer 1

penso che si dovrebbe usare algoritmo genetico perché:

• È più adatto per le grandi istanze del problema.
• Produce ridotta complessità temporale sul prezzo di risposta imprecisa (non l'ultimo migliore)
• È possibile specificare vincoli & preferenze facilmente regolando punizioni di fitness per i più non soddisfatte.
• È possibile specificare il limite di tempo per l'esecuzione del programma.

• La qualità della soluzione dipende da quanto tempo avete intenzione di trascorrere risolvere il programma ..

  Genetic Algorithms Definition

  Genetic Algorithms Tutorial

  Class scheduling project with GA

Answer 2

La descrizione del problema non è del tutto chiara, ma se tutto quello che stai cercando di fare è trovare un programma che non ha eventi sovrapposti, allora questo è un problema semplice bipartite matching.

Sono disponibili due gruppi di nodi: eventi e orari. Traccia un vantaggio da ciascun evento a ogni possibile momento della riunione. È quindi possibile costruire in modo efficiente la corrispondenza (il più grande insieme possibile di bordi tra i nodi) utilizzando augmented paths. Questo funziona perché puoi sempre convertire un grafico bipartito in un diagramma di flusso equivalente.

Un esempio di codice che esegue questa operazione è BIM. Anche le librerie di grafici standard come GOBLIN e NetworkX dispongono di implementazioni di corrispondenza bipartite.

Answer 3

Sembra che questo potrebbe essere un buon candidato per una soluzione dynamic programming, in particolare qualcosa di simile al problema interval scheduling.

Ci sono alcuni elementi grafici here per il problema di pianificazione intervallo in particolare, che può rendere il concetto più chiaro. Here è un buon tutorial sulla programmazione dinamica in generale.

Answer 4

Ci sono diversi modi per farlo questo

Un approccio consiste nel programmare i vincoli. È un caso speciale della programmazione dinamica suggerita da Feanor. È di aiuto usare una libreria specializzata in grado di eseguire i limiti e le ramificazioni per te. (Google per "gecode" o "comet-online" per trovare le librerie)

Se sei incline matematicamente, puoi anche utilizzare la programmazione di interi per risolvere il problema.L'idea di base qui è quella di tradurre il tuo problema in un insieme di disuguaglianze lineari. (Google per "programmazione dei numeri interi" per trovare molti esempi di vita reale e google per "Abacus COIN-OR" per una libreria utile)

La mia ipotesi è che la programmazione dei vincoli sia l'approccio più semplice, ma la programmazione dei numeri interi è utile se si vuoi includere variabili reali nel tuo problema ad un certo punto.