#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil
from best_search import BestSearch
biggest = 99
start = LinkedList([(2, 2), (3, 1), (2, 3), (2, 1), (3, 3), (1, 2), (3, 2), (1, 3), (1, 1)])
goal = LinkedList([(1, 3), (2, 3), (3, 3), (1, 2), (2, 2), (3, 2), (1, 1), (2, 1), (3, 1)])
def is_goal(state):
return state == goal
def move_anyYC(numbers):
if numbers == Nil:
return
xb, yb = numbers.head
if xb > 1: # pohyb mezery doleva
xl = xb - 1
new_tail = replace((xl, yb), (xb, yb), numbers.tail)
yield (Cons((xl, yb), new_tail), 1)
if xb < 3: # pohyb mezery doprava
xr = xb + 1
new_tail = replace((xr, yb), (xb, yb), numbers.tail)
yield (Cons((xr, yb), new_tail), 1)
if yb > 1: # pohyb mezery dolu
yd = yb - 1
new_tail = replace((xb, yd), (xb, yb), numbers.tail)
yield (Cons((xb, yd), new_tail), 1)
if yb < 3: # pohyb mezery nahoru
yu = yb + 1
new_tail = replace((xb, yu), (xb, yb), numbers.tail)
yield (Cons((xb, yu), new_tail), 1)
def replace(x, y, xs):
if x == xs.head:
return Cons(y, xs.tail)
return Cons(xs.head, replace(x, y, xs.tail))
def h1(state):
a, b, c, d, e, f, g, h, i = state
return (a != (1, 3)) + (b != (2, 3)) + (c != (3, 3)) + \
(d != (1, 2)) + (e != (2, 2)) + (f != (3, 2)) + \
(g != (1, 1)) + (h != (2, 1)) + (i != (3, 1))
def h2(state):
a, b, c, d, e, f, g, h, i = state
return dist(a, (1, 3)) + dist(b, (2, 3)) + dist(c, (3, 3)) + \
dist(d, (1, 2)) + dist(e, (2, 2)) + dist(f, (3, 2)) + \
dist(g, (1, 1)) + dist(h, (2, 1)) + dist(i, (3, 1))
def dist(a, b): # manhattanska vzdalenost
xa, ya = a
xb, yb = b
return abs(xa-xb) + abs(ya-yb)
def writelist(xs):
writelist_(xs, 1)
def writelist_(xs, i):
if xs != Nil:
print("%d: %s" % (i, xs.head))
writelist_(xs.tail, i+1)
def length(xs):
if xs == Nil:
return 0
return 1 + length(xs.tail)
# demonstracni vypis
if __name__ == "__main__":
print("8-posunovacka, algoritmus A*\n")
print("Pocatecni stav: %s" % start)
print("\nNalezene reseni (heuristika h1):")
astar = BestSearch(biggest, is_goal, move_anyYC, h1)
solution = next(astar.search(start))
print("Prohledano %d stavu, vysledne reseni ma cenu %d." % (astar.total, length(solution)-1))
writelist(solution.reverse())
print("\nNalezene reseni (heuristika h2):")
astar = BestSearch(biggest, is_goal, move_anyYC, h2)
solution = next(astar.search(start))
print("Prohledano %d stavu, vysledne reseni ma cenu %d." % (astar.total, length(solution)-1))
writelist(solution.reverse())
8-posunovacka, algoritmus A*
Pocatecni stav: [(2, 2), (3, 1), (2, 3), (2, 1), (3, 3), (1, 2), (3, 2), (1, 3), (1, 1)]
Nalezene reseni (heuristika h1):
Prohledano 170244 stavu, vysledne reseni ma cenu 26.
1: [(2, 2), (3, 1), (2, 3), (2, 1), (3, 3), (1, 2), (3, 2), (1, 3), (1, 1)]
2: [(1, 2), (3, 1), (2, 3), (2, 1), (3, 3), (2, 2), (3, 2), (1, 3), (1, 1)]
3: [(1, 3), (3, 1), (2, 3), (2, 1), (3, 3), (2, 2), (3, 2), (1, 2), (1, 1)]
4: [(2, 3), (3, 1), (1, 3), (2, 1), (3, 3), (2, 2), (3, 2), (1, 2), (1, 1)]
5: [(2, 2), (3, 1), (1, 3), (2, 1), (3, 3), (2, 3), (3, 2), (1, 2), (1, 1)]
6: [(3, 2), (3, 1), (1, 3), (2, 1), (3, 3), (2, 3), (2, 2), (1, 2), (1, 1)]
7: [(3, 1), (3, 2), (1, 3), (2, 1), (3, 3), (2, 3), (2, 2), (1, 2), (1, 1)]
8: [(2, 1), (3, 2), (1, 3), (3, 1), (3, 3), (2, 3), (2, 2), (1, 2), (1, 1)]
9: [(1, 1), (3, 2), (1, 3), (3, 1), (3, 3), (2, 3), (2, 2), (1, 2), (2, 1)]
10: [(1, 2), (3, 2), (1, 3), (3, 1), (3, 3), (2, 3), (2, 2), (1, 1), (2, 1)]
11: [(2, 2), (3, 2), (1, 3), (3, 1), (3, 3), (2, 3), (1, 2), (1, 1), (2, 1)]
12: [(3, 2), (2, 2), (1, 3), (3, 1), (3, 3), (2, 3), (1, 2), (1, 1), (2, 1)]
13: [(3, 1), (2, 2), (1, 3), (3, 2), (3, 3), (2, 3), (1, 2), (1, 1), (2, 1)]
14: [(2, 1), (2, 2), (1, 3), (3, 2), (3, 3), (2, 3), (1, 2), (1, 1), (3, 1)]
15: [(1, 1), (2, 2), (1, 3), (3, 2), (3, 3), (2, 3), (1, 2), (2, 1), (3, 1)]
16: [(1, 2), (2, 2), (1, 3), (3, 2), (3, 3), (2, 3), (1, 1), (2, 1), (3, 1)]
17: [(2, 2), (1, 2), (1, 3), (3, 2), (3, 3), (2, 3), (1, 1), (2, 1), (3, 1)]
18: [(3, 2), (1, 2), (1, 3), (2, 2), (3, 3), (2, 3), (1, 1), (2, 1), (3, 1)]
19: [(3, 3), (1, 2), (1, 3), (2, 2), (3, 2), (2, 3), (1, 1), (2, 1), (3, 1)]
20: [(2, 3), (1, 2), (1, 3), (2, 2), (3, 2), (3, 3), (1, 1), (2, 1), (3, 1)]
21: [(1, 3), (1, 2), (2, 3), (2, 2), (3, 2), (3, 3), (1, 1), (2, 1), (3, 1)]
22: [(1, 2), (1, 3), (2, 3), (2, 2), (3, 2), (3, 3), (1, 1), (2, 1), (3, 1)]
23: [(2, 2), (1, 3), (2, 3), (1, 2), (3, 2), (3, 3), (1, 1), (2, 1), (3, 1)]
24: [(3, 2), (1, 3), (2, 3), (1, 2), (2, 2), (3, 3), (1, 1), (2, 1), (3, 1)]
25: [(3, 3), (1, 3), (2, 3), (1, 2), (2, 2), (3, 2), (1, 1), (2, 1), (3, 1)]
26: [(2, 3), (1, 3), (3, 3), (1, 2), (2, 2), (3, 2), (1, 1), (2, 1), (3, 1)]
27: [(1, 3), (2, 3), (3, 3), (1, 2), (2, 2), (3, 2), (1, 1), (2, 1), (3, 1)]
Nalezene reseni (heuristika h2):
Prohledano 7087 stavu, vysledne reseni ma cenu 26.
1: [(2, 2), (3, 1), (2, 3), (2, 1), (3, 3), (1, 2), (3, 2), (1, 3), (1, 1)]
2: [(1, 2), (3, 1), (2, 3), (2, 1), (3, 3), (2, 2), (3, 2), (1, 3), (1, 1)]
3: [(1, 3), (3, 1), (2, 3), (2, 1), (3, 3), (2, 2), (3, 2), (1, 2), (1, 1)]
4: [(2, 3), (3, 1), (1, 3), (2, 1), (3, 3), (2, 2), (3, 2), (1, 2), (1, 1)]
5: [(2, 2), (3, 1), (1, 3), (2, 1), (3, 3), (2, 3), (3, 2), (1, 2), (1, 1)]
6: [(2, 1), (3, 1), (1, 3), (2, 2), (3, 3), (2, 3), (3, 2), (1, 2), (1, 1)]
7: [(1, 1), (3, 1), (1, 3), (2, 2), (3, 3), (2, 3), (3, 2), (1, 2), (2, 1)]
8: [(1, 2), (3, 1), (1, 3), (2, 2), (3, 3), (2, 3), (3, 2), (1, 1), (2, 1)]
9: [(2, 2), (3, 1), (1, 3), (1, 2), (3, 3), (2, 3), (3, 2), (1, 1), (2, 1)]
10: [(3, 2), (3, 1), (1, 3), (1, 2), (3, 3), (2, 3), (2, 2), (1, 1), (2, 1)]
11: [(3, 3), (3, 1), (1, 3), (1, 2), (3, 2), (2, 3), (2, 2), (1, 1), (2, 1)]
12: [(2, 3), (3, 1), (1, 3), (1, 2), (3, 2), (3, 3), (2, 2), (1, 1), (2, 1)]
13: [(1, 3), (3, 1), (2, 3), (1, 2), (3, 2), (3, 3), (2, 2), (1, 1), (2, 1)]
14: [(1, 2), (3, 1), (2, 3), (1, 3), (3, 2), (3, 3), (2, 2), (1, 1), (2, 1)]
15: [(2, 2), (3, 1), (2, 3), (1, 3), (3, 2), (3, 3), (1, 2), (1, 1), (2, 1)]
16: [(3, 2), (3, 1), (2, 3), (1, 3), (2, 2), (3, 3), (1, 2), (1, 1), (2, 1)]
17: [(3, 1), (3, 2), (2, 3), (1, 3), (2, 2), (3, 3), (1, 2), (1, 1), (2, 1)]
18: [(2, 1), (3, 2), (2, 3), (1, 3), (2, 2), (3, 3), (1, 2), (1, 1), (3, 1)]
19: [(2, 2), (3, 2), (2, 3), (1, 3), (2, 1), (3, 3), (1, 2), (1, 1), (3, 1)]
20: [(3, 2), (2, 2), (2, 3), (1, 3), (2, 1), (3, 3), (1, 2), (1, 1), (3, 1)]
21: [(3, 3), (2, 2), (2, 3), (1, 3), (2, 1), (3, 2), (1, 2), (1, 1), (3, 1)]
22: [(2, 3), (2, 2), (3, 3), (1, 3), (2, 1), (3, 2), (1, 2), (1, 1), (3, 1)]
23: [(2, 2), (2, 3), (3, 3), (1, 3), (2, 1), (3, 2), (1, 2), (1, 1), (3, 1)]
24: [(2, 1), (2, 3), (3, 3), (1, 3), (2, 2), (3, 2), (1, 2), (1, 1), (3, 1)]
25: [(1, 1), (2, 3), (3, 3), (1, 3), (2, 2), (3, 2), (1, 2), (2, 1), (3, 1)]
26: [(1, 2), (2, 3), (3, 3), (1, 3), (2, 2), (3, 2), (1, 1), (2, 1), (3, 1)]
27: [(1, 3), (2, 3), (3, 3), (1, 2), (2, 2), (3, 2), (1, 1), (2, 1), (3, 1)]
| % priklad na reseni posunovacky pomoci A*
start([2/2, 3/1, 2/3, 2/1, 3/3, 1/2, 3/2, 1/3, 1/1]).
goal([1/3, 2/3, 3/3, 1/2, 2/2, 3/2, 1/1, 2/1, 3/1]).
% move pomoci pohybu mezery (cena vzdy 1)
move([XB/YB | Numbers], [XL/YB | NewNumbers], 1) :-
XB>1, % pohyb mezery doleva
XL is XB - 1, replace(XL/YB, XB/YB, Numbers, NewNumbers).
move([XB/YB | Numbers], [XR/YB | NewNumbers], 1) :-
XB<3, % pohyb mezery doprava
XR is XB + 1, replace(XR/YB, XB/YB, Numbers, NewNumbers).
move([XB/YB | Numbers], [XB/YD | NewNumbers], 1) :-
YB>1, % pohyb mezery dolu
YD is YB - 1, replace(XB/YD, XB/YB, Numbers, NewNumbers).
move([XB/YB | Numbers], [XB/YU | NewNumbers], 1) :-
YB<3, % pohyb mezery nahoru
YU is YB + 1, replace(XB/YU, XB/YB, Numbers, NewNumbers).
% replace
replace(A,B,[A|T],[B|T]):-!.
replace(A,B,[H|T1],[H|T2]) :- replace(A,B,T1,T2).
% heuristika h1
h(State,H):-
cnt_1(State,Ok_1),
cnt_2(State,Ok_2),
cnt_3(State,Ok_3),
cnt_4(State,Ok_4),
cnt_5(State,Ok_5),
cnt_6(State,Ok_6),
cnt_7(State,Ok_7),
cnt_8(State,Ok_8),
H is Ok_1+Ok_2+Ok_3+Ok_4+Ok_5+Ok_6+Ok_7+Ok_8.
%write('H['),write(State),write(']='),write(H),nl.
%goal([1/3, 2/3, 3/3, 1/2, 2/2, 3/2, 1/1, 2/1, 3/1]).
cnt_1([_,2/3|_],0):-!. cnt_1(_,1).
cnt_2([_,_,3/3|_],0):-!. cnt_2(_,1).
cnt_3([_,_,_,1/2|_],0):-!. cnt_3(_,1).
cnt_4([_,_,_,_,2/2|_],0):-!. cnt_4(_,1).
cnt_5([_,_,_,_,_,3/2|_],0):-!. cnt_5(_,1).
cnt_6([_,_,_,_,_,_,1/1|_],0):-!. cnt_6(_,1).
cnt_7([_,_,_,_,_,_,_,2/1|_],0):-!. cnt_7(_,1).
cnt_8([_,_,_,_,_,_,_,_,3/1],0):-!. cnt_8(_,1).
%
biggest(99).
writelist(L):-writelist(L,1).
writelist([E|L],I):-write(I),write(': '),write(E),nl,I1 is I+1,writelist(L,I1).
writelist([],_).
run:-
['4.1_9.pl'], nl,
write('8-posunovacka, algoritmus A*, heuristika h1'), nl, nl,
start(Start),
write('Pocatecni stav: '), write(Start), nl,
bestsearch(Start, Solution),
write('Nalezene reseni:'),nl,
reverse(Solution,RSolution),
writelist(RSolution).
% s heuristikou h1 vyzaduje hodne pameti (pro d=26)
:- set_prolog_stack(local, limit(256 000 000)). % vyzaduje 64-bit system
:- run.
% vim: set ft=prolog:
8-posunovacka, algoritmus A*, heuristika h1
Pocatecni stav: [2/2,3/1,2/3,2/1,3/3,1/2,3/2,1/3,1/1]
Nalezene reseni:
1: [2/2,3/1,2/3,2/1,3/3,1/2,3/2,1/3,1/1]
2: [1/2,3/1,2/3,2/1,3/3,2/2,3/2,1/3,1/1]
3: [1/3,3/1,2/3,2/1,3/3,2/2,3/2,1/2,1/1]
4: [2/3,3/1,1/3,2/1,3/3,2/2,3/2,1/2,1/1]
5: [2/2,3/1,1/3,2/1,3/3,2/3,3/2,1/2,1/1]
6: [2/1,3/1,1/3,2/2,3/3,2/3,3/2,1/2,1/1]
7: [1/1,3/1,1/3,2/2,3/3,2/3,3/2,1/2,2/1]
8: [1/2,3/1,1/3,2/2,3/3,2/3,3/2,1/1,2/1]
9: [2/2,3/1,1/3,1/2,3/3,2/3,3/2,1/1,2/1]
10: [3/2,3/1,1/3,1/2,3/3,2/3,2/2,1/1,2/1]
11: [3/3,3/1,1/3,1/2,3/2,2/3,2/2,1/1,2/1]
12: [2/3,3/1,1/3,1/2,3/2,3/3,2/2,1/1,2/1]
13: [1/3,3/1,2/3,1/2,3/2,3/3,2/2,1/1,2/1]
14: [1/2,3/1,2/3,1/3,3/2,3/3,2/2,1/1,2/1]
15: [2/2,3/1,2/3,1/3,3/2,3/3,1/2,1/1,2/1]
16: [3/2,3/1,2/3,1/3,2/2,3/3,1/2,1/1,2/1]
17: [3/1,3/2,2/3,1/3,2/2,3/3,1/2,1/1,2/1]
18: [2/1,3/2,2/3,1/3,2/2,3/3,1/2,1/1,3/1]
19: [2/2,3/2,2/3,1/3,2/1,3/3,1/2,1/1,3/1]
20: [3/2,2/2,2/3,1/3,2/1,3/3,1/2,1/1,3/1]
21: [3/3,2/2,2/3,1/3,2/1,3/2,1/2,1/1,3/1]
22: [2/3,2/2,3/3,1/3,2/1,3/2,1/2,1/1,3/1]
23: [2/2,2/3,3/3,1/3,2/1,3/2,1/2,1/1,3/1]
24: [2/1,2/3,3/3,1/3,2/2,3/2,1/2,1/1,3/1]
25: [1/1,2/3,3/3,1/3,2/2,3/2,1/2,2/1,3/1]
26: [1/2,2/3,3/3,1/3,2/2,3/2,1/1,2/1,3/1]
27: [1/3,2/3,3/3,1/2,2/2,3/2,1/1,2/1,3/1]
|