prolog

tsp1(Origem,Caminho,Custo):-criar_lista_cidades(Origem,L),branch_n_bound(Origem,L,LFinal),sort(LFinal,[(Custo,Caminho)|_]),!.

criar_lista_cidades(Orig,Lista):-findall(X,city(X,_,_),L1),eliminar(L1,Orig,Lista).

eliminar([],_,_):- !.
eliminar([E|T],E ,T).
eliminar([H|T],E,[H|Y]):- eliminar(T,E,Y).

branch_n_bound(_,[],[]):-!.
branch_n_bound(Orig,[H|T],[(DF,CF)|LFinal]):-branch_n_bound(Orig,T,LFinal),bnb(Orig,H,L1,C),append_retorno(Orig,C,L1,CF,DF).

bnb(Orig,Dest,Cam,Custo):-
    bnb2(Dest,[(0,[Orig])],Cam,Custo).
bnb2(Dest,[(Custo,[Dest|T])|T2],Cam,Custo):-
    calc_tam_caminho([Dest|T],Tam),
    (Tam==5,reverse([Dest|T],Cam),true);
    bnb2(Dest,T2,Cam,Custo).
bnb2(Dest,[(Ca,LA)|Outros],Cam,Custo):-
    LA=[Act|_],
    findall((CaX,[X|LA]),(Dest\==Act, dist_cities(Act,X,CustoX),\+ member(X,LA), CaX is CustoX + Ca),Novos),
    append(Outros,Novos,Todos),
    sort(Todos,TodosOrd),
    bnb2(Dest,TodosOrd,Cam,Custo).


append_retorno(Orig,C,[H|T],CamFinal,DistFinal):-dist_ultimo_origem(Orig,[H|T],D1),append([H|T],[Orig],CamFinal),DistFinal is D1 + C.

calc_tam_caminho((_,L),Tam):-calc_tam_caminho(L,Tam).
calc_tam_caminho([],0):-!.
calc_tam_caminho([_|T],Tam):-calc_tam_caminho(T,Tam1), Tam is Tam1 + 1.

dist_ultimo_origem(Orig,[X],Dist):-dist_cities(X,Orig,Dist).
dist_ultimo_origem(Orig,[_|T],Dist):-dist_ultimo_origem(Orig,T,Dist).