prikaz prve stranice dokumenta Algoritam smanjivanja prostora stanja pretrage
  Download
PDF 1.93 MB
undergraduate thesis
Algoritam smanjivanja prostora stanja pretrage
Split: University of Split, University of Split, Faculty of science, 2020. urn:nbn:hr:166:921546
Sokol, Domina
University of Split
Faculty of Science
Department of Informatics

Institutional repository: Repository of Faculty of Science

Cite this document

Sokol, D. (2020). Algoritam smanjivanja prostora stanja pretrage (Undergraduate thesis). Split: University of Split, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol, Domina. "Algoritam smanjivanja prostora stanja pretrage." Undergraduate thesis, University of Split, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol, Domina. "Algoritam smanjivanja prostora stanja pretrage." Undergraduate thesis, University of Split, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol, D. (2020). 'Algoritam smanjivanja prostora stanja pretrage', Undergraduate thesis, University of Split, Faculty of Science, accessed 27 November 2024, https://urn.nsk.hr/urn:nbn:hr:166:921546

Sokol D. Algoritam smanjivanja prostora stanja pretrage [Undergraduate thesis]. Split: University of Split, Faculty of Science; 2020 [cited 2024 November 27] Available at: https://urn.nsk.hr/urn:nbn:hr:166:921546

D. Sokol, "Algoritam smanjivanja prostora stanja pretrage", Undergraduate thesis, University of Split, Faculty of Science, Split, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:166:921546

Metadata
TitleAlgoritam smanjivanja prostora stanja pretrage
Title (english)State space pruning
AuthorDomina Sokol
MentorGoran Zaharija (mentor)
Committee memberGoran Zaharija (predsjednik povjerenstva)
Committee memberSaša Mladenović (član povjerenstva)
Committee memberDivna Krpan (član povjerenstva)
GranterUniversity of Split
Faculty of Science
(Department of Informatics)
Split
Defense date and country2020-09-18, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
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*.
Abstract (english)
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*.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:166:921546
Study programmeTitle: Mathematics and Computer Science; specializations in: major in teaching
Course: major in teaching
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) matematike i informatike (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) matematike i informatike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2021-01-27 11:28:21