logic-programming/lab5.pl at master · doliom/logic-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
goal([3,_]).

next([X,Y],[9,Y],1):-
    X < 9.
next([X,Y],[0,Y],1):-
    X > 0.
next([X,Y],[X,5],1):-
    Y < 5.
next([X,Y],[X,0],1):-
    Y > 0.
next([X,Y],[0,Y1],1):-
    X > 0,
    Y+X =< 5,
    Y1 is X+Y.
next([X,Y],[Ost,5],1):-
    X > 0,
    X+Y > 5,
    Ost is (X+Y)-5.
next([X,Y],[X1,0],1):-
    Y > 0,
    X+Y =< 9,
    X1 is X+Y.
next([X,Y],[9,Ost],1):-
    Y > 0,
    X+Y > 9,
    Ost is (X+Y)-9.

solve(Node, Path/Cost) :-
  estimate(Node, E),
  astar([[Node]/0/E], Path/Cost/_).

estimate(State, E):-
    goal(Goal),
    estimate_count(State, Goal, E).

estimate_count(X,X,0):-!.

estimate_count([H1|_],[H2|_],Result):-
    Result is abs(H1-H2).

astar(All_Paths, Path) :-
  choose_min(All_Paths, Path),
  Path = [Node|_]/_/_,
  goal(Node).

astar(Paths, Solution) :-
  choose_min(Paths, BestPath),
  select(BestPath, Paths, OtherPaths),
  s0(BestPath, Situation),
  append(OtherPaths, Situation, NewPaths),
  astar(NewPaths, Solution).

next_step([Node|Path]/Cost/_, [NextNode,Node|Path]/NewCost/Est) :-
  next(Node, NextNode, StepCost),
  \+ member(NextNode, Path),
  NewCost is Cost + StepCost,
  estimate(NextNode, Est).

s0(Path, Situation) :-
  findall(S, next_step(Path,S), Situation).

choose_min([Path], Path) :- !.

choose_min([Path1/Cost1/Est1,_/Cost2/Est2|Paths], BestPath) :-
  Cost1 + Est1 =< Cost2 + Est2, !,
  choose_min([Path1/Cost1/Est1|Paths], BestPath).

choose_min([_|Paths], BestPath) :-
  choose_min(Paths, BestPath).