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

Povzetek

Ključne besede

Podatki

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:

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