ans
algorithms start10 start12 start20 start30 start40
UCS 2565 Mem Mem Mem Mem
IDS 2407 13812 5297410 Time Time
A∗ 33 26 915 Mem Mem
IDA∗(Man) 29 21 952 17297 112571
IDA∗(Mis) 35 87 5214 3806765 Time
I change the predicate totdist .
Following code
totdist([], [], 0).
totdist([Tile|Tiles], [Position|Positions], D) :-
mandist(Tile, Position, D1),
totdist(Tiles, Positions, D2),
D is D1 + D2.
replaced by
Question 2
(a)
(b)
totdist([_|Tiles], [_|Positions], D):-
totdistHelp(Tiles, Positions, D).
totdistHelp([], [], 0).
totdistHelp([Tile|Tiles], [Position|Positions], D) :-
Tile == Position,
totdistHelp(Tiles, Positions, D).
totdistHelp([Tile|Tiles], [Position|Positions], D) :-
Tile \= Position,
totdistHelp(Tiles, Positions, Dl),
D is Dl + 1.
IDA∗(Man) has the highest efficiency. Next is A∗ , IDA∗(Mis) and IDS . UCS has the worst
efficiency.
start50-G start50-N start60-G start60-N start64-G start64-N
IDA* 50 1462512 60 321252368 64 1209086782
1.2 52 191438 62 230861 66 431033
1.4 66 116174 82 3673 94 188917
1.6 100 34647 148 55626 162 235852
1.8 236 6942 314 8816 344 2529
Greedy 164 5447 166 1617 184 2174
Following code
(c)
Question 3
(a)
(b)
depthlim(Path, Node, G, F_limit, Sol, G2) :-
nb_getval(counter, N),
N1 is N + 1,
nb_setval(counter, N1),
% write(Node),nl, % print nodes as they are expanded
s(Node, Node1, C),
not(member(Node1, Path)), % Prevent a cycle
G1 is G + C,
h(Node1, H1),
F1 is G1 + H1,
F1 =< F_limit,
depthlim([Node|Path], Node1, G1, F_limit, Sol, G2).
replaced by
depthlim(Path, Node, G, F_limit, Sol, G2) :-
nb_getval(counter, N),
N1 is N + 1,
nb_setval(counter, N1),
% write(Node),nl, % print nodes as they are expanded
s(Node, Node1, C),
not(member(Node1, Path)), % Prevent a cycle
G1 is G + C,
h(Node1, H1),
W is 1.2,
A is 2 - W,
Gx is A * G1,
H2 is W * H1,
F1 is Gx + H2,
F1 =< F_limit,
depthlim([Node|Path], Node1, G1, F_limit, Sol, G2).
Updates in (a) table.
From the table, we can see that when we increase w , generally the quality of solution will decrease and
the speed will increase. The greedy algorithm performs better than w=1.8 in both speed and quality.
(c)
(d)