Institutional Repository of Vilnius University
A* paieškos algoritmo variantų tyrimai sprendžiant NP sudėtingumo uždavinius /
Abstract
dc:descriptionSolving NP problems is a difficult challange: a slight increase in problem’s size causes an exponential increase in problem’s complexity. It soon becomes impossible to find a solution in a given time. To mitigate this issue, A* algorithm is introduced ‑ it can solve a subclass of NP problems. A* heuristics of selected problems are analyzed, comparing solution time and memory usage. After that, Weighted A* is analyzed. The algorithm sacrifices solution optimality for a speed gain in finding the suboptimal solution. Solution optimality loss is relatively compared to solution speed gain. After Weighted A* analysis, not all NP problems can be solved in an adequate time, therefore, a compromise between A* and Weighted A* ‑ Anytime Repairing A* (ARA*) ‑ is investigated. ARA* can find a suboptimal solution relatively quickly and then refine it ‑ making it more optimal. If needed, ARA* can be terminated mid execution and the algorithm still has given the best so far solution. Due to conclusions made in research sections Beam Search A* is analyzed. Lastly, it is explained which heuristics should be used in certain situations and which should be avoided. It is also explained when to use A*, Weighted A* and ARA*.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Visockas, Evaldas,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD192846504&prefLang=en_US