SmartLights - Soft - Maramures - 2009 Nationala

verdun0
dinu
verdun0


3. Folosesc un fel de algoritm greedy, astfel ca sunt sigur ca solutia pe care o ofer eu semaforului e cea mai buna.



:laughing: De cand si pana cand greedy ofera solutia optima? Prin definitie greedy nu ofera (neaparat) solutia optima :exclamation:

Exista numeroase probleme la care greedy ofera solutia optima. Un exemplu este clasica problema a spectacolelor.
Da, de aceea am pus "(neaparat)". Dar formularea ta lasa de inteles ca nu ai priceput metoda greedy. Fara suparare si sper sa confirme si alti programatori care or sa citeasca. Tu ai folosit o metoda euristica. Metodele euristice pentru solutii dificile sunt greu de verificat da ca ofera solutia optima.

Cum spune si dinu, nici eu nu prea vad o solutie optima cu un greedy. Fiecare problema de au o solutie optima, si se rezolva cu greedy are o explicatie matematica si totodata logica: Gandestete: La Programarea spectacolelor, sau la algoritmul lui Prim sau Kruskal, pentru determinarea unui arbore partial de cost minim, nici nu iti trebuie matematica, si doar un pic de logica, sa vezi solutia

Dar aici nu prea o vad, la greedy-ul tau.

Intrebare: Daca la fiecare semafor stau cate x masini. Cum scoate algorimul? O masina de la semaforu 1, o masina de la semaforu 2, ? sau cum?

andrei_andrei

Cum spune si dinu, nici eu nu prea vad o solutie optima cu un greedy. Fiecare problema de au o solutie optima, si se rezolva cu greedy are o explicatie matematica si totodata logica: Gandestete: La Programarea spectacolelor, sau la algoritmul lui Prim sau Kruskal, pentru determinarea unui arbore partial de cost minim, nici nu iti trebuie matematica, si doar un pic de logica, sa vezi solutia



Dar aici nu prea o vad, la greedy-ul tau.

Intrebare: Daca la fiecare semafor stau cate x masini. Cum scoate algorimul? O masina de la semaforu 1, o masina de la semaforu 2, ? sau cum?




Scoate tot timpul astfel incat timpul mediu de asteptare sa fie minim.