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

Abstract

Keywords

Data

Language:	Slovenian
Year of publishing:	2012
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[J. Medvešek]
UDC:	004(043.2)
COBISS:	9390164
Views:	53
Downloads:	3
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Optimisation of space-saving graph search with approximate heuristic values
Secondary abstract:	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*.
Secondary keywords:	search;optimization;granulation;computer science;computer and information science;computer science and mathematics;diploma;
File type:	application/pdf
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	32 str.
ID:	24142493