---
# System prepended metadata

title: JPS - ASTAR dokumentacja

---

# JPS - ASTAR dokumentacja

## Skład zespołu:

* Damian Kolaska
* Kamil Przybyła

## Ilustracja grafu

![](https://i.imgur.com/u4DOoUj.png)

## Prezentacja działania

Uruchamiamy procedurę poszukującą ścieżki `Path` z wierzchołka `a`. Użytkownik będzie mógł wybierać który wierzchołek ma zostać odwiedzony z listy maksymalnie 4-elementowej, a głębokość przeszukiwań będzie równa 2. 
![](https://i.imgur.com/oNICWEO.png)

Do kolejki został dodany jedynie węzeł początkowy, więc użytkownik może wybrać tylko jeden węzeł. Podejmujemy jedyną możliwą decyzję.
![](https://i.imgur.com/pahmyqj.png)

Z listy `Nodes` zostanie wybrany element o indeksie 1.
![](https://i.imgur.com/DHaFsC6.png)

Do kolejki dodano węzły dostępne z odwiedzonego węzła `a`, a głębokość przeszukiwania została zwiększona.
![](https://i.imgur.com/1xW3Tce.png)

Węzeł `a` jest umieszczony w `ClosedSet`, ponieważ był już odwiedzony. Sugerujemy algorytmowi aby w pierwszej kolejności odwiedził węzeł `b`, pozostawiając punkt wyboru.
![](https://i.imgur.com/FNDVqAf.png)

Z listy `Nodes` zostanie wybrany element o indeksie 1.
![](https://i.imgur.com/e1o9U2B.png)

Kolejka została poszerzona o sąsiadów węzła `b`.
![](https://i.imgur.com/ybYonXx.png)

Zmuszamy algorytm do odwiedzenia węzła `g`, z którego nie ma możliwości wyjścia.
![](https://i.imgur.com/fmcJNDj.png)

Z listy `Nodes` zostanie wybrany element o indeksie 2.
![](https://i.imgur.com/RBkDCzI.png)

Głębokość przeszukiwań zostaje przekroczona i nie zezwalamy na zwiększenie jej, co skutkuje nawrotem do procedury `choose_element`.
![](https://i.imgur.com/y0BxecB.png)

Interpreter wraca do punktu wyboru, w którym wybierał element z listy `[1, 2]` i tym razem zostanie wybiera element o indeksie 2.
![](https://i.imgur.com/2HDlvJj.png)

Dzięki nawrotowi głębokość została zmniejszona. Kolejka tym razem zawiera węzły sąsiadujące z `c`.
![](https://i.imgur.com/qwwPn6j.png)

W `ClosedSet` widzimy, że rzeczywiście został odwiedzony węzeł `c`. Prowadzimy algorytm ścieżką przechodzącą przez węzeł `d`, ale nie ma to szczególnego znaczenia.
![](https://i.imgur.com/iI4Sngj.png)

Wybrany zostaje element o indeksie 2.
![](https://i.imgur.com/BUTRodF.png)

Znów została przekroczona maksymalna głębokość przeszukiwania. Tym razem zgadzamy się na zwiększenie jej, aby algorytm był w stanie dostać się do celu.
![](https://i.imgur.com/DrD2Y6C.png)

Zostaje wywołana ta sama procedura `search_A_star`, ale ze zwiększonym limitem głębokości, zatem nie jesteśmy pytani o zwiększenie limitu.
![](https://i.imgur.com/QfhUUNY.png)

Węzeł `d` został odwiedzony i dodano jego sąsiadów do kolejki. Wybieramy węzeł `m` jako następny, aby algorytm zakończył swe działanie.
![](https://i.imgur.com/hnPu1Mb.png)

Wybrany zostaje jedyny z możliwych elementów i wyświetlana jest odkryta ścieżka w grafia (`a->c->d->m`).
![](https://i.imgur.com/QFGf4iA.png)

## Opis funkcji
**start_A_star(InitState, PathCost, N, MaxDepth)**
Główna funkcja uruchamiająca procedurę. Parametr *N* określa maksymalną liczbę węzłów przedstawianych użytkownikowi, **MaxDepth** z kolei wyznacza maksymalną głębokość przeszukiwania.
```
start_A_star(InitState, PathCost, N, MaxDepth) :-
	score(InitState, 0, 0, InitCost, InitScore),
	search_A_star( [node(InitState, nil, nil, InitCost, InitScore ) ], [ ], PathCost, N, 0, MaxDepth).
```
**search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth)**
Podobnie jak w przypadku **start_A_star** funkcja przyjmuje dodatkowe paramtery *N* i *MaxDepth*. Poza tym na wejściu dostaje także *Depth* określającą obecną głębokość przeszukiwania.
```
search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	my_trace(1, search_A_star, 1, ['Queue'/Queue, 'Depth'/Depth]),
	Depth =< MaxDepth,
	fetch(Node, Queue, ClosedSet, N),
	continue(Node, Queue, ClosedSet, PathCost, N, Depth, MaxDepth).
    
search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	Depth > MaxDepth,
	write("Limit korków osiągnięty. Wprowadź tak, aby zwiększyć limit."), nl,
	read(Input),
	Input = tak,
	NewMaxDepth is MaxDepth + 1,
	search_A_star(Queue, ClosedSet, PathCost, N, Depth, NewMaxDepth).
```
**continue(Node, RestQueue, ClosedSet, Path, N, Depth, MaxDepth)**
```
continue(node(State, Action, Parent, Cost, _), _, ClosedSet, path_cost(Path, Cost), _, _, _) :-
	goal( State), !,
	build_path(node(Parent, _ ,_ , _ , _ ) , ClosedSet, [Action/State], Path) .

continue(Node, RestQueue, ClosedSet, Path, N, Depth, MaxDepth) :-
	expand(Node, NewNodes),
	insert_new_nodes(NewNodes, RestQueue, NewQueue),
	NewDepth is Depth + 1,
	search_A_star(NewQueue, [Node | ClosedSet ], Path, N, NewDepth, MaxDepth).
```
**fetch_n(Nodes, N, Queue, ClosedSet)**
Procedura wyjmuje pierwsze *N* węzłów nienależących do *ClosedSet* z kolejki *Queue*. Wynik umieszcza w *Nodes*.
```
fetch_n([], 0, _, _).
fetch_n([], _, [], _).

fetch_n([H | RestNodes], N, [H | RestQueue], ClosedSet) :-
	N \= 0,
	\+ member(H, ClosedSet), !,
	NewN is N - 1,
	fetch_n(RestNodes, NewN, RestQueue, ClosedSet).

fetch_n(Nodes, N, [ _ |RestQueue], ClosedSet) :-
	N \= 0,
	fetch_n(Nodes, N, RestQueue, ClosedSet).
```
**choose_element(X, ChoiceList)**
Wybiera element z *ChoiceList* i umieszcza go w *X*.
```
choose_element(X, [X | _]) :-
	my_trace(1, choose_element, 1, ['X'/X]).
choose_element(X, [_ | Rest]) :-
	choose_element(X, Rest).
```
**select_nth(Node, Nodes, Index)**
Wybiera *Nodes[Index]* i umieszcza go w *Node*. 
```
select_nth(Node, [Node | _], 1).
select_nth(Node, [_ | Rest], Idx) :-
	Idx \= 1,
	NewIdx is Idx - 1,
	select_nth(Node, Rest, NewIdx).
```
**fetch(Node, Queue, ClosedSet, N)**
Wyciąga *N* elementów z kolejki *Queue*, prezentuje je użytkownikowi, prosząć aby podał kolejność odwiedzania węzłów. Następnie zwraca kolejne węzły zgodnie z kolejnością zdefiniowaną przez użytkownika.

Procedury **expand**, **score**, **insert_new_nodes**, **insert_p_queue**, **build_path** oraz **del** pozostają bez zmian.

## Kod źródłowy programu
```
:- include('my_trace.pl').

start_A_star(InitState, PathCost, N, MaxDepth) :-
	score(InitState, 0, 0, InitCost, InitScore),
	search_A_star( [node(InitState, nil, nil, InitCost, InitScore ) ], [ ], PathCost, N, 0, MaxDepth).

search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	my_trace(1, search_A_star, 1, ['Queue'/Queue, 'Depth'/Depth]),
	Depth =< MaxDepth,
	fetch(Node, Queue, ClosedSet, N),
	continue(Node, Queue, ClosedSet, PathCost, N, Depth, MaxDepth).

search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	Depth > MaxDepth,
	write("Limit korków osiągnięty. Wprowadź tak, aby zwiększyć limit."), nl,
	read(Input),
	Input = tak,
	NewMaxDepth is MaxDepth + 1,
	search_A_star(Queue, ClosedSet, PathCost, N, Depth, NewMaxDepth).

continue(node(State, Action, Parent, Cost, _), _, ClosedSet, path_cost(Path, Cost), _, _, _) :-
	goal( State), !,
	build_path(node(Parent, _ ,_ , _ , _ ) , ClosedSet, [Action/State], Path) .

continue(Node, RestQueue, ClosedSet, Path, N, Depth, MaxDepth) :-
	expand(Node, NewNodes),
	insert_new_nodes(NewNodes, RestQueue, NewQueue),
	NewDepth is Depth + 1,
	search_A_star(NewQueue, [Node | ClosedSet ], Path, N, NewDepth, MaxDepth).

fetch_n([], 0, _, _).
fetch_n([], _, [], _).

fetch_n([H | RestNodes], N, [H | RestQueue], ClosedSet) :-
	N \= 0,
	\+ member(H, ClosedSet), !,
	NewN is N - 1,
	fetch_n(RestNodes, NewN, RestQueue, ClosedSet).

fetch_n(Nodes, N, [ _ |RestQueue], ClosedSet) :-
	N \= 0,
	fetch_n(Nodes, N, RestQueue, ClosedSet).

choose_element(X, [X | _]) :-
	my_trace(1, choose_element, 1, ['X'/X]).
choose_element(X, [_ | Rest]) :-
	choose_element(X, Rest).

select_nth(Node, [Node | _], 1).
select_nth(Node, [_ | Rest], Idx) :-
	Idx \= 1,
	NewIdx is Idx - 1,
	select_nth(Node, Rest, NewIdx).

fetch(Node, Queue, ClosedSet, N) :-
	fetch_n(Nodes, N, Queue, ClosedSet),
	my_trace(1, fetch, 1, ['ClosedSet'/ClosedSet, 'Nodes'/Nodes]),
	write("Wprowadź listę wyboru:"), nl,
	read(ChoiceList),
	choose_element(ChoosedElement, ChoiceList),
	select_nth(Node, Nodes, ChoosedElement).

expand(node(State, _ ,_ , Cost, _ ), NewNodes)  :-
	findall(node(ChildState, Action, State, NewCost, ChildScore) ,
			(succ(State, Action, StepCost, ChildState),
			    score(ChildState, Cost, StepCost, NewCost, ChildScore)),
			NewNodes).


score(State, ParentCost, StepCost, Cost, FScore)  :-
	Cost is ParentCost + StepCost ,
	hScore(State, HScore),
	FScore is Cost + HScore.


insert_new_nodes( [ ], Queue, Queue).

insert_new_nodes( [Node|RestNodes], Queue, NewQueue) :-
	insert_p_queue(Node, Queue, Queue1),
	insert_new_nodes( RestNodes, Queue1, NewQueue).


insert_p_queue(Node, [ ], [Node]) :- !.

insert_p_queue(node(State, Action, Parent, Cost, FScore),
		[node(State1, Action1, Parent1, Cost1, FScore1)|RestQueue],
			[node(State1, Action1, Parent1, Cost1, FScore1)|Rest1] )  :-
	FScore >= FScore1,  ! ,
	insert_p_queue(node(State, Action, Parent, Cost, FScore), RestQueue, Rest1).

insert_p_queue(node(State, Action, Parent, Cost, FScore),  Queue,
				[node(State, Action, Parent, Cost, FScore)|Queue]).


build_path(node(nil, _, _, _, _), _, Path, Path) :- !.

build_path(node(EndState, _, _, _, _), Nodes, PartialPath, Path) :-
	del(Nodes, node(EndState, Action, Parent, _, _), Nodes1) ,
	build_path( node(Parent,_ ,_ , _ , _ ) , Nodes1, [Action/EndState|PartialPath],Path).


del([X|R],X,R).
del([Y|R],X,[Y|R1]) :-
	X\=Y,
	del(R,X,R1).

succ(a, ab, 2, b).
succ(b, bf, 3, f).
succ(a, ac, 3, c).
succ(b, bg, 4, g).
succ(c, cd, 2, d).
succ(d, dm, 1, m).
succ(c, ce, 3, e).
succ(e, em, 5, m).
succ(f, fm, 3, m).

goal(m).

hScore(a, 4).
hScore(b, 4).
hScore(f, 7).
hScore(g, 1).
hScore(m, 0).
hScore(c, 3).
hScore(d, 1).
hScore(e, 4).
```

