Izračun urnika

Seveda. S tem se ukvarja naš Thomas. Tule: https://www.algit.si/

Samo da te na hitro ustavim glede terminologije:

"program bi pa izračunal najbolj optimalen urnik? :)" Tole ni mogoče.
Program ti bo izračunal nek urnik (če ti ga bo). In to je najbolje kar lahko dobiš.

Me prav zanima kaj tale program vrže za recimo urnik na nekem malo večjem faksu, 30 predavalnic, 3 smeri po 4 letniki, 50 predmetov, 50 profesorjev, asistentov itd. Vsak s svojimi omejitvami. Kdaj lahko predava, kdaj ne. Poskrbeti da bodo vedno predavanja/vaje v dovolj velikih učilnicah, hkrati pa še upoštevati da bodo urniki čimbolj smiselni, torej da ne bo 2 uri zjutraj in 2 uri zvečer itd.

Verjamem, da bo tale program doživel v tem primeru doživel hudo blamažo.

Za to, da boš pa še malo bolj pameten, pa veselo branje tegale:

https://www.linkedin.com/pulse/np-compl...

Seveda pa je v algoritem zelo težko zakodirat enostavno človeško intuicijo in logiko. Ampak vsi eksperti na tem področju na forumu pa že vejo, da sestavljanje urnika ne more biti nič težje kot kak BFS ali DFS.

Z evolucijskimi algoritmi bo zagotovo prišel v nek optimum, verjetnost da bo to globalni optimum pa je odvisna od problema in operaterja, da korigira in testira različne parametre. Dober algoritem z ustreznim faktorjem mutacije med generacijami, uspe zlezti iz lokalnega optimuma.

@jernejk90, če bi bil to tako enostaven problem, ne bi imeli zdaj tukaj debate.

Tako kot je @borisk povedal. Evocijski algoritmi oz. nature-inspired metaheuristike so po mojih izkušnjah sposobne precej dobro reševati problem sestavljanja urnika z velikim številom upoštevanih omejitev. Problem je, da je njihovo izvajanje lahko precej časovno kompleksno.

@darkolord, imaš morda informacije v kakšnem času cca. reši podoben primer?

FET https://lalescu.ro/liviu/fet/

jernejl je 28. avg 2020 ob 14:39 izjavil:

Ponavadi je tako, da dlje kot takemu algoritmu pustiš delati, boljši je rezultat :)

Facebook dev je 28. avg 2020 ob 13:42 izjavil:

Seveda pa je v algoritem zelo težko zakodirat enostavno človeško intuicijo in logiko.

Kaj pomaga človeška intuicija in logika, če človek ni sposoben najti dobre rešitve?
V algoritem se pravila precej enostavno zakodira v ocenjevalno funkcijo. Kakšne parametre in uteži bo imela ocenjevalna funkcija, pa je odvisno od intuicije in logike človeka, ki jo pripravi.

Moraš vedet, da je umetna inteligenca še svetlobna leta zadaj pred inteligenco nekega povprečnega človeka. In ja, to ni sedaj problem o umetni inteligenci in tako dalje, to je samo primer, da nemoreš samo napisat "zakodiram omejitve" in bam, algoritem bo med 10^2349128409214812094809 možnosti poiskal zelo dobre rešitve. To pač tako ne gre.

Še nekaj desetletij nazaj, je bil neznanski problem kako računalnik prepozna kaj je na sliki, medtem ko človek z lahkoto "vidi" kaj je gor. Za primer damo lahko tudi igri Šah in Go. Večina boljših igralcev lahko s pogledom na pozicijo v sekundi ali dveh v večini primerov najde najboljšo oziroma eno izmed najboljših možnih potez. Kako je to mogoče, če pa je kombinacij za pregledat v številki, ki si je niti nemoreš zamislit?

In podobna situacija je tu pri urniku, človek lahko samo ošvrkne urnik in vidi kako bi na hitro naredil par premikov po tabeli in naredil boljši urnik, takoj dobi neke intuitivne ideje za spremembe. Srečno pa takšne ideje zakodirat v algoritem.

Kako pa to?

Fantje, dejte si mal prebrat o tej temu, o NP problemih, o NP polnih problemih in kam napram tem problemom sodi sestavljanje urnika.

Je pa res seveda, algoritem, ki ti bo 10 predavanj zmetal skupaj v en teden ni tezko naredit. Ko pa zacnes na to delat konstrainte, se pa vecinoma uporablja to, da dobis nekje (mogoce tudi od algoritma) neko osnovno resitv, nato pa jo ljudje konkretno izpopolnjujejo in urejajo.

Facebook dev je 28. avg 2020 ob 15:35 izjavil:

Kako pa to?

Fantje, dejte si mal prebrat o tej temu, o NP problemih, o NP polnih problemih in kam napram tem problemom sodi sestavljanje urnika.

Je pa res seveda, algoritem, ki ti bo 10 predavanj zmetal skupaj v en teden ni tezko naredit. Ko pa zacnes na to delat konstrainte, se pa vecinoma uporablja to, da dobis nekje (mogoce tudi od algoritma) neko osnovno resitv, nato pa jo ljudje konkretno izpopolnjujejo in urejajo.

Dam za pivo če premagaš katerikoli go ali šah program na običajnem računalniku.

Facebook dev je 28. avg 2020 ob 15:35 izjavil:

Kako pa to?

Fantje, dejte si mal prebrat o tej temu, o NP problemih, o NP polnih problemih in kam napram tem problemom sodi sestavljanje urnika.

Je pa res seveda, algoritem, ki ti bo 10 predavanj zmetal skupaj v en teden ni tezko naredit. Ko pa zacnes na to delat konstrainte, se pa vecinoma uporablja to, da dobis nekje (mogoce tudi od algoritma) neko osnovno resitv, nato pa jo ljudje konkretno izpopolnjujejo in urejajo.

Ravno, ko zacnes delat s constrainti rabis racunalnik, ker clovek ne more vec handlat tega.