PKO Piemēri

2025-01-27T09:52:49Z

Agree:

#'''(C)VRP(PD)(TW)''' ... u.c. ... (miskastes mašīnas, kurjeri, būvgružu konteineri, elektoauto ar uzlādi, pārvākšanās serviss utt. ...) VRP - apmeklēt noteiktus punktus ātrāk/tuvāk/letāk. TW - laika logi, kad drīkst ierasties. C - mašīnas ietilpība. PD - paņemšana/nolikšana.
#'''Studenti gatavojas eksāmenam - kurus uzdevumus risināt?''' Students vakarā atceras, ka viņam rīt ir -kontroldarbs, bet viņš neko nav mācījies. Priekš gatavošanās viņam ir atlikušas x minūtes. Viņš zina, ka kontroldarbā būs n uzdevumi katrs par savu tēmu. Tāpat viņš zina katra uzdevuma vērtību v[i] un viņš zina arī laiku t[i], kas nepieciešams, lai sagatavotos katram uzdevumam. Kuriem uzdevumiem viņam ir jāgatavojas, lai iegūtu pēc iespējas labāku vērtējumu?
#'''Šahs - figūru izvietošana, lai neapdraud viena otru''' (N_Queens) Dots nxm šaha galdiņš uz kura izvietoti x kauliņi, izvietot kauliņus tā lai tie pēc iespējas mazāk apdraudētu viens otru. Kauliņš var būt: tornis, zirgs, laidnis, dāma, karalis. Attiecīgi kauliņi apdraudēšanu veic tāpat kā klasiskajos šaha noteikumos. ProgrSamma spēj apstrādāt situāciju kur būs daudz kauliņi, kas neizbēgami apdraudēs viens otru, bet programmai jāatrod variants kur kauliņi apdraud pēc iespējas mazāk citus kauliņus (resp mazāk pārklājās).
#'''Sagatavju optimāla griešana''' Darbnīcā ir n metāla cauruļu sagataves, katra garumā I[i], kur 0<i<=n. Ir pasūtījums izgatavot m caurules garumos p[j]. Uzdevums ir saplānot, no kurām sagatavēm izgatavot pasūtītās caurules, lai būtu pēc iespējas mazāk atlikumu - nogriezto, bet neizmantoto sagatavju gabalu.
#'''Sanāksmju plānošana''' Dots - m telpas offisā, katrā ir ietilpības lielums[i], cilvēku skaits, ko tas var izmitināt; tehniskais aprīkojums - projektora pieejamība p[i] (Jā/Nē), videokonferenču aprīkojuma pieejamība v[i] (Jā/Nē). n darbinieki ar noteiktu darba laiku un iespējamām sanāksmju laika vēlmēm. k projekti, katrs ar sanāksmēm, kurām nepieciešami: obligāto dalībnieku saraksts, neobligāto dalībnieku saraksts, noteikts tehniskais aprīkojums (projektors, videokonference), fiksēts plānotais ilgums sanāksmei. '''Hard prasības''': telpu piešķiršana sapulcēm - telpas sanāksmēm tiek piešķirtas tā, lai telpas ietilpības lielums[i] ir atbilstošs dalībnieku skaitam un nepieciešamais aprīkojums (projektors p[i], videokonference v[i]) ir pieejams. Obligāto dalībnieku grafiki, kas nepārklājas: jāsaplāno sanāksmes, nodrošinot, ka obligātajiem dalībniekiem nav konfliktu un tie noteikti spēs apmeklēt sanāksmi. Sanāksmes ilguma ievērošana: jāievēro fiksēto plānoto sanāksmju ilgumu darba laikā. Unikālo telpu rezervēšana: nodrošiniet, lai katra telpa vienlaikus būtu rezervēta tikai vienai sapulcei. '''Soft prasības''': izvēlēto dalībnieku uzņemšana - plānojiet sanāksmes, ņemot vērā neobligāto dalībnieku pieejamību; sapulces laika vēlmes - pēc iespējas ņemiet vērā darbinieku un projekta sanāksmes laika vēlmes (no rīta, pēcpusdienā). Vienmērīga telpas izmantošana - vienmērīgi sadaliet sapulces visās pieejamajās telpās. Bufera laiks starp sanāksmēm - ideālā gadījumā jāieplāno bufera periodu (piemēram, 15 minūtes) starp secīgām sanāksmēm tajā pašā telpā, lai varētu tās izvēdināt.
#Dinamiskās darba telpas aizpildīšana Pamata problēma: ir darba vieta ar dinamisko darba telpu, kur nāk tie darbinieki, kas nevēlas/nevar pilno laiku strādāt klātienē. 80 darbiniekus nepieciešams izvietot 30 vietās tā, lai vismaz trešo daļu no ceturkšņa katrs no trim biznesa centriem (struktūrvienība darbiniekiem) pavadītu klātienē. Jāņem vērā iepriekš saskaņots regulāro sapulču grafiks, kur ir piezīme - klātiene vai online, kur klātienes sapulču laikā darbiniekiem jābūt klātienē, online - attālināti. Ja vienam darbiniekam ir vienāds skaits gan klātienes, gan attālināto sapulču vienā dienas pusē, tad vēlams nodrošināt attālinātu. Vērā jāņem arī darbinieku grafiks - kuros laikos noteikti darbinieki nevarēs būt klātienē. (Iespējams! pievienot arī darbinieku vēlmes - vairāk/mazāk klātieni, labāk rītus/pēcpusdienas, u.tml.) Lai atvieglotu darbinieku transporta grafiku, laiks šeit nozīmē vienu no divām vērtībām - rīts un pēcpusdiena, tā kā cilvēki nevēlēsies braukt uz/no darba vairākkārt vienā dienā vai, piemēram, pastrādāt stundu mājās un tad braukt uz darbu 4 stundas un tad atkal mājās. Sastādītajam grafikam vajadzētu būt pēc iespējas regulāram, ieturot vienu grafiku vai nu katrai nedēļai, vai katrām divām. Sēdvietu iedalījums neeksistē.
#'''Produktu sapakošana''' Uzņēmumā ir n pakošanas mašīnas. Tam ir jāizpilda k pakošanas uzdevumi, kur katrs uzdevums ir iepakot noteiktu produktu p[i] līdz noteiktam termiņam T[i]. Ir zināms, ka katrs uzdevums veicams laikā t[i]. Tāpat arī zināms, ja pakošanas mašīnā nomainās produkts, tad tā ir jāiztīra un tas konkrētam produktam aizņem laiku c[j]. Saplānot kādā secībā un kurās pakošanas mašīnās veikt visus uzdevumus tā, lai visi pasūtījumi būtu laikā un viss process aizņemtu pēc iespējas mazāku laiku.
#'''Chineese Postman Problem (sniega tīrīšana)''' Dots orientēts grafs Map=(Intersectrions,Steets), kas reprezentē Latvijas valsts karti kā ceļa tīklu. Intersectrions ir virsotņu kopa (krustojumi) un Streets ir svarotu šķautņu kopa (ielas), kur svari apzīmē ielas garumu. Automašīnai ir dots uzdevums apbraukt kādu Latvijas pilsētu (vai pilsētas daļu) areaToTraverse, kas ir sakarīgs Map apakšgrafs, ievērojot sekojošus nosacījumus: 1. Automašīnai sāk savu ceļu no autoparka, kas var nepiederēt areaToTraverse grafam. Tāpēc automašīnai ir jānonāk līdz kādam areaToTraverse grafam piederošam krustojumam. 2. Ceļš sākas un beidzas autoparkā3. Braukšanas ceļš ir cikls ar vismazāko šķautņu svaru summu, kur ceļš sākas un beidzas autoparkā. 4. Automašīnai jāapmeklē visas ielas no grafa Town tā, ka katra iela tika apmeklēta visos atļautos braukšanas virzienos vismaz vienu reizi, t.i., vienvirziena ielas apmeklētas vismaz vienu reizi atļautā virzienā, savukārt divvirziena ielas ir apmeklēta vismaz vienu reizi abos virzienos. 5. Dažas ielas vai ielas virzieni var būt slēgti dēļ remontdarbiem vai kādiem citiem ierobežojumiem.
#Vakcinācijas plānošana Ir k vakcinācijas centri, kur katram ir brīvi laika logi w[i], kad var nākt vakcinēties. Saplānot vakcināciju n cilvēkiem, tā, lai kopējais attālums līdz vakcinācijas centriem būtu pēc iespējas mazāks. Doti attālumi starp visiem cilvēkiem un centriem, kā arī katram cilvēkam ir pateikts, no cikiem līdz cikiem viņi tiek uz vakcināciju!
#'''Skolēnu piekārtošana skolām''' Doti n skolas un m skolēni. Zināma katras skolas ietilpība s[i], kur 0<i<=n un attālumi a[k,j] no k-tā skolēna līdz j-tajai skolai, kur 0<k<=m un 0<j<=n. Zināms, ka s[1]+...+s[n]<=m, t.i., skolās kopumā vietu pietiek. Piekārtot skolēniem skolas tā, lai kopējais attālums, kas jāveic skolēniem būtu pēc iespējas mazāks.
#'''Paciņu izvietošana pa mašīnām''' Dotas m automašīnas, katra ar kravas kastes izmēru w[i] x l[i]. Dotas n kastes ar izmēriem p[j] x g[j].Salikt visas kastes pēc iespējas mazāk automašīnās. Var arī 3D!
#'''Blēžu bildēšana''' Uzdevums ir sastādīt plānošanas grafiku detektivem, lai noķertu visus blēžus. '''Detektīvi''': ķer blēžus ar mērķi vienas dienas laikā noķert pēc iespējas vairāk blēžu. Katram detektīvam ir savs protokola sastādīšanas laiks. Katram detektīvam ir savs darba laika sākums un beigas. Katrs detektīvs pārvietojas, vai nu ar sabiedrisko transportu, vai nu ar auto. Ne visiem detektīviem ir auto. Katram detektīvam ir savs pieredzes līmenis (strādājošo mēnešu skaits). No tā ir atkarīgs laiks, kas nepieciešams, lai nofotografētu blēžu grupu. Katrs detektīvam ir ofiss, kur viņš strādā un kurā jāatgriežās pēc grupas ķeršanas. Katram detektīvam ir maksimālais blēžu grupu skaits, kuru var noķert. Katram detektīvam ir jāmaksā par veicamo darba ilgumu atkarībā no viņa stundas likmes. Detektīvi darbojas brīvajā darba režīmā un drīkst atpūsties ārpus tie ķer blēžu grupas. Tāpēc ir jāmaksā tikai par laiku, kad tie brauc no vai līdz blēžu grupai. Katram detektīvam ir jāmaksā par auto izmaksām (proti, ja tam ir auto). Ja detektīvam ir auto, tad katru blēžu grupa viņš ķer, pārvietojoties ar auto. '''Blēžu grupas:''' blēži satiekas grupās. Visas grupas var būt dažādas! Viens blēdis var būt vairākas grupās. Katrs blēdis satiekas vismaz viena grupā. Katrai blēžu grupai ir piekārtots pieredzes līmenis jeb novērtējums, cik grūti ir noķert šo grupu. Katram grupai ir savs tikšanas laiks un tikšanas beigu laiks. '''Nosacījums blēžu grupas noķeršanai:''' visi detektīvi sākumā atrodas ofisos. Detektīvs ir noķēris blēžu grupu, ja atbrauca pie grupas šīs grupas tikšanas laikos un sava darba laikā. Nofotografējis grupu. Atbrauca atpakaļ ofisā viņa darba laikā. '''Hard ierobežojumi''': pēc katras grupas apmeklēšanas detektīvam jāatgriežas sava ofisā. Detektīva pieredzes līmenim jābūt lielākam vai vienādam ar blēžu grupas pieredzes līmeni. Visas blēžu grupas ir jāķer to tikšanas laikos. Visas blēžu grupas ir jāķer detektīva darba laikā Detektīvs nedrīkst ķert vairāk nekā tam paredzēts grupu skaits. '''Soft ierobežojumi''': kopējam attālumam jābūt pēc iespējas mazākam. Izmaksām par detektīva darba laiku jābūt pēc iespējas mazākām. Izmaksām par detektīva auto lietošanu jābūt pēc iespējas mazākām.
#'''Japāņu krustvārdu mīklas''' Atrisināt melnbaltu [https://www.nonograms.org/nonograms/size/xsmall Japāņu krustwārdu mīklu].
#'''Sudoku visvisādi varianti''' Atrisināt [https://www.funwithpuzzles.com/2017/02/sudoku-variations-index-page.html Sudoku] mīklu.
#'''Sociālā dienesta,ārstu apmeklējumu plānošana''' CVRPTW tipa uzdevums. Slimnīca piedāvā pakalpojumu kur viņu ārsti ir gatavi apciemot pacientus viņu mājās. Katram pacientam ir vajadzīga noteikta specialitāte no ārsta, lai viņs spētu to apkalpot, kā arī noteikts spēks gadījumā ja ar pacientu ir jārīkos fiziskā mērā, piemēram, pacientu vajadzētu pārvietot no gultas uz kaut kur citu viet. Ārsti braucot pie pacientiem ved līdzi medikamentus vai citus preperātus, kas viņiem būtu vajadzīgi, lai apkalpotu pacientu. Ārstam braucot pie pacienta var arī būt vajadzība no tā pievākt preperātus, piemeram, asisns analīzes, urīns etc. Ārsti strādā noteiktos darba laikos, jeb laika logos, kā arī viņu pacienti var būt tikt apciemoti tikai to noteiktajos laikos.
#'''Pacientu gultasvietu plānošana''' Pastāv slimnīca ar vairākām nodaļām, kurās pastāv istabas ar gultām, kur tiks novietoti slimnīcas pacienti, lai tie varētu pavadīt vienu nakti slimnīcā. Pacientu ierašanās un aiziešanās no slimnīcas datumi ir noteikti. Katrā istabā pastāv maksimāls gultu skaits, kuru iespējams novietot tajā, un pacientam ir vēlme būt novietotam ar istabu ar noteiktu izmēru (velme tiek nodefinēta kā istabas maksimālais izmērs, kura apmierina pacientu. Ja pacients tiek novietots istabā ar mazāku izmēru, tad pacients joprojām būs apmierināts). Pacienta ir iespējams novietot gan departamenta, kas nodarbojas ar slimības ārstēšanu, gan istabā, kura ir aprīkota ar nepieciešamām iekārtām pacienta slimības ārstēšanai. Pastāv pacienti, kuriem iekārtas ir nepieciešamas un tie, kuri vēlās, lai istabā būtu tās iekārtas. Istabām pastāv savi ierobežojumi: sieviešu istaba, vīriešu istaba, viena dzimuma pacienti vienā naktī, bez ierobežojuma. Tātad vīrieši nevar pavadīt nakti sieviešu istabā un sievietes nevar pavadīt nakti vīriešu istabā. Vienu dzimuma istabā kopā var pavadīt nakti vienlaikus tikai vīrieši vai tikai sievietes.
#'''Lekciju saraksta sastādīšana (Timetabling)''' Uzdevums ir daļa no Timetabling uzdevumu klases, precīzāk Educational Timetabling klases. University Timetabling ietver dažādus apakšuzdevumus, piemēram, sastādīt lekciju sarakstu, sastādīt eksāmenu sarakstu, sastādīt konferencēm grafikus, aizstāvēšanu grafikus, utt. Šajā uzdevumā tiks apskatīts tieši lekciju saraksta sastādīšana. Uzdevumā ir dotas vairākas lekcijas, piemēram, “Lineārā algebra I”, “Kombinatorika”, utt., katrai no šīm lekcijām ir vajadzīgs piekārtot nedēļā lekciju konkrētā telpā, konkrētā laikā, kas nemainās visu semestri, ja tas nav 2 KP kurss, bet lielāks, piemēram, 4 KP, tad var būt 2 lekcijas nedēļā, utml. Toties jāņem vērā dažādi ierobežojumi, piemēram, vienā laikā un vienā telpā nevar notikt 2 lekcijas, vienā laikā pasniedzējs nevar pasniegt 2 lekcijas, vienā laikā grupa studentu nevar būt divās lekcijās vienlaicīgi. Kā arī var definēt citus ierobežojumus. Kopumā ir vērts skatīt šo uzdevumu, kā daļu no lielāka resursu (telpu, ierīču, personāla, ...) plānošanas uzdevuma.
#'''Grāmatu draugi''' Grāmatu draugu biedrībā ir n lasītāji un n grāmatas. Pie katra lasītāja ir viena grāmata, kuru viņš ir izlasījis. Tāpat par katru citu grāmatu ir zināms, vai viņš to ir lasījis, vai nē. Kurjera uzdevums ir savākt un izvadāt grāmatas tā, lai beigās pie visiem lasītājiem būtu grāmata, ko viņš nav lasījis. Ir zināmi attālumi starp lasītājiem! Saplānot kurjera maršrutu tā, lai viņam būtu jānobrauc pēc iespējas mazāks attālums!
#'''Darba grafika plānošana''' Sastādīt darbinieku maiņu grafiku - piekārtot darba vietai darbinieku ar atbilstošām prasmēm, ņemot verā darba likumdošanu un darbinieku vēlmes.
#'''Darbu un resursu plānošana''' Sastādīt darbu izpildes grafiku, ņemot vērā pieejamo resursu daudzumu un termiņus.
#'''Šņūksti''' (@ Dāvis Valts Briedis) SIA Šņūkstings Bruņuvardes ir bruņuvaržu ražošanas uzņēmums. Uzņēmumā strādā tikai šņūksti. Katru dienu tajā strādājošie šņūksti pabaro bruņuvardes, bet viņiem nav skaidrs kāds ir vislabākais grafiks bruņuvaržu barošanai, tāpēc viņiem ir nepieciešama IT sistēma, kas spēs optimizēt barošanas grafikus. Papildus šņūkstiem jāpaspēj pusdienās iesņūkstēties. Uzņēmuma teritorijā ir iespējams nokļūt tikai caur administrācijas ēku. Tajā arī atrodas ēdnīca. Tālāk ir iespējams no administrācijas ēkas nokļūt uz korpusu 1. No korpusa 1 ir iespējams nokļūt uz korpusu 2 un korpusu 2a. Ir iespējams arī nokļūt no korpusa 2 uz korpusu 2a, bet ceļš starp tiem ir mīnēts. Bruņuvardes tiek uzglabātas bruņuvaržu krātiņos. Katram krātiņam ir numurs. Krātiņi ar secīgiem numuriem arī fiziski atradīsies blakus. Vienā krātiņā ir viena bruņuvarde. Katrā korpusā ir zināms daudzums krātiņu. Administrācijas ēkā nav krātiņu. Ir jāatrod grafiks, kas būs bruņuvaržu barošanas secība. Tas sastāvēs no ierakstiem, katrā ierakstā būs norādīts kāda darbība šņūkstam ir jāveic, kurā korpusā tā ir jāveic un kurā krātiņā tā ir jāveic. Grafikam jābūt saliktam tādam, ka ja šņūksts seko šim grafikam, viņš būs paveicis savu darbu iespējami īsākā laikā.
#'''Lidmašinu apkalpju darba plānošana''' Kaut kāda diena ir X lidojumi, katram lidojumam ir nepieciešams atrast ekipāžu kurš sastav no A pirmā līmeņa pilotiem, B otrā līmeņa pilotiem un C stjuartiem (katram lidojuma A,B un C var būt dažādi). Katram lidojumam ir zinamas izlidošanas un ielidošanas lidosta, ka arī plānotais izlidošanas un ielidošanas laiks. Kompānija strāda Y darbinieki, par katru darbinieku ir zinama viņa profesija, mājas lidosta (t.i. kur strādnieks atrodas tagad) un viņa pieejamība stradāta šaja dienā (piejams, nav pieejams, nevēlams). U-zdevums ir katram lidojumam atrast ekipāžu tā lai: '''Hard ierobežojumi:''' - Strādnieks ekipažā aizņem savu profesiju - Stradnieks nevar atrasties 2 dažas lidojumos vienlaikus - Strādnieks startē savā mājas lidostā - Strādnieks atlidojot kaut kāda lidosta, nākamu lidojumu var veikt tikai no šis lidostas - Stradnieks nevar strādat ja vina pieejamība “nav pieejams”. '''Soft ierobežojumi:''' - Strādniekam ir nepieciešama vismaz 2 stundu atpūta starp lidojumiem - Strādnieks dienas beigās atgriežas savas mājas lidostā - Stradnieks nevar strādat, ja vina pieejamība “nevēlams”
#'''F1 grafika plānošana''' F1 sacensības notiek nedēļas nogalēs, laikā no marta līdz novembrim. Tātad mums ir n nedēļas nogales (apzīmēsim ar w[i], kārtējo nogali), kurās rīkot šo posmu. Ir k posmi (apzīmēsim ar p[j]), kas notiek noteiktā vietā uz pasaules un ir zināmas izmaksas, lai komandas aizceļotu no katra punkta uz katru (izm[p[j]]), kas iekļauj sevī arī radītās emisijas. Ir arī zināmi ieņēmumi no katra posma, ja tas tiek rīkots noteiktā laika posmā ien[p[j],w[i]). Bahreinā vasaras vidū varētu būt par karstu. Piekārtot katram posmam nedēļas nogali tā tā, peļņa būtu vislielākā!
#'''Skolas autobusu maršrutu plānošana''' Optimizēt skolas autobusu maršrutus, lai uzņemtu un izlaistu skolēnus, vienlaikus ievērojot laika ierobežojumus un transportlīdzekļu ietilpību kā arī maksimāli apmierināt studentu vēlmes.
#'''Aktieru nolīgšana''' Pieņemsim, ka mums ir jāizveido filmu ar vairākām ainām. Katrā ainā ir jāuzņem vienam vai vairākiem aktieriem. Aktieris uzņemt tikai vienu ainu dienā. Šo aktieru algas tiek aprēķinātas pa dienām. Šajā problēmā aktieris tiek pieņemts darbā līdz laikam, kad aktieris nofilmē visas savas ainas. Piemēram, mēs nevaram pieņemt darbā aktieri pirmajā un trešajā dienā, bet ne otrajā dienā. Nomas perioda laikā aktieriem joprojām ir jāmaksā, pat ja viņi nav iesaistīti filmēšanā. Vienā dienā var tikt filmēta tikai viena aina. Talantu plānošanas mērķis ir samazināt aktieru kopējo algu, pielāgojot ainu secību. Dots aktieru skaits N. Katram aktierim tiek piešķirta alga dienā. Dots ainu skaits M. Katrā M ainā tiek definēts aktieru masīvs, kur tiek ietverti aktieru numuri, kas piedalās ainā.
#'''Rogainings, utml.''' Dotam grafam ar virsotnēm un zināmiem ceļu garumiem, atrast ceļu, kas savāc visaugstāko apmeklēto virsotņu vērtību, nepārsniedzot laika ierobežojumu.Katrai virsotnei ir punktu skaits ko var nopelnīt to apmeklējot. Katrai virsotnei ir tās veikšanai nepieciešamais laiks. Zināma distance starp virsotnēm. Zināms pārvietošanās ātrums. Zināms sākuma un beigu virsotnes, nokļūšana no/uz tiem iekļauta laikā. Sāk sākuma virsotnē. Beidz beigu virsotnē. Nepārsniedz laiku. Savāc maksimāli lielu punktu skaitu (ne obligāti var visas apmeklēt). Veic pēc iespējas mazāku distanci. Pēc iespējas mazāka kāpšana augšā/lejā kalnā.
#'''Izvietot k punktus nxn režģī - no-3-in-a-row''' Dots uzdevums, kas sastāv no 𝑛∙𝑛 režģa, kur uz režģa krustpunktiem ir izvietots 𝑘daudzums ar punktiem. Uzdevuma mērķis ir atrast tādu punktu 𝑘 izvietojumu, ka nav iespējams novilkt taisnu līniju cauri trim vai vairāk punktiem. Tātad uz katras taisnes drīkst atrasties maksimums divi punkti.
#'''Pentamino''' Ar dotajiem [https://en.wikipedia.org/wiki/Pentomino pentamino] kauliņiem maksimāli noklāt doto ģeometrisko figūru. Kauliņi nedrīkst pārklāties vai iziet ārpus figūras robežas.
#'''Kameru izvietošana telpās''' Dotas N telpas un K kameras . Ir M vietas, kur izvietot kameras , kur katrai vietai ir dotas tās telpas, kas ir no turienes redzamas. Izvietot kameras tā, lai visas telpas būtu redzamas vismaz no 2 kamerām un kameru skaits būtu pēc iespējas mazāks.
#'''Testēšanas darbu plānošana''' Ir testēšanas sistēma, kurai laikā L ir nepieciešams izpildīt T testus. Katram no testiem ir platformu saraksts, uz kurām ir nepieciešams notestēt doto testu (praksē platformu skaits ir neliels, ~10). Testus būtu labi patestēt uz dažādām arhitektūrām (katrai platformai tādas var būt vairākas; praksē skaits arī ir neliels, <20). Testi tiek palaisti uz N ierīcēm (N ir novērojami mazāks nekā T), katrai ierīcei ir viena vai vairākas platformas (piem., linux + android [izmantojot emulatoru]) un viena vai vairākas arhitektūras (piem., uz x86_64 var palaist arī x86). Katram testam ir zināms tā darbības laiks (uz kādas “etalona” ierīces ar “jaudu/ātrumu” 1). Katrai ierīcei ir rēķināšanas “jauda/ātrums”, kas ir izteikts kā attiecība pret etalona ierīces jaudu. (Tad testa darbības laiks ir kādas ierīces x ir testa darbības laiks uz etalona ierīces / ierīces x jauda). Uzdevums ir izveidot plānu: kad, uz kādas ierīces, kādas platformas un izmantojot kādu arhitektūru ir nepieciešams palaist kādu testu, tā, lai: kopā visi T testi tiktu izpildīti, kopējais testēšanas laiks nepārsniedz L, katrs no testiem tiktu palaists uz katras platformas (no testam atbilstošām platformām), katram testam tiktu pārbaudītas pēc iespējas vairākas arhitektūras... (šeit var diskutēt par to, kā to novērtēt. Būtība ir tāda, ka nevajadzētu dot priekšroku "alkatīgi" izvēlēties tikai visātrākos testus un tos pārbaudīt uz vairākām arhitektūrām, bet lēnākus palaist tikai uz vienas. Tāpēc šajā uzdevumā prasība ir, lai minimālā vērtība "pārbaudīto arhitektūru skaits" / "visu testam iespējamo arhitektūru skaits" starp visiem testiem būtu maksimāla). Starp plāniem ar vienādu minimālo "pārbaudīto arhitektūru skaitu" / "visu testam iespējamo arhitektūru skaitu" starp testiem (no iepriekšējā punkta) jāatrod to, kuram vidējā vērtība (vai summa) pārbaudīto arhitektūru skaitu procentam visiem testiem ir vislielākā.
#'''Towers mīkla''' [https://www.puzzle-skyscrapers.com/ Torņu mīkla]
#'''Noliktavu izvietošanas plānošana, lai nodrošinātu pieprasījumu''' Uzdevumā pamatā ir Facility Location Problem, kuru mērķis ir atrast optimālākās atrašanās vietas noliktavām, lai attālums līdz veikaliem būtu pēc iespējas tuvāks, ņemot vērā to, ka katrai noliktavai ir noteikts darba kapacitātes apjoms, kuru nedrīkst pārsniegt. Šī darba kapacitāte balstās uz nobrauktu attālumu starp šo noliktavu no saistītiem veikaliem kopā ar apkalpošanas laiku vienam veikalam (nosacītā laika vienība). Pieņēmumi: noliktava ir spējīga apkalpot vienā izbraukumā tikai vienu veikalu, pēc katra izbraukuma “mašīna” atgriežas līdz noliktavai, uzdevumā tiek uzskatīts, ka visas rēķināšanas tiek veiktas gadījumiem, kad visiem veikaliem dienas laikā ir jānogādā nepieciešamas preces. Jebkurā secībā/laikā, nevis noteiktā laika apgabalā(ne time windows). Ieejas dati: Visas potenciālās noliktavas, kuras ir pieejamas nomai. Visi veikali, kas ir jāapkalpo. Izejas dati: noliktavas ar piesaistītajiem veikaliem, kurus tie apkalpos, karte ar noliktavām un veikaliem.
#'''Sporta spēļu (turnīra) kalendāra plānošana''' Create an optimization service, that makes a games calendar for football tournaments. As input, there is a list of stadiums, teams with their names and stadium names, where they play home games (one stadium can belong to many teams), and available Date/time slots. Every team pair plays against each other twice: once as a home team, and once as an away team. Games are always played in the home team's stadium. '''Constraints:''' No more than 1 game per day for each team. No more than 1 game per day at each stadium. A game can start only between 10.00 and 23.00. Games should be scheduled on weekends and Fridays. Minimum 2 free days between games for each team. On workdays, games start not earlier than 18.00. On weekends games start no earlier than 12.00. On weekends games start before 21.00. No more than one game for each time slot.
#'''Lidostu skrejceļu izmantošanas plānošana''' Dati ir par lidmašīnu ierašanās laikiem lidostā un mērķis ir atrast optimālo plānu, kuros skrejceliņos, kurām lidmašīnām ir atļauts nolaisties, lai minimizētu citu lidmašīnu gaidīšanas laiku.
#'''Bioinformātika - sequence alignment''' Dotas divas virknes a un b alfabētā A. Ļausim mainīt virknes sekojošā veidā ar funkcijas edit(x,y) palīdzību, kur x un y pieder A+{gap}, iespējamās darbības: 1) Ievietot gap vienā no virknēm 2) izdzēst gap vienā no virknēm 3) samainīt 2 blakus esošus simbolus vienā no virknēm. Nodefinēsim edit f-jas izmaksas cost(x,y). Tad izmaiņu virknes S kopējā izmaksās, būs visu izmaiņu izmaksu summa. Uzdevums ir atrast tādus a' un b', kas pieder A+{gap}, |a'|=|b'|, a' ir iegūstams no a, pievienojot {gap} simbolus, bet b' iegūstams no b pievienojot tam {gap} simbolus un izmaksas, kas nepieciešamas, lai no a' iegūtu b' ir vismazākās!
#'''Kūku cepšana''' Min-Cut Kūku cepšana - [https://www.hackerearth.com/practice/algorithms/graphs/min-cut/practice-problems/algorithm/mancunian-the-confectioner/ Mancucian the confectioner]
#'''Punktu pārklāšana''' Ar dotajām plaknes figūrām pārklāt pēc iespējas vairāk punktus.
#'''Pirkumu plāns''' Doti veikali, to darba laiki un preces, ko tur var nopirkt. Sastādīt iepirkšanās plānu, ja ir zināmas preces, kas nepieciešamas, kā aŗī papildus vēlmes, kā piemēram, vēlamais veikalu apmeklēšanas biežums, produktu derīguma termiņš, u.c.
#'''Iekārtu izvietošana telpās''' Izvietot iekārtas telpās, ņemot vērā to savstarpējā novietojuma izdevīgumu un telpu izmēru.
#'''Domino puzle''' [https://ksim.cvg.edu.lv/gallery/KSIM2024_fin_uzd.pdf). KSIM Cēsis 2024 fināla uzdevums]
#'''Grāmatu sakārtošana plauktos''' Sakārtot grāmatas plauktos tā, lai viena autora drāmatas būtu pēc iespējas tuvāk. Plauktiem ir izmēri un svars, ko tie var nest.
#'''Delegāciju dalībnieku izvietošana viesnīcās''' Dots dalībnieku un komandu vadītāju saraksts, pieejamo viesnīcas/-u numuru saraksts. Par katru dalībnieku un vadītāju zināms dzimums (V/S) un pārstāvētā valsts. Katram viesnīcas numuram zināma cena par vienu nakti, gultu skaits un viesnīca, kurā tas atrodas. Katras valsts komandai ir noteikts budžets, cik daudz līdzekļu drīkst iztērēt katru nakti.
#'''Curriculum-Based Course Timetabling (CB-CTT)''' [https://www.eeecs.qub.ac.uk/itc2007/curriculmcourse/course_curriculm_index.htm CB-CTT]
#'''Būvobjektu izvietošana pilsētā''' Mērķis ir optimizēt pilsētas objektu izvietojumu, piemēram, māju, skolu, ofisu, veikalu u.c. būvju izvietošanai konkrētās lokācijās
#'''Dial-a-ride''' Mums ir jāizplāno ceļi un laiki, kurā dotais transporta līdzeklis (mašīna, autobuss vai cits) ar konkrētu vietu skaitu savāc un piegādā cilvēkus no ienas vietas uz citu (pēc pieteikuma). Atkarībā no problēmas, šie pietikumi braukšanai var būt zināmi no sākuma (statiski) vai arī tie var parādīties ceļa laikā (dinamiski). Kā arī problēmas risināšanai var būt vairākas mašīnas vienlaikus vai tikai viena visu brauciena laikā.
#'''Tūrista ceļojuma plānošana''' Uzdevums - ceļojuma plānošana: Tūrists dodas ceļojumā un vēlas apmeklēt pēc iespējas vairāk interesantu vietu. Tomēr laiks ir ierobežots un nepieciešams arī parūpēties par fizisko veselību - paēst un pagulēt. Dots ceļojuma sākuma un beigu laiks, kā arī darba laiki dažādiem apskates objektiem un restorāniem. Katram apskates objektam un restorānam arī zināms, cik lielu prieku tūrists gūtu no šo vietu apmeklēšanas un cik ilgu laiku tas prasīs. Mērķis - maksimizēt prieku, neupurējot citas vajadzības.
#'''Ikdienas aktivitāšu plānošana''' Saplānot ikdienas aktivitātes.

PKO Piemēri

2025-01-27T09:52:13Z

Agree: 2024. gada rudens uzdevumi

#'''(C)VRP(PD)(TW)''' ... u.c. ... (miskastes mašīnas, kurjeri, būvgružu konteineri, elektoauto ar uzlādi, pārvākšanās serviss utt. ...) VRP - apmeklēt noteiktus punktus ātrāk/tuvāk/letāk. TW - laika logi, kad drīkst ierasties. C - mašīnas ietilpība. PD - paņemšana/nolikšana.
#'''Studenti gatavojas eksāmenam - kurus uzdevumus risināt?''' Students vakarā atceras, ka viņam rīt ir -kontroldarbs, bet viņš neko nav mācījies. Priekš gatavošanās viņam ir atlikušas x minūtes. Viņš zina, ka kontroldarbā būs n uzdevumi katrs par savu tēmu. Tāpat viņš zina katra uzdevuma vērtību v[i] un viņš zina arī laiku t[i], kas nepieciešams, lai sagatavotos katram uzdevumam. Kuriem uzdevumiem viņam ir jāgatavojas, lai iegūtu pēc iespējas labāku vērtējumu?
#'''Šahs - figūru izvietošana, lai neapdraud viena otru''' (N_Queens) Dots nxm šaha galdiņš uz kura izvietoti x kauliņi, izvietot kauliņus tā lai tie pēc iespējas mazāk apdraudētu viens otru. Kauliņš var būt: tornis, zirgs, laidnis, dāma, karalis. Attiecīgi kauliņi apdraudēšanu veic tāpat kā klasiskajos šaha noteikumos. ProgrSamma spēj apstrādāt situāciju kur būs daudz kauliņi, kas neizbēgami apdraudēs viens otru, bet programmai jāatrod variants kur kauliņi apdraud pēc iespējas mazāk citus kauliņus (resp mazāk pārklājās).
#'''Sagatavju optimāla griešana''' Darbnīcā ir n metāla cauruļu sagataves, katra garumā I[i], kur 0<i<=n. Ir pasūtījums izgatavot m caurules garumos p[j]. Uzdevums ir saplānot, no kurām sagatavēm izgatavot pasūtītās caurules, lai būtu pēc iespējas mazāk atlikumu - nogriezto, bet neizmantoto sagatavju gabalu.
#'''Sanāksmju plānošana''' Dots - m telpas offisā, katrā ir ietilpības lielums[i], cilvēku skaits, ko tas var izmitināt; tehniskais aprīkojums - projektora pieejamība p[i] (Jā/Nē), videokonferenču aprīkojuma pieejamība v[i] (Jā/Nē). n darbinieki ar noteiktu darba laiku un iespējamām sanāksmju laika vēlmēm. k projekti, katrs ar sanāksmēm, kurām nepieciešami: obligāto dalībnieku saraksts, neobligāto dalībnieku saraksts, noteikts tehniskais aprīkojums (projektors, videokonference), fiksēts plānotais ilgums sanāksmei. '''Hard prasības''': telpu piešķiršana sapulcēm - telpas sanāksmēm tiek piešķirtas tā, lai telpas ietilpības lielums[i] ir atbilstošs dalībnieku skaitam un nepieciešamais aprīkojums (projektors p[i], videokonference v[i]) ir pieejams. Obligāto dalībnieku grafiki, kas nepārklājas: jāsaplāno sanāksmes, nodrošinot, ka obligātajiem dalībniekiem nav konfliktu un tie noteikti spēs apmeklēt sanāksmi. Sanāksmes ilguma ievērošana: jāievēro fiksēto plānoto sanāksmju ilgumu darba laikā. Unikālo telpu rezervēšana: nodrošiniet, lai katra telpa vienlaikus būtu rezervēta tikai vienai sapulcei. '''Soft prasības''': izvēlēto dalībnieku uzņemšana - plānojiet sanāksmes, ņemot vērā neobligāto dalībnieku pieejamību; sapulces laika vēlmes - pēc iespējas ņemiet vērā darbinieku un projekta sanāksmes laika vēlmes (no rīta, pēcpusdienā). Vienmērīga telpas izmantošana - vienmērīgi sadaliet sapulces visās pieejamajās telpās. Bufera laiks starp sanāksmēm - ideālā gadījumā jāieplāno bufera periodu (piemēram, 15 minūtes) starp secīgām sanāksmēm tajā pašā telpā, lai varētu tās izvēdināt.
#Dinamiskās darba telpas aizpildīšana Pamata problēma: ir darba vieta ar dinamisko darba telpu, kur nāk tie darbinieki, kas nevēlas/nevar pilno laiku strādāt klātienē. 80 darbiniekus nepieciešams izvietot 30 vietās tā, lai vismaz trešo daļu no ceturkšņa katrs no trim biznesa centriem (struktūrvienība darbiniekiem) pavadītu klātienē. Jāņem vērā iepriekš saskaņots regulāro sapulču grafiks, kur ir piezīme - klātiene vai online, kur klātienes sapulču laikā darbiniekiem jābūt klātienē, online - attālināti. Ja vienam darbiniekam ir vienāds skaits gan klātienes, gan attālināto sapulču vienā dienas pusē, tad vēlams nodrošināt attālinātu. Vērā jāņem arī darbinieku grafiks - kuros laikos noteikti darbinieki nevarēs būt klātienē. (Iespējams! pievienot arī darbinieku vēlmes - vairāk/mazāk klātieni, labāk rītus/pēcpusdienas, u.tml.) Lai atvieglotu darbinieku transporta grafiku, laiks šeit nozīmē vienu no divām vērtībām - rīts un pēcpusdiena, tā kā cilvēki nevēlēsies braukt uz/no darba vairākkārt vienā dienā vai, piemēram, pastrādāt stundu mājās un tad braukt uz darbu 4 stundas un tad atkal mājās. Sastādītajam grafikam vajadzētu būt pēc iespējas regulāram, ieturot vienu grafiku vai nu katrai nedēļai, vai katrām divām. Sēdvietu iedalījums neeksistē.
#'''Produktu sapakošana''' Uzņēmumā ir n pakošanas mašīnas. Tam ir jāizpilda k pakošanas uzdevumi, kur katrs uzdevums ir iepakot noteiktu produktu p[i] līdz noteiktam termiņam T[i]. Ir zināms, ka katrs uzdevums veicams laikā t[i]. Tāpat arī zināms, ja pakošanas mašīnā nomainās produkts, tad tā ir jāiztīra un tas konkrētam produktam aizņem laiku c[j]. Saplānot kādā secībā un kurās pakošanas mašīnās veikt visus uzdevumus tā, lai visi pasūtījumi būtu laikā un viss process aizņemtu pēc iespējas mazāku laiku.
#'''Chineese Postman Problem (sniega tīrīšana)''' Dots orientēts grafs Map=(Intersectrions,Steets), kas reprezentē Latvijas valsts karti kā ceļa tīklu. Intersectrions ir virsotņu kopa (krustojumi) un Streets ir svarotu šķautņu kopa (ielas), kur svari apzīmē ielas garumu. Automašīnai ir dots uzdevums apbraukt kādu Latvijas pilsētu (vai pilsētas daļu) areaToTraverse, kas ir sakarīgs Map apakšgrafs, ievērojot sekojošus nosacījumus: 1. Automašīnai sāk savu ceļu no autoparka, kas var nepiederēt areaToTraverse grafam. Tāpēc automašīnai ir jānonāk līdz kādam areaToTraverse grafam piederošam krustojumam. 2. Ceļš sākas un beidzas autoparkā3. Braukšanas ceļš ir cikls ar vismazāko šķautņu svaru summu, kur ceļš sākas un beidzas autoparkā. 4. Automašīnai jāapmeklē visas ielas no grafa Town tā, ka katra iela tika apmeklēta visos atļautos braukšanas virzienos vismaz vienu reizi, t.i., vienvirziena ielas apmeklētas vismaz vienu reizi atļautā virzienā, savukārt divvirziena ielas ir apmeklēta vismaz vienu reizi abos virzienos. 5. Dažas ielas vai ielas virzieni var būt slēgti dēļ remontdarbiem vai kādiem citiem ierobežojumiem.
#Vakcinācijas plānošana Ir k vakcinācijas centri, kur katram ir brīvi laika logi w[i], kad var nākt vakcinēties. Saplānot vakcināciju n cilvēkiem, tā, lai kopējais attālums līdz vakcinācijas centriem būtu pēc iespējas mazāks. Doti attālumi starp visiem cilvēkiem un centriem, kā arī katram cilvēkam ir pateikts, no cikiem līdz cikiem viņi tiek uz vakcināciju!
#'''Skolēnu piekārtošana skolām''' Doti n skolas un m skolēni. Zināma katras skolas ietilpība s[i], kur 0<i<=n un attālumi a[k,j] no k-tā skolēna līdz j-tajai skolai, kur 0<k<=m un 0<j<=n. Zināms, ka s[1]+...+s[n]<=m, t.i., skolās kopumā vietu pietiek. Piekārtot skolēniem skolas tā, lai kopējais attālums, kas jāveic skolēniem būtu pēc iespējas mazāks.
#'''Paciņu izvietošana pa mašīnām''' Dotas m automašīnas, katra ar kravas kastes izmēru w[i] x l[i]. Dotas n kastes ar izmēriem p[j] x g[j].Salikt visas kastes pēc iespējas mazāk automašīnās. Var arī 3D!
#'''Blēžu bildēšana''' Uzdevums ir sastādīt plānošanas grafiku detektivem, lai noķertu visus blēžus. '''Detektīvi''': ķer blēžus ar mērķi vienas dienas laikā noķert pēc iespējas vairāk blēžu. Katram detektīvam ir savs protokola sastādīšanas laiks. Katram detektīvam ir savs darba laika sākums un beigas. Katrs detektīvs pārvietojas, vai nu ar sabiedrisko transportu, vai nu ar auto. Ne visiem detektīviem ir auto. Katram detektīvam ir savs pieredzes līmenis (strādājošo mēnešu skaits). No tā ir atkarīgs laiks, kas nepieciešams, lai nofotografētu blēžu grupu. Katrs detektīvam ir ofiss, kur viņš strādā un kurā jāatgriežās pēc grupas ķeršanas. Katram detektīvam ir maksimālais blēžu grupu skaits, kuru var noķert. Katram detektīvam ir jāmaksā par veicamo darba ilgumu atkarībā no viņa stundas likmes. Detektīvi darbojas brīvajā darba režīmā un drīkst atpūsties ārpus tie ķer blēžu grupas. Tāpēc ir jāmaksā tikai par laiku, kad tie brauc no vai līdz blēžu grupai. Katram detektīvam ir jāmaksā par auto izmaksām (proti, ja tam ir auto). Ja detektīvam ir auto, tad katru blēžu grupa viņš ķer, pārvietojoties ar auto. '''Blēžu grupas:''' blēži satiekas grupās. Visas grupas var būt dažādas! Viens blēdis var būt vairākas grupās. Katrs blēdis satiekas vismaz viena grupā. Katrai blēžu grupai ir piekārtots pieredzes līmenis jeb novērtējums, cik grūti ir noķert šo grupu. Katram grupai ir savs tikšanas laiks un tikšanas beigu laiks. '''Nosacījums blēžu grupas noķeršanai:''' visi detektīvi sākumā atrodas ofisos. Detektīvs ir noķēris blēžu grupu, ja atbrauca pie grupas šīs grupas tikšanas laikos un sava darba laikā. Nofotografējis grupu. Atbrauca atpakaļ ofisā viņa darba laikā. '''Hard ierobežojumi''': pēc katras grupas apmeklēšanas detektīvam jāatgriežas sava ofisā. Detektīva pieredzes līmenim jābūt lielākam vai vienādam ar blēžu grupas pieredzes līmeni. Visas blēžu grupas ir jāķer to tikšanas laikos. Visas blēžu grupas ir jāķer detektīva darba laikā Detektīvs nedrīkst ķert vairāk nekā tam paredzēts grupu skaits. '''Soft ierobežojumi''': kopējam attālumam jābūt pēc iespējas mazākam. Izmaksām par detektīva darba laiku jābūt pēc iespējas mazākām. Izmaksām par detektīva auto lietošanu jābūt pēc iespējas mazākām.
#'''Japāņu krustvārdu mīklas''' Atrisināt melnbaltu [https://www.nonograms.org/nonograms/size/xsmall Japāņu krustwārdu mīklu].
#'''Sudoku visvisādi varianti''' Atrisināt [https://www.funwithpuzzles.com/2017/02/sudoku-variations-index-page.html Sudoku] mīklu.
#'''Sociālā dienesta,ārstu apmeklējumu plānošana''' CVRPTW tipa uzdevums. Slimnīca piedāvā pakalpojumu kur viņu ārsti ir gatavi apciemot pacientus viņu mājās. Katram pacientam ir vajadzīga noteikta specialitāte no ārsta, lai viņs spētu to apkalpot, kā arī noteikts spēks gadījumā ja ar pacientu ir jārīkos fiziskā mērā, piemēram, pacientu vajadzētu pārvietot no gultas uz kaut kur citu viet. Ārsti braucot pie pacientiem ved līdzi medikamentus vai citus preperātus, kas viņiem būtu vajadzīgi, lai apkalpotu pacientu. Ārstam braucot pie pacienta var arī būt vajadzība no tā pievākt preperātus, piemeram, asisns analīzes, urīns etc. Ārsti strādā noteiktos darba laikos, jeb laika logos, kā arī viņu pacienti var būt tikt apciemoti tikai to noteiktajos laikos.
#'''Pacientu gultasvietu plānošana''' Pastāv slimnīca ar vairākām nodaļām, kurās pastāv istabas ar gultām, kur tiks novietoti slimnīcas pacienti, lai tie varētu pavadīt vienu nakti slimnīcā. Pacientu ierašanās un aiziešanās no slimnīcas datumi ir noteikti. Katrā istabā pastāv maksimāls gultu skaits, kuru iespējams novietot tajā, un pacientam ir vēlme būt novietotam ar istabu ar noteiktu izmēru (velme tiek nodefinēta kā istabas maksimālais izmērs, kura apmierina pacientu. Ja pacients tiek novietots istabā ar mazāku izmēru, tad pacients joprojām būs apmierināts). Pacienta ir iespējams novietot gan departamenta, kas nodarbojas ar slimības ārstēšanu, gan istabā, kura ir aprīkota ar nepieciešamām iekārtām pacienta slimības ārstēšanai. Pastāv pacienti, kuriem iekārtas ir nepieciešamas un tie, kuri vēlās, lai istabā būtu tās iekārtas. Istabām pastāv savi ierobežojumi: sieviešu istaba, vīriešu istaba, viena dzimuma pacienti vienā naktī, bez ierobežojuma. Tātad vīrieši nevar pavadīt nakti sieviešu istabā un sievietes nevar pavadīt nakti vīriešu istabā. Vienu dzimuma istabā kopā var pavadīt nakti vienlaikus tikai vīrieši vai tikai sievietes.
#'''Lekciju saraksta sastādīšana (Timetabling)''' Uzdevums ir daļa no Timetabling uzdevumu klases, precīzāk Educational Timetabling klases. University Timetabling ietver dažādus apakšuzdevumus, piemēram, sastādīt lekciju sarakstu, sastādīt eksāmenu sarakstu, sastādīt konferencēm grafikus, aizstāvēšanu grafikus, utt. Šajā uzdevumā tiks apskatīts tieši lekciju saraksta sastādīšana. Uzdevumā ir dotas vairākas lekcijas, piemēram, “Lineārā algebra I”, “Kombinatorika”, utt., katrai no šīm lekcijām ir vajadzīgs piekārtot nedēļā lekciju konkrētā telpā, konkrētā laikā, kas nemainās visu semestri, ja tas nav 2 KP kurss, bet lielāks, piemēram, 4 KP, tad var būt 2 lekcijas nedēļā, utml. Toties jāņem vērā dažādi ierobežojumi, piemēram, vienā laikā un vienā telpā nevar notikt 2 lekcijas, vienā laikā pasniedzējs nevar pasniegt 2 lekcijas, vienā laikā grupa studentu nevar būt divās lekcijās vienlaicīgi. Kā arī var definēt citus ierobežojumus. Kopumā ir vērts skatīt šo uzdevumu, kā daļu no lielāka resursu (telpu, ierīču, personāla, ...) plānošanas uzdevuma.
#'''Grāmatu draugi''' Grāmatu draugu biedrībā ir n lasītāji un n grāmatas. Pie katra lasītāja ir viena grāmata, kuru viņš ir izlasījis. Tāpat par katru citu grāmatu ir zināms, vai viņš to ir lasījis, vai nē. Kurjera uzdevums ir savākt un izvadāt grāmatas tā, lai beigās pie visiem lasītājiem būtu grāmata, ko viņš nav lasījis. Ir zināmi attālumi starp lasītājiem! Saplānot kurjera maršrutu tā, lai viņam būtu jānobrauc pēc iespējas mazāks attālums!
#'''Darba grafika plānošana''' Sastādīt darbinieku maiņu grafiku - piekārtot darba vietai darbinieku ar atbilstošām prasmēm, ņemot verā darba likumdošanu un darbinieku vēlmes.
#'''Darbu un resursu plānošana''' Sastādīt darbu izpildes grafiku, ņemot vērā pieejamo resursu daudzumu un termiņus.
#'''Šņūksti''' (@ Dāvis Valts Briedis) SIA Šņūkstings Bruņuvardes ir bruņuvaržu ražošanas uzņēmums. Uzņēmumā strādā tikai šņūksti. Katru dienu tajā strādājošie šņūksti pabaro bruņuvardes, bet viņiem nav skaidrs kāds ir vislabākais grafiks bruņuvaržu barošanai, tāpēc viņiem ir nepieciešama IT sistēma, kas spēs optimizēt barošanas grafikus. Papildus šņūkstiem jāpaspēj pusdienās iesņūkstēties. Uzņēmuma teritorijā ir iespējams nokļūt tikai caur administrācijas ēku. Tajā arī atrodas ēdnīca. Tālāk ir iespējams no administrācijas ēkas nokļūt uz korpusu 1. No korpusa 1 ir iespējams nokļūt uz korpusu 2 un korpusu 2a. Ir iespējams arī nokļūt no korpusa 2 uz korpusu 2a, bet ceļš starp tiem ir mīnēts. Bruņuvardes tiek uzglabātas bruņuvaržu krātiņos. Katram krātiņam ir numurs. Krātiņi ar secīgiem numuriem arī fiziski atradīsies blakus. Vienā krātiņā ir viena bruņuvarde. Katrā korpusā ir zināms daudzums krātiņu. Administrācijas ēkā nav krātiņu. Ir jāatrod grafiks, kas būs bruņuvaržu barošanas secība. Tas sastāvēs no ierakstiem, katrā ierakstā būs norādīts kāda darbība šņūkstam ir jāveic, kurā korpusā tā ir jāveic un kurā krātiņā tā ir jāveic. Grafikam jābūt saliktam tādam, ka ja šņūksts seko šim grafikam, viņš būs paveicis savu darbu iespējami īsākā laikā.
#'''Lidmašinu apkalpju darba plānošana''' Kaut kāda diena ir X lidojumi, katram lidojumam ir nepieciešams atrast ekipāžu kurš sastav no A pirmā līmeņa pilotiem, B otrā līmeņa pilotiem un C stjuartiem (katram lidojuma A,B un C var būt dažādi). Katram lidojumam ir zinamas izlidošanas un ielidošanas lidosta, ka arī plānotais izlidošanas un ielidošanas laiks. Kompānija strāda Y darbinieki, par katru darbinieku ir zinama viņa profesija, mājas lidosta (t.i. kur strādnieks atrodas tagad) un viņa pieejamība stradāta šaja dienā (piejams, nav pieejams, nevēlams). U-zdevums ir katram lidojumam atrast ekipāžu tā lai: '''Hard ierobežojumi:''' - Strādnieks ekipažā aizņem savu profesiju - Stradnieks nevar atrasties 2 dažas lidojumos vienlaikus - Strādnieks startē savā mājas lidostā - Strādnieks atlidojot kaut kāda lidosta, nākamu lidojumu var veikt tikai no šis lidostas - Stradnieks nevar strādat ja vina pieejamība “nav pieejams”. '''Soft ierobežojumi:''' - Strādniekam ir nepieciešama vismaz 2 stundu atpūta starp lidojumiem - Strādnieks dienas beigās atgriežas savas mājas lidostā - Stradnieks nevar strādat, ja vina pieejamība “nevēlams”
#'''F1 grafika plānošana''' F1 sacensības notiek nedēļas nogalēs, laikā no marta līdz novembrim. Tātad mums ir n nedēļas nogales (apzīmēsim ar w[i], kārtējo nogali), kurās rīkot šo posmu. Ir k posmi (apzīmēsim ar p[j]), kas notiek noteiktā vietā uz pasaules un ir zināmas izmaksas, lai komandas aizceļotu no katra punkta uz katru (izm[p[j]]), kas iekļauj sevī arī radītās emisijas. Ir arī zināmi ieņēmumi no katra posma, ja tas tiek rīkots noteiktā laika posmā ien[p[j],w[i]). Bahreinā vasaras vidū varētu būt par karstu. Piekārtot katram posmam nedēļas nogali tā tā, peļņa būtu vislielākā!
#'''Skolas autobusu maršrutu plānošana''' Optimizēt skolas autobusu maršrutus, lai uzņemtu un izlaistu skolēnus, vienlaikus ievērojot laika ierobežojumus un transportlīdzekļu ietilpību kā arī maksimāli apmierināt studentu vēlmes.
#'''Aktieru nolīgšana''' Pieņemsim, ka mums ir jāizveido filmu ar vairākām ainām. Katrā ainā ir jāuzņem vienam vai vairākiem aktieriem. Aktieris uzņemt tikai vienu ainu dienā. Šo aktieru algas tiek aprēķinātas pa dienām. Šajā problēmā aktieris tiek pieņemts darbā līdz laikam, kad aktieris nofilmē visas savas ainas. Piemēram, mēs nevaram pieņemt darbā aktieri pirmajā un trešajā dienā, bet ne otrajā dienā. Nomas perioda laikā aktieriem joprojām ir jāmaksā, pat ja viņi nav iesaistīti filmēšanā. Vienā dienā var tikt filmēta tikai viena aina. Talantu plānošanas mērķis ir samazināt aktieru kopējo algu, pielāgojot ainu secību. Dots aktieru skaits N. Katram aktierim tiek piešķirta alga dienā. Dots ainu skaits M. Katrā M ainā tiek definēts aktieru masīvs, kur tiek ietverti aktieru numuri, kas piedalās ainā.
#'''Rogainings, utml.''' Dotam grafam ar virsotnēm un zināmiem ceļu garumiem, atrast ceļu, kas savāc visaugstāko apmeklēto virsotņu vērtību, nepārsniedzot laika ierobežojumu.Katrai virsotnei ir punktu skaits ko var nopelnīt to apmeklējot. Katrai virsotnei ir tās veikšanai nepieciešamais laiks. Zināma distance starp virsotnēm. Zināms pārvietošanās ātrums. Zināms sākuma un beigu virsotnes, nokļūšana no/uz tiem iekļauta laikā. Sāk sākuma virsotnē. Beidz beigu virsotnē. Nepārsniedz laiku. Savāc maksimāli lielu punktu skaitu (ne obligāti var visas apmeklēt). Veic pēc iespējas mazāku distanci. Pēc iespējas mazāka kāpšana augšā/lejā kalnā.
#'''Izvietot k punktus nxn režģī - no-3-in-a-row''' Dots uzdevums, kas sastāv no 𝑛∙𝑛 režģa, kur uz režģa krustpunktiem ir izvietots 𝑘daudzums ar punktiem. Uzdevuma mērķis ir atrast tādu punktu 𝑘 izvietojumu, ka nav iespējams novilkt taisnu līniju cauri trim vai vairāk punktiem. Tātad uz katras taisnes drīkst atrasties maksimums divi punkti.
#'''Pentamino''' Ar dotajiem [https://en.wikipedia.org/wiki/Pentomino pentamino] kauliņiem maksimāli noklāt doto ģeometrisko figūru. Kauliņi nedrīkst pārklāties vai iziet ārpus figūras robežas.
#'''Kameru izvietošana telpās''' Dotas N telpas un K kameras . Ir M vietas, kur izvietot kameras , kur katrai vietai ir dotas tās telpas, kas ir no turienes redzamas. Izvietot kameras tā, lai visas telpas būtu redzamas vismaz no 2 kamerām un kameru skaits būtu pēc iespējas mazāks.
#'''Testēšanas darbu plānošana''' Ir testēšanas sistēma, kurai laikā L ir nepieciešams izpildīt T testus. Katram no testiem ir platformu saraksts, uz kurām ir nepieciešams notestēt doto testu (praksē platformu skaits ir neliels, ~10). Testus būtu labi patestēt uz dažādām arhitektūrām (katrai platformai tādas var būt vairākas; praksē skaits arī ir neliels, <20). Testi tiek palaisti uz N ierīcēm (N ir novērojami mazāks nekā T), katrai ierīcei ir viena vai vairākas platformas (piem., linux + android [izmantojot emulatoru]) un viena vai vairākas arhitektūras (piem., uz x86_64 var palaist arī x86). Katram testam ir zināms tā darbības laiks (uz kādas “etalona” ierīces ar “jaudu/ātrumu” 1). Katrai ierīcei ir rēķināšanas “jauda/ātrums”, kas ir izteikts kā attiecība pret etalona ierīces jaudu. (Tad testa darbības laiks ir kādas ierīces x ir testa darbības laiks uz etalona ierīces / ierīces x jauda). Uzdevums ir izveidot plānu: kad, uz kādas ierīces, kādas platformas un izmantojot kādu arhitektūru ir nepieciešams palaist kādu testu, tā, lai: kopā visi T testi tiktu izpildīti, kopējais testēšanas laiks nepārsniedz L, katrs no testiem tiktu palaists uz katras platformas (no testam atbilstošām platformām), katram testam tiktu pārbaudītas pēc iespējas vairākas arhitektūras... (šeit var diskutēt par to, kā to novērtēt. Būtība ir tāda, ka nevajadzētu dot priekšroku "alkatīgi" izvēlēties tikai visātrākos testus un tos pārbaudīt uz vairākām arhitektūrām, bet lēnākus palaist tikai uz vienas. Tāpēc šajā uzdevumā prasība ir, lai minimālā vērtība "pārbaudīto arhitektūru skaits" / "visu testam iespējamo arhitektūru skaits" starp visiem testiem būtu maksimāla). Starp plāniem ar vienādu minimālo "pārbaudīto arhitektūru skaitu" / "visu testam iespējamo arhitektūru skaitu" starp testiem (no iepriekšējā punkta) jāatrod to, kuram vidējā vērtība (vai summa) pārbaudīto arhitektūru skaitu procentam visiem testiem ir vislielākā.
#'''Towers mīkla''' [https://www.puzzle-skyscrapers.com/ Torņu mīkla]
#'''Noliktavu izvietošanas plānošana, lai nodrošinātu pieprasījumu''' Uzdevumā pamatā ir Facility Location Problem, kuru mērķis ir atrast optimālākās atrašanās vietas noliktavām, lai attālums līdz veikaliem būtu pēc iespējas tuvāks, ņemot vērā to, ka katrai noliktavai ir noteikts darba kapacitātes apjoms, kuru nedrīkst pārsniegt. Šī darba kapacitāte balstās uz nobrauktu attālumu starp šo noliktavu no saistītiem veikaliem kopā ar apkalpošanas laiku vienam veikalam (nosacītā laika vienība). Pieņēmumi: noliktava ir spējīga apkalpot vienā izbraukumā tikai vienu veikalu, pēc katra izbraukuma “mašīna” atgriežas līdz noliktavai, uzdevumā tiek uzskatīts, ka visas rēķināšanas tiek veiktas gadījumiem, kad visiem veikaliem dienas laikā ir jānogādā nepieciešamas preces. Jebkurā secībā/laikā, nevis noteiktā laika apgabalā(ne time windows). Ieejas dati: Visas potenciālās noliktavas, kuras ir pieejamas nomai. Visi veikali, kas ir jāapkalpo. Izejas dati: noliktavas ar piesaistītajiem veikaliem, kurus tie apkalpos, karte ar noliktavām un veikaliem.
#'''Sporta spēļu (turnīra) kalendāra plānošana''' Create an optimization service, that makes a games calendar for football tournaments. As input, there is a list of stadiums, teams with their names and stadium names, where they play home games (one stadium can belong to many teams), and available Date/time slots. Every team pair plays against each other twice: once as a home team, and once as an away team. Games are always played in the home team's stadium. '''Constraints:''' No more than 1 game per day for each team. No more than 1 game per day at each stadium. A game can start only between 10.00 and 23.00. Games should be scheduled on weekends and Fridays. Minimum 2 free days between games for each team. On workdays, games start not earlier than 18.00. On weekends games start no earlier than 12.00. On weekends games start before 21.00. No more than one game for each time slot.
#'''Lidostu skrejceļu izmantošanas plānošana''' Dati ir par lidmašīnu ierašanās laikiem lidostā un mērķis ir atrast optimālo plānu, kuros skrejceliņos, kurām lidmašīnām ir atļauts nolaisties, lai minimizētu citu lidmašīnu gaidīšanas laiku.
#'''Bioinformātika - sequence alignment''' Dotas divas virknes a un b alfabētā A. Ļausim mainīt virknes sekojošā veidā ar funkcijas edit(x,y) palīdzību, kur x un y pieder A+{gap}, iespējamās darbības: 1) Ievietot gap vienā no virknēm 2) izdzēst gap vienā no virknēm 3) samainīt 2 blakus esošus simbolus vienā no virknēm. Nodefinēsim edit f-jas izmaksas cost(x,y). Tad izmaiņu virknes S kopējā izmaksās, būs visu izmaiņu izmaksu summa. Uzdevums ir atrast tādus a' un b', kas pieder A+{gap}, |a'|=|b'|, a' ir iegūstams no a, pievienojot {gap} simbolus, bet b' iegūstams no b pievienojot tam {gap} simbolus un izmaksas, kas nepieciešamas, lai no a' iegūtu b' ir vismazākās!
#'''Kūku cepšana''' Min-Cut Kūku cepšana - [https://www.hackerearth.com/practice/algorithms/graphs/min-cut/practice-problems/algorithm/mancunian-the-confectioner/ Mancucian the confectioner]
#'''Punktu pārklāšana''' Ar dotajām plaknes figūrām pārklāt pēc iespējas vairāk punktus.
#'''Pirkumu plāns''' Doti veikali, to darba laiki un preces, ko tur var nopirkt. Sastādīt iepirkšanās plānu, ja ir zināmas preces, kas nepieciešamas, kā aŗī papildus vēlmes, kā piemēram, vēlamais veikalu apmeklēšanas biežums, produktu derīguma termiņš, u.c.
#'''Iekārtu izvietošana telpās''' Izvietot iekārtas telpās, ņemot vērā to savstarpējā novietojuma izdevīgumu un telpu izmēru.
#'''Domino puzle''' [https://ksim.cvg.edu.lv/gallery/KSIM2024_fin_uzd.pdf). KSIM Cēsis 2024 fināla uzdevums]
#'''Grāmatu sakārtošana plauktos''' Sakārtot grāmatas plauktos tā, lai viena autora drāmatas būtu pēc iespējas tuvāk. Plauktiem ir izmēri un svars, ko tie var nest.
#'''Delegāciju dalībnieku izvietošana viesnīcās''' Dots dalībnieku un komandu vadītāju saraksts, pieejamo viesnīcas/-u numuru saraksts. Par katru dalībnieku un vadītāju zināms dzimums (V/S) un pārstāvētā valsts. Katram viesnīcas numuram zināma cena par vienu nakti, gultu skaits un viesnīca, kurā tas atrodas. Katras valsts komandai ir noteikts budžets, cik daudz līdzekļu drīkst iztērēt katru nakti.
#'''Curriculum-Based Course Timetabling (CB-CTT)''' [https://www.eeecs.qub.ac.uk/itc2007/curriculmcourse/course_curriculm_index.htm CB-CTT]
#'''Būvobjektu izvietošana pilsētā''' Mērķis ir optimizēt pilsētas objektu izvietojumu, piemēram, māju, skolu, ofisu, veikalu u.c. būvju izvietošanai konkrētās lokācijās
#'''Dial-a-ride''' Mums ir jāizplāno ceļi un laiki, kurā dotais transporta līdzeklis (mašīna, autobuss vai cits) ar konkrētu vietu skaitu savāc un piegādā cilvēkus no ienas vietas uz citu (pēc pieteikuma). Atkarībā no problēmas, šie pietikumi braukšanai var būt zināmi no sākuma (statiski) vai arī tie var parādīties ceļa laikā (dinamiski). Kā arī problēmas risināšanai var būt vairākas mašīnas vienlaikus vai tikai viena visu brauciena laikā.
#'''Tūrista ceļojuma plānošana''' Uzdevums - ceļojuma plānošana: Tūrists dodas ceļojumā un vēlas apmeklēt pēc iespējas vairāk interesantu vietu. Tomēr laiks ir
ierobežots un nepieciešams arī parūpēties par fizisko veselību - paēst un pagulēt. Dots ceļojuma sākuma un beigu laiks, kā arī darba laiki dažādiem apskates objektiem un restorāniem. Katram apskates objektam un restorānam arī zināms, cik lielu prieku tūrists gūtu no šo vietu apmeklēšanas un cik ilgu laiku tas prasīs. Mērķis - maksimizēt prieku, neupurējot citas vajadzības.
#'''Ikdienas aktivitāšu plānošana''' Saplānot ikdienas aktivitātes.

PKO Piemēri

2025-01-27T09:28:27Z

Agree:

Praktiskā Kombinatoriālā Optimizācija

2024-02-16T18:40:14Z

Agree:

Te būs apraksts par to, kas ir praktiskā kombinatoriālā optimizācija (PKO)!

PKO tipiski risina "piekārtošanas problēmu" - doti plānošanas mainīgie un to vērtību apgabali, kā arī izmaksu funkcija, kas ļauj novērtēt un salīdzināt iegūtos risinājumus. Uzdevums ir atrast risinājumu - plānošanas mainigajiem piekārtoto vērtību komplektu, kas dod vislabākās izmaksas!

[[PKO Piemēri]]

Te būs dažādu tēmu detalizētāks apraksts!

2020-09-25T14:44:19Z

Agree: /* Spēles */

Šajā vietnē [//www.lu.lv Latvijas Universitātes] [//df.lu.lv Datorikas fakultātes] docents un [//www.lumii.lv Matemātikas un informātikas institūta] vadošais pētnieks Agris Šostaks apkopo dažādas interesantas ar datorzinātnēm saistītas tēmas, kas galvenokārt varētu tikt attīstītas studiju darbu (kvalifikācijas, kursa, bakalaura, maģistra) veidā.

2017. gada rudens semestrī kopā ar docenti Elīnu Kalniņu tika organizēts [[Specseminārs]] par Grafisko Domēna Specifisko Valodu atbalsta rīku būvi.

== Tēmas ==
Šeit ir vispārīgs tēmu uzskaitījums, kuru lēnā garā taisos detalizēt.
=== [[Domēnspecifiskas valodas]] ===
# Valoda likumu (juridiskā nozīmē), kas ietver sevī precīzus aprēķinus, atkļūdošanai.

=== [[Automātu Teorija un Formālās Gramatikas]] ===
# Magazīnas automātu "normālformas"
# Tīmekļa rīks galīgu automātu (determinētu, nedeterminētu, magazīnas) būvei, darbināšanai un pārveidei.
# Automātiska risinājuma pārbaude un novērtēšana
# Problēmu ģenerēšana

Bakalaura darbs, Artūrs Jānis Pētersons, [https://dspace.lu.lv/dspace/handle/7/38664 Galīgu determinētu automātu būves uzdevumu automātiska vērtēšana], 2018

=== [[Šahs]] ===
# Šaha uzdevumu MATS X GĀJIENOS ģenerēšana
# Šaha uzdevumu ''Skaistuma'' novērtēšana
# Vai cilvēks + dators spēlē labāk nekā tikai dators?
# Automātiska pozīcijas atpazīšana no foto

Bakalaura darbs, Dāvids Miezāks, [https://dspace.lu.lv/dspace/handle/7/51697 Šaha uzdevumu ģenerēšana], 2020

Bakalaura darbs, Olafs Eglājs, [https://dspace.lu.lv/dspace/handle/7/39670 Galda spēļu stāvokļu automātiska atpazīšana], 2018

=== [[Flexible Modeling]] ===
# Diagrammu zīmēšanas rīks (~ Powerpoint vai Visio)
# Diagrammu zīmēšanas rīks ar manuālu semantikas pievienošanu
# Diagrammu zīmēšanas rīks ar pusautomātisku semantikas pievienošanu (semantikas inference)
# Ne-grafu diagrammu formalizācija
# Diagrammas elementu formas vispārināšana, izmantojot [http://bl.ocks.org/mbostock/1021103 superformulu]
# [[Diagrammatiskas valodas kognitīvās efektivitātes novērtēšana]]

Bakalaura darbs, Ralfs Sedlenieks, [https://dspace.lu.lv/dspace/handle/7/47330 Ar superformulu ģenerētu objektu īpašības un pielietojumi], 2019

=== [[Vaicājumu valodas]] ===
# Grafiskas vaicājumu valodas izstrāde
# Grafiskas vaicājumu valodas rīka izstrāde
# Uz dabīgo valodu balstītas vaicājumu valodas izmantojamo konstrukciju sarežģītība
# Vaicājumu žurnāla izmantošana datu shēmas uzlabošanai
# GADBMS (GPU-accelerated Database Management Systems) un vaicājumu valodas priekš tām.

=== [[Ģenerēšana]] ===
# Regulāro izteiksmju ģenerēšana no piemēriem
# Bezkonteksta gramatiku ģenerēšana no piemēriem
# Regulāro izteiksmju ''krustvārdu mīklu'' automātiska ģenerēšana
# Dotajiem datiem līdzīgu datu ģenerēšana
# Ainavu ģenerēšana
# Induktīvā programmēšana

Bakalaura darbs, Agnese Rumkovska, [https://dspace.lu.lv/dspace/handle/7/50783 Algoritmiski ģenerēta mūzika], 2020

Bakalaura darbs, Dmitrijs Arkašarins, [https://dspace.lu.lv/dspace/handle/7/50767 Lietotāja vadīts reljefa ģenerēšanas algoritms], 2020

Bakalaura darbs, Inta Kovaļenko, [https://dspace.lu.lv/dspace/handle/7/35273 L-sistēmu pielietojums augu 3D modeļu ģenerēšanai], 2017

=== [[Spēles]] ===
# Procedural Content Generation (PCG) in Games
# General Game Playing
# Model Driven Engineering (MDE) spēļu izstrādē
# Galda spēļu botu izstrāde ar mašīnmācīšanās metodēm
# Domeina specifisku valodu (DSL) izstrāde spēļu aprakstīšanai
# Galīgu automātu, regulāru izteiksmju, gramatiku pielietojums spēļu izstrādē

Bakalaura darbs, Mārtiņš Kurmis, [https://dspace.lu.lv/dspace/handle/7/48329 Procedurāla trīsdimensionāla labirinta ģenerēšana], 2019

Bakalaura darbs, Emīls Kadiķis, [https://dspace.lu.lv/dspace/handle/7/39691 Dažādu galda spēļu spēlēšana ar vispārīgu mašīnmācīšanās algoritmu], 2018

Bakalaura darbs, Uvis Zviedris, [https://dspace.lu.lv/dspace/handle/7/33250 Datorspēļu līmeņu ar adaptīvu sarežģītības pakāpi procedurāla ģenerēšana], 2016

=== [[Kombinatoriskās Optimizācijas Problēmas]] ===
# Kombinatoriskās optimizācija universālo risinātāju (solveru) ietvari. Piemēram, Optaplanner, OR Tools.
# Vehicle Routing Problem With Time Windows - klasiskie risinājumi
# Vehicle Routing Problem With Time Windows - vai iespējams risināt ar mašīnmācīšanās metodēm?
# Optaplanner rīka lietošana stundu saraksta izveidošanai un optimizēšanai
# Grafiska domēnspecifiska valoda Optaplanner solveru definēšanai.

=== [[Sporta analītika]] ===
# Sporta rezultātu prognozēšana

Bakalaura darbs, Madars Zvaigzne, [https://dspace.lu.lv/dspace/handle/7/36289, Mašīnmācīšanās pielietojums sporta notikumu prognozēšanā]

Sākumlapa

2020-09-25T14:42:24Z

2019-02-26T09:28:09Z

Agree: MIT Sloan

Sporta analītikai veltīta konference [http://www.sloansportsconference.com MIT Sloan Sports Analytics Conference]

Sākumlapa

2019-02-26T09:26:30Z

Agree: Sports

Spēles

2019-02-26T09:23:36Z

Agree:

Runa iet gan par datorspēlēm, gan galda spēlēm! Ko var izdarīt ar datoru šajā lauciņā?
* spēlēt spēles (veidot ''botus'')
* veidot jaunas spēles
* '''veidot dažādus spēles elementus'''
* analizēt spēles (piemēram, meklēt labākās stratēģijas)
* ...

Pamatā pievērsīsimies dažādu spēļu elementu automātiskai veidošanai - [http://pcgbook.com/ grāmata par šo tēmu].

Spēles, kuru pamatā IR procedurālā ģenerēšana: [https://en.wikipedia.org/wiki/Elite:_Dangerous Elite: Dangerous] un [https://en.wikipedia.org/wiki/No_Man%27s_Sky No Man's Sky].

Izrādās gandrīz daudz dažādas formas iespējams aprakstīt ar [https://en.wikipedia.org/wiki/Superformula Superformulu]!

MDE (Model Driven Engineering) pielietojums spēļu izstrādē. Piemēram, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.553.7547&rep=rep1&type=pdf tā], [http://dsmforum.org/events/DSM06/Papers/1-Furtado.pdf tā] vai [http://researchonline.ljmu.ac.uk/205/1/JILR%20Journal%202011%20(S%20Tang%20%20M%20%20Hanneghan)%20-%20final.pdf tā (apskats tapis 2011. gadā)]. Tiek [http://www.jorisdormans.nl/pdf/dormans_modeltransformation.pdf lietotas arī modeļu transformācijas]. [http://www.jorisdormans.nl/pdf/ModelDrivenGameDesign.pdf Pārdomas par MDE piemērotību spēļu izstrādei].

[http://www.jorisdormans.nl Joris Dormans] raksta par spēļu izstrādi. Ir vērts palasīt viņa [http://www.jorisdormans.nl/pdf/dormans_engineering_emergence.pdf PhD Thesis].

Daudz spēļu laukumu (pasauļu) ģenerēšanā ir darījis [https://graphics.tudelft.nl/Publications-new/index.php?idAuthor=2087 Ruben Smelik]. Interesanta ir ideja [https://graphics.tudelft.nl/Publications-new/2009/STDB09a/STDB09a.pdf ģenerēt reljefu] (ainavu), kas ir līdzīga kādai esošai. Piemēram, būtu interesanti uzģenerēt tipisku Vidzemes vai Latgales ainavu.

Gribētos, ka kāds iemācītos ģenerēt [https://en.wikipedia.org/wiki/Heroes_of_Might_and_Magic_III Heroes of Might&Magic III] kartes! Kaut ko šajā virzienā [[HeroesIII Karšu Ģenerācija|esam iesākuši]].

Galda spēļu [http://eprints.qut.edu.au/31909/1/c31909.pdf automātiska izstrāde]. Šeit tiek izmantoti GGP (General Game Playing) elementi. Cameron Browne [http://eprints.qut.edu.au/17025/1/Cameron_Browne_Thesis.pdf PhD Thesis] ir laba lasāmviela par šo tēmu. Te ir arī par spēļu ''skaistumu''.

Par spēļu ģenerāciju savā [https://dspace.mit.edu/handle/1721.1/9164#files-area PhD Thesis] rakstīja arī Jon Orwant.

[http://livegamedesign.github.io/publications/ Live Game Design] - holandiešu spēļu izstrādes projekta rezultāti (Riemer van Rozen).

GGP (General Game Playing) - programmai iedod spēles noteikumus un tā spēlē! Šobrīd labi veicās determinētās pilnas informācijas spēlēs (kā šahs). Stanford-ā notiek [http://logic.stanford.edu/ggp/readings/retrospective.html sacensības]. Tomēr pagaidām netiek galā ar kāršu spēlēm (''nepilnas informācijas'', ''varbūtiska spēle'').

IGGP (Inductive General Game Playing) - spēlētājs novēro spēļu partijas un mēģina saprast spēles noteikumus!