diplomsko delo
Jure Medvešek (Avtor), Ivan Bratko (Mentor)

Povzetek

Optimizacija prostorsko varčnega preiskovanja grafov z zaokroževanjem hevrističnih ocen

Ključne besede

preiskovanje grafov;optimizacija;granulacija;računalništvo;računalništvo in informatika;računalništvo in matematika;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [J. Medvešek]
UDK: 004(043.2)
COBISS: 9390164 Povezava se bo odprla v novem oknu
Št. ogledov: 53
Št. prenosov: 3
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Optimisation of space-saving graph search with approximate heuristic values
Sekundarni povzetek: Finding an optimal path in a state space is often very difficult in practise. The goal of this diploma thesis is to find a space efficient algorithm which finds an optimal solution within an acceptable time frame, even in large problem spaces. Algorithm A* is relatively fast, but it has exponential space complexity. Algorithms with linear space complexity can have quadratic time complexity, in terms of A*'s time complexity. In both cases we do not check for duplicates achieved by different paths. For this type of graphs we propose an optimization of the IDA* algorithm, where we granulate the heuristic function f. The new algorithm finds an optimal solution with time complexity O(N logN), where N is the number of nodes expanded by algorithm A*. Space complexity is linear in the length of the longest expanded path. The same idea can be applied to algorithm RBFS where RBFS can be even slightly faster than IDA*.
Sekundarne ključne besede: search;optimization;granulation;computer science;computer and information science;computer science and mathematics;diploma;
Vrsta datoteke: application/pdf
Vrsta dela (COBISS): Diplomsko delo
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 32 str.
ID: 24142493
Priporočena dela:
, metrike, metode in orodja
, zbirnik za spletne brskalnike