Jezik: | Slovenski jezik |
---|---|
Leto izida: | 2012 |
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 |
Št. ogledov: | 53 |
Št. prenosov: | 3 |
Ocena: | 0 (0 glasov) |
Metapodatki: |
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 |