API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 13th, 2018
98
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.77 KB | None | 0 0
raw download clone embed print report
  1. :-reconsult('bc_tp2').
  2.  
  3. %=====================
  4.  
  5. %Iteracao 1:
  6.  
  7. tsp1(Cidade,Caminho):-
  8. findall((Caminho1, Distancia), (todosCaminhos(Cidade, Caminho1), Caminho1=[H|T], calculaDistancia(H,T,Distancia)), NovosCaminhos),
  9. sort(2, @>, NovosCaminhos, NovosCaminhosSorted),
  10. last(NovosCaminhosSorted,Caminho),!.
  11.  
  12. todosCaminhos(Cidade, Caminho):-
  13. dfs(Cidade, [Cidade], Caminho1),
  14. append(Caminho1, [Cidade], Caminho).
  15.  
  16. dfs(_, ListaAux, Caminho):-
  17. total(ListaAux, T1),
  18. contarCidades(T2),
  19. T1 =:= T2,
  20. reverse(ListaAux, Caminho).
  21.  
  22. dfs(Cidade, ListaAux, Caminho):-
  23. city(C , _, _),
  24. \+ member(C , ListaAux),
  25. C \== Cidade,
  26. dfs(C, [C|ListaAux], Caminho).
  27.  
  28. total([],0).
  29. total([_|T], N):-
  30. total(T, N1),
  31. N is N1 + 1.
  32.  
  33. contarCidades(Total):-
  34. findall(Prox_Cid, city(Prox_Cid , _, _), ListaTotal), total(ListaTotal, Total).
  35.  
  36.  
  37. calculaDistancia(Cidade1,[Cidade2], Distancia):-
  38. dist_cities(Cidade1, Cidade2, Distancia).
  39. calculaDistancia(Cidade1,T, Distancia):-
  40. T = [Cidade2|T2],
  41. dist_cities(Cidade1, Cidade2, Dist_Cidade),
  42. calculaDistancia(Cidade2, T2, Distancia1),
  43. Distancia is Dist_Cidade + Distancia1.
  44.  
  45. %2) Foi conseguido um total máximo de 10 cidades.
  46.  
  47. %================================================
  48.  
  49. %Iteracao 2:
  50.  
  51. tsp2(Cidade, Caminho, Distancia):-
  52. tsp(Cidade, [Cidade], Caminho, Cidade, Distancia), !.
  53.  
  54. tsp(Cidade, CidadesVisitadas, Caminho, CidadeInicial, Distancia):-
  55. total(CidadesVisitadas, N1),
  56. contarCidades(N2),
  57. N1 =:= N2,
  58. CidadesVisitadas2 = [CidadeInicial|CidadesVisitadas],
  59. dist_cities(CidadeInicial, Cidade, Dist_Cidade),
  60. Distancia is Dist_Cidade,
  61. reverse(CidadesVisitadas2, Caminho).
  62.  
  63. tsp(Cidade, CidadesVisitadas, Caminho, CidadeInicial, Distancia):-
  64. findall((Dist_Cidade, Prox_Cidade), (dist_cities(Prox_Cidade, Cidade, Dist_Cidade), (\+ member(Prox_Cidade, CidadesVisitadas))), NovasCidades),
  65. sort(NovasCidades, NovasCidadesSorted),
  66. NovasCidadesSorted = [(DistanciaMelhor,Melhor)|_],
  67. CidadesVisitadas2 =[Melhor|CidadesVisitadas],
  68. tsp(Melhor, CidadesVisitadas2, Caminho, CidadeInicial, Distancia2),
  69. Distancia is Distancia2 + DistanciaMelhor.
  70.  
  71. %=============================================================
  72.  
  73. %Iteracao 3:
  74.  
  75. tsp3(Cidade, Caminho, Distancia):-
  76. tsp2(Cidade, Caminho2, _),
  77. lista(Caminho2, NovaLista),
  78. eliminarCruzamentos(Cidade, NovaLista, NovaLista, ListaDesorganizada),
  79. reorganizacao(ListaDesorganizada, Caminho),
  80. Caminho = [CaminhoHead|CaminhoTail],
  81. calculaDistancia(CaminhoHead, CaminhoTail, Distancia),!.
  82.  
  83. lista([H|T], Lista):-
  84. total([H|T], N1),
  85. N1 =:= 2,
  86. T=[H2|_],
  87. Lista = [[H, H2]].
  88. lista([H|T], Lista):-
  89. lista(T, Resultado),
  90. T=[H2|_],
  91. Lista = [[H, H2]| Resultado].
  92.  
  93. eliminarCruzamentos(_,[], H, H).
  94. eliminarCruzamentos(Cidade, [[Cid1,Cid2]|Res], ListaOriginal, ListaDesorganizada):-
  95. findall([Cid3, Cid4], (member([Cid3, Cid4], Res), Cid1\=Cid3, Cid1\=Cid4, Cid2\=Cid3, Cid2\=Cid4,
  96. cruzamento(Cid1,Cid2,Cid3,Cid4)), [[H,T]|_]),
  97. eliminarCruz([Cid1, Cid2], [H, T], ListaOriginal, ListaDesorganizada1),
  98. rGraph(Cidade, ListaDesorganizada1, Caminho),
  99. eliminarCruzamentos(Cidade, Caminho, Caminho, ListaDesorganizada),!.
  100.  
  101. eliminarCruzamentos(Cidade, [_|Lista], ListaOriginal, ListaDesorganizada):-
  102. eliminarCruzamentos(Cidade, Lista, ListaOriginal, ListaDesorganizada).
  103.  
  104. eliminarCruz([Cid1,Cid2], [Cid3,Cid4], ListaOriginal, ListaDesorganizada):-
  105. select([Cid1, Cid2], ListaOriginal, ListaOriginal1),
  106. select([Cid3, Cid4], ListaOriginal1, ListaOriginal2),
  107. append(ListaOriginal2, [[Cid1,Cid3]], ListaOriginal3),
  108. append(ListaOriginal3, [[Cid2,Cid4]], ListaDesorganizada).
  109.  
  110. cruzamento(Cid1, Cid2, Cid3, Cid4):-
  111. city(Cid1, Lat1, Long1),
  112. city(Cid2, Lat2, Long2),
  113. city(Cid3, Lat3, Long3),
  114. city(Cid4, Lat4, Long4),
  115. doIntersect((Lat1, Long1),(Lat2, Long2),(Lat3, Long3),(Lat4, Long4)).
  116.  
  117. reorganizacao([H], H):-!.
  118. reorganizacao([H|T], Caminho):-
  119. H = [Cidade|_],
  120. reorganizacao(T, Caminho2),
  121. Caminho = [Cidade|Caminho2].
  122.  
  123. %===========================================================
  124.  
  125. %Iteracao 4:
  126.  
  127. %=== Parameterizacao ===%
  128.  
  129. geracoes(5).
  130. populacao(1).
  131. prob_cruzamento(0.8).
  132. prob_mutacao(0.1).
  133. %== Tem de ser sempre menos uma que o valor de cidades real ==%
  134. cidades(49).
  135.  
  136. %=== Metodo inicial, chama todas as partes do algoritmo ===%
  137. tsp4(CidadeOrigem):-
  138. gera_populacao(Pop,CidadeOrigem),
  139. avalia_populacao(Pop,PopAvaliada),
  140. ordena_populacao(PopAvaliada,PopOrdenada),
  141. geracoes(NGeracoes),
  142. gera_geracao(NGeracoes,PopOrdenada),!.
  143.  
  144. %=== Metodo para gerar a populacao ===%
  145. gera_populacao(Pop,Cidade):-
  146. populacao(TamPop),
  147. cidades(NumCidades),
  148. findall(Prox_Cidade, city(Prox_Cidade, _, _), ListaCidades),
  149. delete(ListaCidades,Cidade,NListaCidades),
  150. gera_populacao(TamPop,NListaCidades,NumCidades,Pop,Cidade),nl.
  151.  
  152. gera_populacao(0,_,_,[],_):-!.
  153.  
  154. gera_populacao(TamPop,ListaCidades,NumCidades,[LR|Resto],Cidade):-
  155. TamPop1 is TamPop-1,
  156. gera_populacao(TamPop1,ListaCidades,NumCidades,Resto,Cidade),
  157. gera_individuo(ListaCidades,NumCidades,Ind),
  158. adicionarPrimeiraeUltima(Ind,LR,Cidade,Cidade),
  159. not(member(LR,Resto)).
  160.  
  161. gera_populacao(TamPop,ListaCidades,NumCidades,L,Cidade):-
  162. gera_populacao(TamPop,ListaCidades,NumCidades,L,Cidade).
  163.  
  164. %=== Metodo para gerar o individuo ===%
  165. gera_individuo([G],1,[G]):-!.
  166.  
  167. gera_individuo(ListaCidades,NumCidades,[G|Resto]):-
  168. NumTemp is NumCidades + 1, % To use with random
  169. random(1,NumTemp,N),
  170. retira(N,ListaCidades,G,NovaLista),
  171. NumCidades1 is NumCidades-1,
  172. gera_individuo(NovaLista,NumCidades1,Resto).
  173.  
  174. retira(1,[G|Resto],G,Resto).
  175.  
  176. retira(N,[G1|Resto],G,[G1|Resto1]):-
  177. N1 is N-1,
  178. retira(N1,Resto,G,Resto1).
  179.  
  180. %== Metodo ara avaliar a populacao ===%
  181. avalia_populacao([],[]).
  182.  
  183. avalia_populacao([Ind|Resto],[Ind*V|Resto1]):-
  184. avalia(Ind,V),
  185. avalia_populacao(Resto,Resto1).
  186.  
  187. avalia(Seq,V):-
  188. avalia_(Seq,V).
  189.  
  190. avalia_([],0).
  191.  
  192. avalia_([Atual|[Prox|Resto]],V):-
  193. avalia([Prox|Resto],V1),
  194. dist_cities(Atual,Prox,DistAtual),
  195. V is DistAtual+V1.
  196.  
  197. avalia_([Atual|[Prox]],V):-
  198. avalia([],V1),
  199. dist_cities(Atual,Prox,DistAtual),
  200. V is DistAtual+V1.
  201.  
  202. %=== Metodo para ordenar a populacao ===%
  203. ordena_populacao(PopAv,PopAvOrd):-
  204. bsort(PopAv,PopAvOrd).
  205.  
  206. bsort([X],[X]):-!.
  207.  
  208. bsort([X|Xs],Ys):-
  209. bsort(Xs,Zs),
  210. btroca([X|Zs],Ys).
  211.  
  212. btroca([X],[X]):-!.
  213.  
  214. btroca([X*VX,Y*VY|L1],[Y*VY|L2]):-
  215. VX>VY,!,
  216. btroca([X*VX|L1],L2).
  217.  
  218. btroca([X|L1],[X|L2]):-
  219. btroca(L1,L2).
  220.  
  221. %=== Metodo para gerar a proxima geracao ===%
  222. gera_geracao(0,Pop):-!,
  223. write('%=== GERACAO '), write(0), write(' ===%'), nl, write(Pop), nl.
  224.  
  225. gera_geracao(G,Pop):-
  226. %=== Geracao seguinte ===%
  227. write('%=== GERACAO '), write(G), write(' ===%'), nl, write(Pop), nl,
  228. removerPrimeiroeUltimo_pop(Pop,PopSemPriEUlt,Inicio,Fim),
  229. cruzamento(PopSemPriEUlt,NPopSemPriEUlt),
  230. mutacao(NPopSemPriEUlt,NPop1),
  231. adicionarPrimeiroeUltimoPop(NPop1,NPop,Inicio,Fim),
  232. avalia_populacao(NPop,NPopAv),
  233. ordena_populacao(NPopAv,NPopOrd),
  234. G1 is G-1,
  235. gera_geracao(G1,NPopOrd).
  236.  
  237. removerPrimeiroeUltimo_pop([],[],[],[]).
  238.  
  239. removerPrimeiroeUltimo_pop([H*Val|T],[LR*Val|PopSem],[Inicio1|Inicio],[Fim1|Fim]):-
  240. removerPrimeiroeUltimo_pop(T,PopSem,Inicio,Fim),
  241. removerPrimeiroeUltimo(H,LR,Inicio1,Fim1).
  242.  
  243. removerPrimeiroeUltimo([Inicio|T],LR,Inicio,Fim):-
  244. removerPrimeiroeUltimo_(T,LR,Fim).
  245.  
  246. removerPrimeiroeUltimo_([Fim],[],Fim).
  247.  
  248. removerPrimeiroeUltimo_([H|T],[H|LR],Fim):-
  249. removerPrimeiroeUltimo_(T,LR,Fim).
  250.  
  251. adicionarPrimeiroeUltimoPop([],[],[],[]).
  252.  
  253. adicionarPrimeiroeUltimoPop([H|T],[LR|PopCom],[H_inicio|T_inicio],[H_fim|T_fim]):-
  254. adicionarPrimeiroeUltimoPop(T,PopCom,T_inicio,T_fim),
  255. adicionarPrimeiraeUltima(H,LR,H_inicio,H_fim).
  256.  
  257. adicionarPrimeiraeUltima(L,[E1|LR],E1,E2):-
  258. adicionarPrimeiraeUltima_(L,E2,LR).
  259.  
  260. adicionarPrimeiraeUltima_([],E2,[E2]).
  261.  
  262. adicionarPrimeiraeUltima_([H|T],E2,[H|LR]):-
  263. adicionarPrimeiraeUltima_(T,E2,LR).
  264.  
  265. gerar_pontos_cruzamento(P1,P2):-
  266. gerar_pontos_cruzamento1(P1,P2).
  267.  
  268. gerar_pontos_cruzamento1(P1,P2):-
  269. cidades(N),
  270. NTemp is N + 1,
  271. random(1,NTemp,P11),
  272. random(1,NTemp,P21),
  273. P11\==P21,!,
  274. ((P11<P21,!,P1=P11,P2=P21);P1=P21,P2=P11).
  275.  
  276. gerar_pontos_cruzamento1(P1,P2):-
  277. gerar_pontos_cruzamento1(P1,P2).
  278.  
  279. cruzamento([],[]).
  280.  
  281. cruzamento([Ind*_],[Ind]).
  282.  
  283. cruzamento([Ind1*_,Ind2*_|Resto],[NInd1,NInd2|Resto1]):-
  284. gerar_pontos_cruzamento(P1,P2),
  285. prob_cruzamento(Pcruz), random(0.0,1.0,Pc),
  286. ((Pc =< Pcruz,!,
  287. cruzar(Ind1,Ind2,P1,P2,NInd1),
  288. cruzar(Ind2,Ind1,P1,P2,NInd2))
  289. ;
  290. (NInd1=Ind1,NInd2=Ind2)),
  291. cruzamento(Resto,Resto1).
  292.  
  293. preencheh([],[]).
  294.  
  295. preencheh([_|R1],[h|R2]):-
  296. preencheh(R1,R2).
  297.  
  298. sublista(L1,I1,I2,L):-
  299. I1 < I2,!,
  300. sublista1(L1,I1,I2,L).
  301.  
  302. sublista(L1,I1,I2,L):-
  303. sublista1(L1,I2,I1,L).
  304.  
  305. sublista1([X|R1],1,1,[X|H]):-!,
  306. preencheh(R1,H).
  307.  
  308. sublista1([X|R1],1,N2,[X|R2]):-!,
  309. N3 is N2 - 1,
  310. sublista1(R1,1,N3,R2).
  311.  
  312. sublista1([_|R1],N1,N2,[h|R2]):-
  313. N3 is N1 - 1,
  314. N4 is N2 - 1,
  315. sublista1(R1,N3,N4,R2).
  316.  
  317. rotate_right(L,K,L1):-
  318. cidades(N),
  319. T is N - K,
  320. rr(T,L,L1).
  321.  
  322. rr(0,L,L):-!.
  323.  
  324. rr(N,[X|R],R2):-
  325. N1 is N - 1,
  326. append(R,[X],R1),
  327. rr(N1,R1,R2).
  328.  
  329. elimina([],_,[]):-!.
  330.  
  331. elimina([X|R1],L,[X|R2]):-
  332. not(member(X,L)),!,
  333. elimina(R1,L,R2).
  334.  
  335. elimina([_|R1],L,R2):-
  336. elimina(R1,L,R2).
  337.  
  338. insere([],L,_,L):-!.
  339. insere([X|R],L,N,L2):-
  340. cidades(T),
  341. ((N>T,!,N1 is N mod T);N1 = N),
  342. insere1(X,N1,L,L1),
  343. N2 is N + 1,
  344. insere(R,L1,N2,L2).
  345.  
  346. insere1(X,1,L,[X|L]):-!.
  347. insere1(X,N,[Y|L],[Y|L1]):-
  348. N1 is N-1,
  349. insere1(X,N1,L,L1).
  350.  
  351. cruzar(Ind1,Ind2,P1,P2,NInd11):-
  352. sublista(Ind1,P1,P2,Sub1),
  353. cidades(NumT),
  354. R is NumT-P2,
  355. rotate_right(Ind2,R,Ind21),
  356. elimina(Ind21,Sub1,Sub2),
  357. P3 is P2 + 1,
  358. insere(Sub2,Sub1,P3,NInd1),
  359. eliminah(NInd1,NInd11).
  360.  
  361. eliminah([],[]).
  362.  
  363. eliminah([h|R1],R2):-!,
  364. eliminah(R1,R2).
  365.  
  366. eliminah([X|R1],[X|R2]):-
  367. eliminah(R1,R2).
  368.  
  369. mutacao([],[]).
  370. mutacao([Ind|Rest],[NInd|Rest1]):-
  371. prob_mutacao(Pmut),
  372. random(0.0,1.0,Pm),
  373. ((Pm < Pmut,!,mutacao1(Ind,NInd));NInd = Ind),
  374. mutacao(Rest,Rest1).
  375.  
  376. mutacao1(Ind,NInd):-
  377. gerar_pontos_cruzamento(P1,P2),
  378. mutacao22(Ind,P1,P2,NInd).
  379.  
  380. mutacao22([G1|Ind],1,P2,[G2|NInd]):-
  381. !, P21 is P2-1,
  382. mutacao23(G1,P21,Ind,G2,NInd).
  383. mutacao22([G|Ind],P1,P2,[G|NInd]):-
  384. P11 is P1-1, P21 is P2-1,
  385. mutacao22(Ind,P11,P21,NInd).
  386.  
  387. mutacao23(G1,1,[G2|Ind],G2,[G1|Ind]):-!.
  388. mutacao23(G1,P,[G|Ind],G2,[G|NInd]):-
  389. P1 is P-1,
  390. mutacao23(G1,P1,Ind,G2,NInd).
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!