Modo ottimale per trovare lo spazio negativo comune nella mappa di student_ids in class_times

Question

Sto scrivendo una dimostrazione di concetto per un'applicazione di pianificazione in PHP. Dispongo di una matrice 2D della pianificazione studenti nel formato (str) class_time => (array) student_ids, stampa: http://d.pr/i/UKAy.

A questo punto dell'elaborazione, devo determinare quale class_time è il più appropriato per ospitare un nuovo corso con 10 studenti che lo richiedano. A tal fine, vorrei stabilire quanti studenti hanno a disposizione n class_times, idealmente archiviati come class_time => student_ids => n_available_class_times.

Quindi, qual è il modo ideale per creare/cercare questi dati? Il risultato finale è un elenco di tutti gli class_times e un'idea di ciò che gli studenti possono utilizzare per una determinata classe poiché ogni nuovo corso è pianificato. Questo mi consente di ordinare per available_class_times per trovare gli studenti che sono più vincolati nella loro pianificazione e che hanno bisogno di priorità per essere programmati per una determinata classe, data la difficoltà con cui li pianificheremo in futuro, dato un numero di presenti/potenziali vincoli.

Answer 1

Qualcosa di simile avrebbe aiutato. Ogni array student_ids deve essere ordinato. Puoi usare l'ordinamento rapido per farlo nel tempo di nlog (n). Quindi dovresti iniziare a pianificare. Penso che qualcosa come la potatura AB funzionerebbe qui perché hai alcuni stati ottimali alla fine e decisioni lungo il percorso che influenzano lo stato ottimale. (Il bit di smistamento alla partenza è solo per renderlo più veloce)

Ecco alcune cose su AB potatura:

Per iniziare, v'è un algoritmo decisionale chiamato min-max che indica che tutte le decisioni in un il "gioco" porta ad uno stato finale che è infinitamente buono o infinitamente cattivo, cioè vincere o perdere. Quindi costruisci questo albero ogni nodo che rappresenta uno "stato di gioco", nel tuo caso uno stato di studenti è in programma. E poi cerchi l'albero. Trasportandolo per i migliori stati di movimento. Nel tuo caso la pianificazione ottimale. In ogni nodo, decidi se è uno stato finale e lo chiami all'infinito infinito o negativo o ti dirigi verso altri nodi. Nota che questo non è un albero binario. I nodi dell'albero decisionale hanno n rami in cui n è il numero di decisioni che puoi prendere lì. Questo non è troppo grande per quello che stai facendo, ma richiede spiegazioni per capire la potatura AB.

Supponiamo ora che invece di chiedere solo se un nodo è una vittoria o una sconfitta, potresti pesare quanto è buono lo stato di un gioco. Nel tuo caso in base al numero di studenti che potrebbero essere programmati in modo ottimale. Come hai attraversato l'enorme albero decisionale, puoi tagliare sezioni enormi perché sai che portano a "stati di gioco" schifosi, ovvero dichiara dove gli studenti vuoi posizionati facilmente e non facilmente posizionati. Il modo in cui lo fai è considerando i nodi che portano agli stati di gioco B che sai essere peggiore di A (il nodo che hai precedentemente valutato). Ciò è positivo perché la ricerca di questo albero è un compito computazionale serio. Questo ti permette di valutare ancora più a fondo ignorando sezioni enormi (qualcosa che è davvero impressionante enorme guadagno computazionale). Questo ti dà la risposta dei migliori stati di pianificazione delle lezioni. Good Luck Dude.

// HERE IS SOME CODE FROM THE INTERNET 
function alphabeta(node, depth, α, β, Player)   
if depth = 0 or node is a terminal node 
    return the heuristic value of node 
if Player = MaxPlayer 
    for each child of node 
     α := max(α, alphabeta(child, depth-1, α, β, not(Player)))  
     if β ≤ α 
      break        (* Beta cut-off *) 
    return α 
else 
    for each child of node 
     β := min(β, alphabeta(child, depth-1, α, β, not(Player)))  
     if β ≤ α 
      break        (* Alpha cut-off *) 
    return β 
(* Initial call *) 
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer) 

Ecco un link sul tema: http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning