程序代写代做代考 algorithm ans

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)