prikaz prve stranice dokumenta Algoritam smanjivanja prostora stanja pretrage
  Preuzmi
PDF 1.93 MB
završni rad
Algoritam smanjivanja prostora stanja pretrage
Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2020. urn:nbn:hr:166:921546
Sokol, Domina
Sveučilište u Splitu
Prirodoslovno-matematički fakultet
Odjel za informatiku

Institucijski repozitorij: repozitorij.pmfst.unist.hr

Citirajte ovaj rad

Sokol, D. (2020). Algoritam smanjivanja prostora stanja pretrage (Završni rad). Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol, Domina. "Algoritam smanjivanja prostora stanja pretrage." Završni rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2020. https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol, Domina. "Algoritam smanjivanja prostora stanja pretrage." Završni rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2020. https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol, D. (2020). 'Algoritam smanjivanja prostora stanja pretrage', Završni rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, citirano: 30.11.2024., https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol D. Algoritam smanjivanja prostora stanja pretrage [Završni rad]. Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet; 2020 [pristupljeno 30.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:921546

D. Sokol, "Algoritam smanjivanja prostora stanja pretrage", Završni rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, Split, 2020. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:921546

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:166:921546
Podaci o radu
NaslovAlgoritam smanjivanja prostora stanja pretrage
Naslov (engleski)State space pruning
AutorDomina Sokol
MentorGoran Zaharija (mentor)
Član povjerenstvaGoran Zaharija (predsjednik povjerenstva)
Član povjerenstvaSaša Mladenović (član povjerenstva)
Član povjerenstvaDivna Krpan (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Splitu
Prirodoslovno-matematički fakultet
(Odjel za informatiku)
Split
Datum i država obrane2020-09-18, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
Redukcija prostora stanja je tehnika optimizacije izvršenja heurističkih algoritama. Dijeli se na dva dijela prema kriteriju optimalnosti pronađenog rješenja: dopustiva redukcija prostora stanja i redukcija prostora stanja uz očuvanje rješenja. Prva skupina metoda odnosi se na one koje čuvaju optimalno rješenje – redukcija podstringova, detekcija slijepih ulica i redukcija pomoću simetrije. Druga skupina odnosi se na one metode koje nužno ne čuvaju optimalno rješenje, ali i dalje osiguravaju pronalazak nekog rješenja (redukcija pomoću makro akcija, odbacivanje nebitnog i redukcija parcijalnog uređaja). U ovom završnom radu je korišten primjer pretraživanja labirinta. Prikazana su dva algoritma koja koriste ideje redukcije prostora stanja – Aho-Corasick algoritam i IDLA*.
Sažetak (engleski)
State space pruning is an optimization technique applied to heuristic algorithms. It is divided into two parts according to the optimality of a found solution: admissible state space pruning and non-admissible state space pruning. The first group of methods is regarding to those which preserve the optimal solution to the given problem – substring pruning, dead-end pruning and symmetry reduction. The other group of methods is regarding to those which do not necessarily preserve the optimal solution, but do ensure some solution (macro problem solving, relevance cuts, partial order reduction). In this bachelor thesis, the example of a labyrinth is frequently used. Two algorthims are shown which use the basic ideas of state space pruning – Aho-Corasick and IDLA*.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:166:921546
Studijski programNaziv: Matematika i informatika; smjerovi: nastavnički
Smjer: nastavnički
Vrsta studija: sveučilišni
Stupanj studija: preddiplomski
Akademski / stručni naziv: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) matematike i informatike (univ. bacc. math. et inf.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2021-01-27 11:28:21