Ohjelman rakenne tällä hetkellä:
-
"pathfinding" paketti: PathFinding(Main)
-
"pathfinding.DataStructures" paketti: ArrayList, HashMap, HashSet, Node, PriorityQueue
-
"pathfinding.PathFinders" paketti: PathFinder (rajapinta), AStar, JPS
-
"pathfinding.Visuals" paketti: MapReader, UI, VisualRep
Koska JPS on toinen versio A*:ista, niin molemmilla on samat Aika- ja tilavaativuudet.
Aikavaativuus on sama kuin Dijkstralla, mutta se riippuu mitä heuristiikkaa käyttää. Tässä tapauksessa käytän priority queue:tä, niin
pahimman tapauksen aikavaativuus on: O(|E| + |V|log|V|), missä E on "kaaret" ja V on "solmut".
Pahimman tapauksen tilavaativuus: O(|E| + |V|log|V|), missä E on "kaaret" ja missä V on "solmut".
Testasin A*:in ja JPS:sän suorituskyvyn suorittamalla molemmat 10 kertaa käyttäen eri karttoja.
Testattu 27.4.2018
test.map
A* suorituskyky keskiarvo: 11.8ms.
JPS suorituskyky keskiarvo: 9.1ms.
maze2.map
Testattu 8.5.2018
A* suorituskyky keskiarvo: 71.4ms.
JPS suorituskyky keskiarvo: 58.3ms.
Daniel Harabor ja Alban Grastien dokumentti JPS:stä