API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 9th, 2016
80
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.08 KB | None | 0 0
raw download clone embed print report
  1. #encoding: utf8
  2.  
  3. from tpi3 import *
  4.  
  5. import math
  6. import time
  7.  
  8. # -------------------------------------------------------------
  9. # Dominio de aplicacao para exercicios sobre pesquisa em arvore
  10. # -------------------------------------------------------------
  11.  
  12. class Cidades(SearchDomain):
  13. def __init__(self,connections, coordinates):
  14. self.connections = connections
  15. self.coordinates = coordinates
  16. def actions(self,Cidade):
  17. actlist = []
  18. for (C1,C2,D) in self.connections:
  19. if (C1==Cidade):
  20. actlist += [(C1,C2)]
  21. elif (C2==Cidade):
  22. actlist += [(C2,C1)]
  23. return actlist
  24. def result(self,state,action):
  25. (C1,C2) = action
  26. if C1==state:
  27. return C2
  28. def cost(self,state,action):
  29. (A,B) = action
  30. if A != state:
  31. return None
  32. for (P,Q,D) in self.connections:
  33. if (P==A and Q==B) or (P==B and Q==A):
  34. return D
  35. return None
  36. def heuristic(self,state,goal):
  37. (x1,y1) = self.coordinates[state]
  38. (x2,y2) = self.coordinates[goal]
  39. return math.sqrt((x1-x2)**2 + (y1-y2)**2)
  40.  
  41. cidades_portugal = Cidades(
  42. # Ligacoes por estrada
  43. [
  44. ('Coimbra', 'Leiria', 73),
  45. ('Aveiro', 'Agueda', 35),
  46. ('Porto', 'Agueda', 79),
  47. ('Agueda', 'Coimbra', 45),
  48. ('Viseu', 'Agueda', 78),
  49. ('Aveiro', 'Porto', 78),
  50. ('Aveiro', 'Coimbra', 65),
  51. ('Figueira', 'Aveiro', 77),
  52. ('Braga', 'Porto', 57),
  53. ('Viseu', 'Guarda', 75),
  54. ('Viseu', 'Coimbra', 91),
  55. ('Figueira', 'Coimbra', 52),
  56. ('Leiria', 'Castelo Branco', 169),
  57. ('Figueira', 'Leiria', 62),
  58. ('Leiria', 'Santarem', 78),
  59. ('Santarem', 'Lisboa', 82),
  60. ('Santarem', 'Castelo Branco', 160),
  61. ('Castelo Branco', 'Viseu', 174),
  62. ('Santarem', 'Evora', 122),
  63. ('Lisboa', 'Evora', 132),
  64. ('Evora', 'Beja', 80), # 105, para ser admissível
  65. ('Lisboa', 'Beja', 178),
  66. ('Faro', 'Beja', 147),
  67. ('Braga', 'Guimaraes', 25),
  68. ('Porto', 'Guimaraes', 44),
  69. ('Guarda', 'Covilha', 46),
  70. ('Viseu', 'Covilha', 57),
  71. ('Castelo Branco', 'Covilha', 62)
  72. ],
  73.  
  74. # Coordenadas das cidades:
  75. { 'Aveiro': (41,215),
  76. 'Figueira': ( 24, 161),
  77. 'Coimbra': ( 60, 167),
  78. 'Agueda': ( 58, 208),
  79. 'Viseu': ( 104, 217),
  80. 'Braga': ( 61, 317),
  81. 'Porto': ( 45, 272),
  82. 'Lisboa': ( 0, 0),
  83. 'Santarem': ( 38, 59),
  84. 'Leiria': ( 28, 115),
  85. 'Castelo Branco': ( 140, 124),
  86. 'Guarda': ( 159, 204),
  87. 'Evora': (120, -10),
  88. 'Beja': (125, -110),
  89. 'Faro': (120, -250),
  90. 'Guimaraes': ( 71, 300),
  91. 'Covilha': ( 130, 175)
  92. } )
  93.  
  94.  
  95. p = SearchProblem(cidades_portugal,'Braga','Faro')
  96. print("-------------------------------------------")
  97. t = MyTree(p,'depth')
  98. print("Solution: {0}".format(t.search2()))
  99. print(t.solution_cost,t.tree_size)
  100. print("-------------------------------------------")
  101. t = MyTree(p,'banbou')
  102. print("Solution: {0}".format(t.search2()))
  103. print(t.solution_cost,t.tree_size)
  104. print("-------------------------------------------")
  105.  
  106. q = SearchProblem(cidades_portugal,'Guarda','Lisboa')
  107. r = MyTree(q,'banbou')
  108. print("Solution: {0}".format(r.search2()))
  109. print(r.solution_cost,r.tree_size)
  110. print("-------------------------------------------")
  111.  
  112.  
  113. # -------------------------------------------------------------
  114. # Rede de Bayes para testar o método markov_blanket()
  115. # -------------------------------------------------------------
  116.  
  117. bn = MyBN()
  118.  
  119. bn.add('a',[],0.003)
  120. bn.add('b_a',[],0.002)
  121. bn.add('c_s',[('a',True )],0.48)
  122. bn.add('c_s',[('a',False)],0.08)
  123.  
  124. bn.add('d',[],0.01)
  125. bn.add('m_f',[],0.01)
  126. bn.add('b_v',[('c_s',True ),('b_a',True )],0.18)
  127. bn.add('b_v',[('c_s',True ),('b_a',False)],0.02)
  128. bn.add('b_v',[('c_s',False),('b_a',True )],0.90)
  129. bn.add('b_v',[('c_s',False),('b_a',False)],0.68)
  130. bn.add('s_m',[],0.05)
  131.  
  132. bn.add('s_p',[],0.3)
  133. bn.add('v_p',[('m_f',True),('d',True ),('b_v',True )],0.003)
  134. bn.add('v_p',[('m_f',True),('d',True ),('b_v',False )],0.12)
  135. bn.add('v_p',[('m_f',True),('d',False ),('b_v',True)],0.08)
  136. bn.add('v_p',[('m_f',True),('d',False),('b_v',False )],0.01)
  137. bn.add('v_p',[('m_f',False),('d',True),('b_v',True)],0.04)
  138. bn.add('v_p',[('m_f',False),('d',True ),('b_v',False)],0.07)
  139. bn.add('v_p',[('m_f',False),('d',False),('b_v',True )],0.13)
  140. bn.add('v_p',[('m_f',False),('d',False),('b_v',False)],0.09)
  141. bn.add('h',[('b_v',True )],0.44)
  142. bn.add('h',[('b_v',False)],0.89)
  143. bn.add('s_s',[('s_m',True),('m_f',True ),('b_v',True )],0.3)
  144. bn.add('s_s',[('s_m',True),('m_f',True ),('b_v',False )],0.21)
  145. bn.add('s_s',[('s_m',True),('m_f',False ),('b_v',True)],0.34)
  146. bn.add('s_s',[('s_m',True),('m_f',False),('b_v',False )],0.12)
  147. bn.add('s_s',[('s_m',False),('m_f',True),('b_v',True)],0.15)
  148. bn.add('s_s',[('s_m',False),('m_f',True ),('b_v',False)],0.14)
  149. bn.add('s_s',[('s_m',False),('m_f',False),('b_v',True )],0.132)
  150. bn.add('s_s',[('s_m',False),('m_f',False),('b_v',False)],0.44)
  151.  
  152. bn.add('s_t',[('d',True )],0.08)
  153. bn.add('s_t',[('d',False)],0.002)
  154. bn.add('s_q',[('s_p',True ),('v_p',True )],0.008)
  155. bn.add('s_q',[('s_p',True ),('v_p',False)],0.4)
  156. bn.add('s_q',[('s_p',False),('v_p',True )],0.51)
  157. bn.add('s_q',[('s_p',False),('v_p',False)],0.13)
  158. bn.add('f_s',[],0.1)
  159. bn.add('c_c',[('s_s',True )],0.49)
  160. bn.add('c_c',[('s_s',False)],0.023)
  161.  
  162. bn.add('car_s',[('c_c',True),('s_t',True),('s_q',True ),('f_s',True )],0.091)
  163. bn.add('car_s',[('c_c',True),('s_t',True),('s_q',True ),('f_s',False )],0.081)
  164. bn.add('car_s',[('c_c',True),('s_t',True),('s_q',False ),('f_s',True )],0.045)
  165. bn.add('car_s',[('c_c',True),('s_t',True),('s_q',False ),('f_s',False )],0.065)
  166. bn.add('car_s',[('c_c',True),('s_t',False),('s_q',True ),('f_s',True)],0.087)
  167. bn.add('car_s',[('c_c',True),('s_t',False),('s_q',True),('f_s',False )],0.043)
  168. bn.add('car_s',[('c_c',True),('s_t',False),('s_q',False ),('f_s',True)],0.035)
  169. bn.add('car_s',[('c_c',True),('s_t',False),('s_q',False),('f_s',False )],0.067)
  170. bn.add('car_s',[('c_c',False),('s_t',True),('s_q',True),('f_s',True)],0.052)
  171. bn.add('car_s',[('c_c',False),('s_t',True),('s_q',True),('f_s',False)],0.054)
  172. bn.add('car_s',[('c_c',False),('s_t',True),('s_q',False),('f_s',True)],0.056)
  173. bn.add('car_s',[('c_c',False),('s_t',True),('s_q',False),('f_s',False)],0.078)
  174. bn.add('car_s',[('c_c',False),('s_t',False),('s_q',True),('f_s',True )],0.045)
  175. bn.add('car_s',[('c_c',False),('s_t',False),('s_q',True),('f_s',False)],0.031)
  176. bn.add('car_s',[('c_c',False),('s_t',False),('s_q',False),('f_s',True )],0.034)
  177. bn.add('car_s',[('c_c',False),('s_t',False),('s_q',False),('f_s',False)],0.023)
  178.  
  179. print("-------------------------------------------")
  180. print("Cobertura de Markov para 's_t'")
  181. print(bn.markov_blanket('s_t'))
  182. print("-------------------------------------------")
  183. print("Cobertura de Markov para 'c_s'")
  184. print(bn.markov_blanket('c_s'))
  185. print("-------------------------------------------")
  186.  
  187.  
  188. # -------------------------------------------------------------
  189. # TWO + TWO = FOUR
  190. # ( teste da pesquisa com restricoes )
  191. # -------------------------------------------------------------
  192.  
  193.  
  194. digits = list(range(0,10))
  195.  
  196. domains = { D:digits for D in ['O','R','T','U','W'] }
  197. domains['F'] = [0,1]
  198. domains['X1'] = [0,1]
  199. domains['X2'] = [0,1]
  200.  
  201.  
  202. def all_different(Aux1):
  203. return len(set(Aux1)) == len(Aux1)
  204.  
  205. def orx1(Aux2):
  206. return 2*Aux2[0] == Aux2[1]+10*Aux2[2]
  207.  
  208. def wx1ux2(Aux3):
  209. return 2*Aux3[0]+Aux3[1] == Aux3[2]+10*Aux3[3]
  210.  
  211. def tx2of(Aux4):
  212. return 2*Aux4[0]+Aux4[1] == Aux4[2]+10*Aux4[3]
  213.  
  214. domains['FORTUW'] = generate_product_domain(['F','O','R','T','U','W'],domains)
  215. domains['FORTUW'] = filter_domain(domains['FORTUW'],all_different)
  216.  
  217. domains['ORX1'] = generate_product_domain(['O','R','X1'],domains)
  218. domains['ORX1'] = filter_domain(domains['ORX1'],orx1)
  219.  
  220. domains['WX1UX2'] = generate_product_domain(['W','X1','U','X2'],domains)
  221. domains['WX1UX2'] = filter_domain(domains['WX1UX2'],wx1ux2)
  222.  
  223. domains['TX2OF'] = generate_product_domain(['T','X2','O','F'],domains)
  224. domains['TX2OF'] = filter_domain(domains['TX2OF'],wx1ux2)
  225.  
  226.  
  227. constraints = []
  228.  
  229. constraints += [ (edge,lambda var,val,auxvar,auxval : val==auxval[0])
  230. for edge in [('F','FORTUW'),('O','ORX1'),('W','WX1UX2'),('T','TX2OF')] ]
  231. constraints += [ (edge,lambda auxvar,auxval,var,val : val==auxval[0])
  232. for edge in [('FORTUW','F'),('ORX1','O'),('WX1UX2','W'),('TX2OF','T')] ]
  233.  
  234. constraints += [ (edge,lambda var,val,auxvar,auxval : val==auxval[1])
  235. for edge in [('O','FORTUW'),('R','ORX1'),('X1','WX1UX2'),('X2','TX2OF')] ]
  236. constraints += [ (edge,lambda auxvar,auxval,var,val : val==auxval[1])
  237. for edge in [('FORTUW','O'),('ORX1','R'),('WX1UX2','X1'),('TX2OF','X2')] ]
  238.  
  239. constraints += [ (edge,lambda var,val,auxvar,auxval : val==auxval[2])
  240. for edge in [('R','FORTUW'),('X1','ORX1'),('U','WX1UX2'),('O','TX2OF')] ]
  241. constraints += [ (edge,lambda auxvar,auxval,var,val : val==auxval[2])
  242. for edge in [('FORTUW','R'),('ORX1','X1'),('WX1UX2','U'),('TX2OF','O')] ]
  243.  
  244. constraints += [ (edge,lambda var,val,auxvar,auxval : val==auxval[3])
  245. for edge in [('T','FORTUW'),('X2','WX1UX2'),('F','TX2OF')] ]
  246. constraints += [ (edge,lambda auxvar,auxval,var,val : val==auxval[3])
  247. for edge in [('FORTUW','T'),('WX1UX2','X2'),('TX2OF','F')] ]
  248.  
  249. constraints += [ (edge,lambda var,val,auxvar,auxval : val==auxval[4])
  250. for edge in [('U','FORTUW')] ]
  251. constraints += [ (edge,lambda auxvar,auxval,var,val : val==auxval[4])
  252. for edge in [('FORTUW','U')] ]
  253.  
  254. constraints += [ (edge,lambda var,val,auxvar,auxval : val==auxval[5])
  255. for edge in [('W','FORTUW')] ]
  256. constraints += [ (edge,lambda auxvar,auxval,var,val : val==auxval[5])
  257. for edge in [('FORTUW','W')] ]
  258.  
  259.  
  260. cs = MyCS(domains,dict(constraints))
  261.  
  262. print("-------------------------------------------")
  263. print("Procura de uma solução")
  264. print("-------------------------------------------")
  265. t0 = time.clock()
  266. sol = cs.search()
  267.  
  268. print("Solucao:",sol)
  269.  
  270. print("Tempo:",time.clock()-t0)
  271.  
  272.  
  273. print("-------------------------------------------")
  274. print("Procura de todas as soluções")
  275. print("-------------------------------------------")
  276. t0 = time.clock()
  277. lsols = cs.search_all()
  278.  
  279. print("Soluções:")
  280. for s in lsols:
  281. print(s)
  282. print("Tempo:",time.clock()-t0)
  283.  
  284. print(len(lsols)," soluções")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!