Permutations - Stuck in a infinite loop

tripsytina · December 2, 2022, 6:01pm

I have done an algorithm wich gets the most time-efficent list from the permutated lists of a certain list.
When i try to run it for a small list (with 2 elements) it works, however, when i try with a bigger list, it get stuck after trying with a small portion of the permutated lists.
I tried tracing the algorithm to see what was wrong and after doing the first list it got stuck on a infinite loop, does somebody know what i am doing wrong?

My code:

%a armazensEntregas
armazens_entregas(L):- findall(K,entrega(_,_,_,K,_,_),L).

%b addMatosinhos
add_matosinhos(L,LB):-append([5],L,LA),append(LA,[5],LB).


:-dynamic custo_min/2.

%c calcula_tempo
calcula_tempo(LC,Final):-
        bateria_camiao(LC,CarM,TempR),
        peso_camiao(3,PesoC),
        tempo_recarga(LC,CarM,TempR,RecargaC,PesoC),
        tempo_extra(LC,ExtraC),
        tempo_entregas(LC,TempoE),
        tempo(LC,Custo,PesoC),
        somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final).


%custo
tempo([_],0,_).
tempo([C1,C2|LC],Custo,PesoC):-
    entregas_peso(C1,LE),
    peso_entregas(LE,PesoE),
    PesoC1 is PesoC - PesoE,
    tempo([C2|LC],Custo1,PesoC1),
    (dadosCam_t_e_ta(_,C1,C2,Tempo,_,_)
    ;dadosCam_t_e_ta(_,C2,C1,Tempo,_,_)),
    peso_camiao(C1,PesoB),
    Tempo1 is (PesoC1*Tempo)/PesoB,
    Custo is Custo1+Tempo1.

%d bateria_camiao (assumindo que o máximo de carga em % é 80%)
bateria_camiao([HC1|_],CarM1,TempR):- dadosCam_t_e_ta(Nome,HC1,_,_,_,_),carateristicasCam(Nome,_,_,CarM,_,TempR),CarM1 is CarM*(0.8).

%e peso do camiao (assumindo que possui carga máxima)
peso_camiao(C1,PesoC):- dadosCam_t_e_ta(Nome,C1,_,_,_,_),carateristicasCam(Nome,Tara,CapC,_,_,_), PesoC is Tara + CapC.

%e tempo_extra
tempo_extra([_],0).
tempo_extra([C1,C2|LC],ExtraC):-
        tempo_extra([C2|LC],ExtraC1),
        (dadosCam_t_e_ta(_,C1,C2,_,_,Extra);dadosCam_t_e_ta(_,C2,C1,_,_,Extra)),
        ExtraC is ExtraC1 + Extra.

%f tempo_recarga
tempo_recarga([_],_,_,0,_).
tempo_recarga([C1,C2|LC],CarM,TempR,RecargaC,PesoC):-
        entregas_peso(C1,LE),
        peso_entregas(LE,PesoE),
        PesoC1 is PesoC - PesoE,
        tempo_recarga([C2|LC],CarM,TempR,RecargaC1,PesoC1),
        (dadosCam_t_e_ta(_,C1,C2,_,Energia,_);
        dadosCam_t_e_ta(_,C2,C1,_,Energia,_)),
        peso_camiao(C1,PesoB),
        Energia1 is (PesoC1*Energia)/PesoB,
        ((CarM - Energia1 < 20, RecargaC is RecargaC1 + ((80 - (CarM - Energia1))*TempR)/60);RecargaC is RecargaC1 + 0).


%g entregas_peso
entregas_peso(C1,LE):- findall(M,entrega(_,_,M,C1,_,_),LE).

%g tempo_entregas
tempo_entregas([],0).
tempo_entregas([HC|LC],TempoE):-
        tempo_entregas(LC,TempoE1),
        buscar_entregas(HC,LI),
        entregas_tempo(LI,TempoT),
        TempoE is TempoE1 + TempoT.

%k buscar_entregas
buscar_entregas(HC,LI):-findall(Id,entrega(Id,_,_,HC,_,_),LI).

%j entregas_tempo
entregas_tempo([],0).
entregas_tempo([HI|LI],TempoT):-
        entregas_tempo(LI,TempoT1),
        entrega(HI,_,_,_,T,TS),
        TempoT is TempoT1 + (T + TS).

%h peso_entregas
peso_entregas([],0).
peso_entregas([HC1|LC1],PesoE):-
        peso_entregas(LC1,PesoE1), PesoE is PesoE1 + HC1.

%i somar_tudo
somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final):- Final is (RecargaC + ExtraC + TempoE + Custo).

%d seq_custo_min

seq_custo_min(LC,Final):-(run;true),custo_min(LC,Final).

run:-
    retractall(custo_min(_,_)),
    assertz(custo_min(_,100000)),
    armazens_entregas(LC),
    permutation(LC,LCPerm),
    add_matosinhos(LCPerm,LCPerm1),
    calcula_tempo(LCPerm1,Final),
    atualiza(LCPerm1,Final),
    fail.

atualiza(LCPerm1,Final):-
  custo_min(_,FinalMin),
  ((Final<FinalMin,!,retract(custo_min(_,_)),assertz(custo_min(LCPerm1,Final)),
    write(Final),nl)
    ;true).

kuniaki.mukai · December 3, 2022, 7:47am

Is your problem related to this description ?

For a give list L, calculate max of the set { f(p) | p is a permutation of L }
where f is a certain numeric function on permutation of L.

It was hard for me to guess from your codes without hint for the problem description.

tripsytina · December 3, 2022, 12:20pm

After looking again , i realised that in some of the methods i was seaching for a value incorrectly.
This corrected some of the problem as now a i can use a bigger list and obtain a result.
However for 6 elements it gets stuck.
I send here the data i use for running and also the updated code.
Anything you want me to clarify, tell me.

%idArmazem(<local>,<codigo>)
idArmazem('Arouca',1).
idArmazem('Espinho',2).
idArmazem('Gondomar',3).
idArmazem('Maia',4).
idArmazem('Matosinhos',5).
idArmazem('Oliveira de Azemeis',6).
idArmazem('Paredes',7).
idArmazem('Porto',8).
idArmazem('Povoa de Varzim',9).
idArmazem('Santa Maria da Feira',10).
idArmazem('Santo Tirso',11).
idArmazem('Sao Joao da Madeira',12).
idArmazem('Trofa',13).
idArmazem('Vale de Cambra',14).
idArmazem('Valongo',15).
idArmazem('Vila do Conde',16).
idArmazem('Vila Nova de Gaia',17).


%carateristicasCam(<nome_camiao>,<tara>,<capacidade_carga>,<carga_total_baterias>,<autonomia>,<t_recarr_bat_20a80>).
carateristicasCam(eTruck01,7500,4300,80,100,60).

%dadosCam_t_e_ta(<nome_camiao>,<cidade_origem>,<cidade_destino>,<tempo>,<energia>,<tempo_adicional>).
dadosCam_t_e_ta(eTruck01,1,2,122,42,0).
dadosCam_t_e_ta(eTruck01,1,3,122,46,0).
dadosCam_t_e_ta(eTruck01,1,4,151,54,25).
dadosCam_t_e_ta(eTruck01,1,5,147,52,25).
dadosCam_t_e_ta(eTruck01,1,6,74,24,0).
dadosCam_t_e_ta(eTruck01,1,7,116,35,0).
dadosCam_t_e_ta(eTruck01,1,8,141,46,0).
dadosCam_t_e_ta(eTruck01,1,9,185,74,53).
dadosCam_t_e_ta(eTruck01,1,10,97,30,0).
dadosCam_t_e_ta(eTruck01,1,11,164,64,40).
dadosCam_t_e_ta(eTruck01,1,12,76,23,0).
dadosCam_t_e_ta(eTruck01,1,13,174,66,45).
dadosCam_t_e_ta(eTruck01,1,14,59,18,0).
dadosCam_t_e_ta(eTruck01,1,15,132,51,24).
dadosCam_t_e_ta(eTruck01,1,16,181,68,45).
dadosCam_t_e_ta(eTruck01,1,17,128,45,0).

dadosCam_t_e_ta(eTruck01,2,1,116,42,0).
dadosCam_t_e_ta(eTruck01,2,3,55,22,0).
dadosCam_t_e_ta(eTruck01,2,4,74,25,0).
dadosCam_t_e_ta(eTruck01,2,5,65,22,0).
dadosCam_t_e_ta(eTruck01,2,6,69,27,0).
dadosCam_t_e_ta(eTruck01,2,7,74,38,0).
dadosCam_t_e_ta(eTruck01,2,8,61,18,0).
dadosCam_t_e_ta(eTruck01,2,9,103,44,0).
dadosCam_t_e_ta(eTruck01,2,10,36,14,0).
dadosCam_t_e_ta(eTruck01,2,11,88,41,0).
dadosCam_t_e_ta(eTruck01,2,12,61,19,0).
dadosCam_t_e_ta(eTruck01,2,13,95,42,0).
dadosCam_t_e_ta(eTruck01,2,14,78,34,0).
dadosCam_t_e_ta(eTruck01,2,15,69,30,0).
dadosCam_t_e_ta(eTruck01,2,16,99,38,0).
dadosCam_t_e_ta(eTruck01,2,17,46,14,0).

dadosCam_t_e_ta(eTruck01,3,1,120,45,0).
dadosCam_t_e_ta(eTruck01,3,2,50,22,0).
dadosCam_t_e_ta(eTruck01,3,4,46,15,0).
dadosCam_t_e_ta(eTruck01,3,5,46,14,0).
dadosCam_t_e_ta(eTruck01,3,6,74,37,0).
dadosCam_t_e_ta(eTruck01,3,7,63,23,0).
dadosCam_t_e_ta(eTruck01,3,8,38,8,0).
dadosCam_t_e_ta(eTruck01,3,9,84,36,0).
dadosCam_t_e_ta(eTruck01,3,10,59,28,0).
dadosCam_t_e_ta(eTruck01,3,11,61,27,0).
dadosCam_t_e_ta(eTruck01,3,12,67,32,0).
dadosCam_t_e_ta(eTruck01,3,13,67,29,0).
dadosCam_t_e_ta(eTruck01,3,14,82,38,0).
dadosCam_t_e_ta(eTruck01,3,15,34,8,0).
dadosCam_t_e_ta(eTruck01,3,16,80,30,0).
dadosCam_t_e_ta(eTruck01,3,17,36,10,0).

dadosCam_t_e_ta(eTruck01,4,1,149,54,25).
dadosCam_t_e_ta(eTruck01,4,2,65,24,0).
dadosCam_t_e_ta(eTruck01,4,3,46,16,0).
dadosCam_t_e_ta(eTruck01,4,5,27,10,0).
dadosCam_t_e_ta(eTruck01,4,6,103,47,0).
dadosCam_t_e_ta(eTruck01,4,7,55,27,0).
dadosCam_t_e_ta(eTruck01,4,8,36,10,0).
dadosCam_t_e_ta(eTruck01,4,9,50,26,0).
dadosCam_t_e_ta(eTruck01,4,10,78,34,0).
dadosCam_t_e_ta(eTruck01,4,11,42,19,0).
dadosCam_t_e_ta(eTruck01,4,12,97,42,0).
dadosCam_t_e_ta(eTruck01,4,13,44,11,0).
dadosCam_t_e_ta(eTruck01,4,14,111,48,0).
dadosCam_t_e_ta(eTruck01,4,15,32,13,0).
dadosCam_t_e_ta(eTruck01,4,16,53,14,0).
dadosCam_t_e_ta(eTruck01,4,17,38,11,0).

dadosCam_t_e_ta(eTruck01,5,1,141,51,24).
dadosCam_t_e_ta(eTruck01,5,2,55,20,0).
dadosCam_t_e_ta(eTruck01,5,3,48,14,0).
dadosCam_t_e_ta(eTruck01,5,4,25,9,0).
dadosCam_t_e_ta(eTruck01,5,6,97,44,0).
dadosCam_t_e_ta(eTruck01,5,7,55,28,0).
dadosCam_t_e_ta(eTruck01,5,8,29,7,0).
dadosCam_t_e_ta(eTruck01,5,9,48,24,0).
dadosCam_t_e_ta(eTruck01,5,10,69,30,0).
dadosCam_t_e_ta(eTruck01,5,11,53,26,0).
dadosCam_t_e_ta(eTruck01,5,12,95,36,0).
dadosCam_t_e_ta(eTruck01,5,13,63,20,0).
dadosCam_t_e_ta(eTruck01,5,14,105,45,0).
dadosCam_t_e_ta(eTruck01,5,15,34,14,0).
dadosCam_t_e_ta(eTruck01,5,16,46,18,0).
dadosCam_t_e_ta(eTruck01,5,17,27,7,0).

dadosCam_t_e_ta(eTruck01,6,1,69,23,0).
dadosCam_t_e_ta(eTruck01,6,2,71,27,0).
dadosCam_t_e_ta(eTruck01,6,3,74,38,0).
dadosCam_t_e_ta(eTruck01,6,4,103,46,0).
dadosCam_t_e_ta(eTruck01,6,5,99,44,0).
dadosCam_t_e_ta(eTruck01,6,7,88,48,0).
dadosCam_t_e_ta(eTruck01,6,8,92,38,0).
dadosCam_t_e_ta(eTruck01,6,9,134,66,45).
dadosCam_t_e_ta(eTruck01,6,10,42,14,0).
dadosCam_t_e_ta(eTruck01,6,11,116,56,30).
dadosCam_t_e_ta(eTruck01,6,12,23,9,0).
dadosCam_t_e_ta(eTruck01,6,13,126,58,33).
dadosCam_t_e_ta(eTruck01,6,14,25,9,0).
dadosCam_t_e_ta(eTruck01,6,15,84,44,0).
dadosCam_t_e_ta(eTruck01,6,16,132,60,35).
dadosCam_t_e_ta(eTruck01,6,17,80,38,0).

dadosCam_t_e_ta(eTruck01,7,1,116,36,0).
dadosCam_t_e_ta(eTruck01,7,2,71,38,0).
dadosCam_t_e_ta(eTruck01,7,3,61,22,0).
dadosCam_t_e_ta(eTruck01,7,4,53,26,0).
dadosCam_t_e_ta(eTruck01,7,5,53,28,0).
dadosCam_t_e_ta(eTruck01,7,6,88,48,0).
dadosCam_t_e_ta(eTruck01,7,8,59,26,0).
dadosCam_t_e_ta(eTruck01,7,9,88,48,0).
dadosCam_t_e_ta(eTruck01,7,10,84,44,0).
dadosCam_t_e_ta(eTruck01,7,11,74,22,0).
dadosCam_t_e_ta(eTruck01,7,12,82,42,0).
dadosCam_t_e_ta(eTruck01,7,13,76,31,0).
dadosCam_t_e_ta(eTruck01,7,14,97,49,21).
dadosCam_t_e_ta(eTruck01,7,15,29,16,0).
dadosCam_t_e_ta(eTruck01,7,16,84,42,0).
dadosCam_t_e_ta(eTruck01,7,17,69,30,0).

dadosCam_t_e_ta(eTruck01,8,1,134,46,0).
dadosCam_t_e_ta(eTruck01,8,2,59,18,0).
dadosCam_t_e_ta(eTruck01,8,3,32,6,0).
dadosCam_t_e_ta(eTruck01,8,4,34,10,0).
dadosCam_t_e_ta(eTruck01,8,5,32,7,0).
dadosCam_t_e_ta(eTruck01,8,6,88,38,0).
dadosCam_t_e_ta(eTruck01,8,7,57,26,0).
dadosCam_t_e_ta(eTruck01,8,9,69,30,0).
dadosCam_t_e_ta(eTruck01,8,10,65,26,0).
dadosCam_t_e_ta(eTruck01,8,11,53,22,0).
dadosCam_t_e_ta(eTruck01,8,12,82,34,0).
dadosCam_t_e_ta(eTruck01,8,13,61,24,0).
dadosCam_t_e_ta(eTruck01,8,14,97,40,0).
dadosCam_t_e_ta(eTruck01,8,15,36,12,0).
dadosCam_t_e_ta(eTruck01,8,16,65,23,0).
dadosCam_t_e_ta(eTruck01,8,17,32,6,0).

dadosCam_t_e_ta(eTruck01,9,1,181,72,50).
dadosCam_t_e_ta(eTruck01,9,2,95,41,0).
dadosCam_t_e_ta(eTruck01,9,3,86,35,0).
dadosCam_t_e_ta(eTruck01,9,4,55,24,0).
dadosCam_t_e_ta(eTruck01,9,5,48,23,0).
dadosCam_t_e_ta(eTruck01,9,6,134,65,42).
dadosCam_t_e_ta(eTruck01,9,7,95,47,0).
dadosCam_t_e_ta(eTruck01,9,8,69,28,0).
dadosCam_t_e_ta(eTruck01,9,10,109,51,24).
dadosCam_t_e_ta(eTruck01,9,11,61,29,0).
dadosCam_t_e_ta(eTruck01,9,12,132,57,31).
dadosCam_t_e_ta(eTruck01,9,13,67,19,0).
dadosCam_t_e_ta(eTruck01,9,14,143,66,45).
dadosCam_t_e_ta(eTruck01,9,15,71,34,0).
dadosCam_t_e_ta(eTruck01,9,16,15,3,0).
dadosCam_t_e_ta(eTruck01,9,17,67,28,0).

dadosCam_t_e_ta(eTruck01,10,1,97,30,0).
dadosCam_t_e_ta(eTruck01,10,2,34,14,0).
dadosCam_t_e_ta(eTruck01,10,3,59,27,0).
dadosCam_t_e_ta(eTruck01,10,4,78,33,0).
dadosCam_t_e_ta(eTruck01,10,5,71,30,0).
dadosCam_t_e_ta(eTruck01,10,6,40,14,0).
dadosCam_t_e_ta(eTruck01,10,7,82,42,0).
dadosCam_t_e_ta(eTruck01,10,8,65,24,0).
dadosCam_t_e_ta(eTruck01,10,9,109,52,25).
dadosCam_t_e_ta(eTruck01,10,11,92,46,0).
dadosCam_t_e_ta(eTruck01,10,12,32,6,0).
dadosCam_t_e_ta(eTruck01,10,13,99,46,0).
dadosCam_t_e_ta(eTruck01,10,14,63,17,0).
dadosCam_t_e_ta(eTruck01,10,15,74,34,0).
dadosCam_t_e_ta(eTruck01,10,16,105,46,0).
dadosCam_t_e_ta(eTruck01,10,17,53,23,0).

dadosCam_t_e_ta(eTruck01,11,1,164,65,42).
dadosCam_t_e_ta(eTruck01,11,2,88,41,0).
dadosCam_t_e_ta(eTruck01,11,3,65,28,0).
dadosCam_t_e_ta(eTruck01,11,4,42,18,0).
dadosCam_t_e_ta(eTruck01,11,5,55,25,0).
dadosCam_t_e_ta(eTruck01,11,6,118,57,31).
dadosCam_t_e_ta(eTruck01,11,7,74,23,0).
dadosCam_t_e_ta(eTruck01,11,8,59,23,0).
dadosCam_t_e_ta(eTruck01,11,9,63,28,0).
dadosCam_t_e_ta(eTruck01,11,10,97,46,0).
dadosCam_t_e_ta(eTruck01,11,12,111,52,25).
dadosCam_t_e_ta(eTruck01,11,13,25,7,0).
dadosCam_t_e_ta(eTruck01,11,14,126,58,33).
dadosCam_t_e_ta(eTruck01,11,15,53,25,0).
dadosCam_t_e_ta(eTruck01,11,16,59,27,0).
dadosCam_t_e_ta(eTruck01,11,17,67,27,0).

dadosCam_t_e_ta(eTruck01,12,1,76,23,0).
dadosCam_t_e_ta(eTruck01,12,2,61,19,0).
dadosCam_t_e_ta(eTruck01,12,3,67,32,0).
dadosCam_t_e_ta(eTruck01,12,4,97,41,0).
dadosCam_t_e_ta(eTruck01,12,5,92,38,0).
dadosCam_t_e_ta(eTruck01,12,6,19,8,0).
dadosCam_t_e_ta(eTruck01,12,7,82,42,0).
dadosCam_t_e_ta(eTruck01,12,8,86,33,0).
dadosCam_t_e_ta(eTruck01,12,9,128,61,37).
dadosCam_t_e_ta(eTruck01,12,10,32,6,0).
dadosCam_t_e_ta(eTruck01,12,11,109,50,23).
dadosCam_t_e_ta(eTruck01,12,13,120,53,26).
dadosCam_t_e_ta(eTruck01,12,14,40,10,0).
dadosCam_t_e_ta(eTruck01,12,15,78,38,0).
dadosCam_t_e_ta(eTruck01,12,16,126,54,28).
dadosCam_t_e_ta(eTruck01,12,17,74,32,0).

dadosCam_t_e_ta(eTruck01,13,1,174,65,42).
dadosCam_t_e_ta(eTruck01,13,2,107,35,0).
dadosCam_t_e_ta(eTruck01,13,3,74,29,0).
dadosCam_t_e_ta(eTruck01,13,4,46,11,0).
dadosCam_t_e_ta(eTruck01,13,5,67,20,0).
dadosCam_t_e_ta(eTruck01,13,6,128,57,31).
dadosCam_t_e_ta(eTruck01,13,7,80,30,0).
dadosCam_t_e_ta(eTruck01,13,8,76,20,0).
dadosCam_t_e_ta(eTruck01,13,9,67,20,0).
dadosCam_t_e_ta(eTruck01,13,10,105,47,0).
dadosCam_t_e_ta(eTruck01,13,11,27,7,0).
dadosCam_t_e_ta(eTruck01,13,12,122,52,25).
dadosCam_t_e_ta(eTruck01,13,14,137,58,33).
dadosCam_t_e_ta(eTruck01,13,15,67,17,0).
dadosCam_t_e_ta(eTruck01,13,16,59,15,0).
dadosCam_t_e_ta(eTruck01,13,17,78,22,0).

dadosCam_t_e_ta(eTruck01,14,1,59,18,0).
dadosCam_t_e_ta(eTruck01,14,2,80,35,0).
dadosCam_t_e_ta(eTruck01,14,3,80,38,0).
dadosCam_t_e_ta(eTruck01,14,4,109,46,0).
dadosCam_t_e_ta(eTruck01,14,5,105,45,0).
dadosCam_t_e_ta(eTruck01,14,6,27,9,0).
dadosCam_t_e_ta(eTruck01,14,7,97,48,0).
dadosCam_t_e_ta(eTruck01,14,8,99,38,0).
dadosCam_t_e_ta(eTruck01,14,9,143,66,45).
dadosCam_t_e_ta(eTruck01,14,10,61,17,0).
dadosCam_t_e_ta(eTruck01,14,11,122,57,31).
dadosCam_t_e_ta(eTruck01,14,12,42,10,0).
dadosCam_t_e_ta(eTruck01,14,13,132,58,35).
dadosCam_t_e_ta(eTruck01,14,15,90,44,0).
dadosCam_t_e_ta(eTruck01,14,16,139,61,37).
dadosCam_t_e_ta(eTruck01,14,17,86,38,0).

dadosCam_t_e_ta(eTruck01,15,1,132,51,24).
dadosCam_t_e_ta(eTruck01,15,2,74,30,0).
dadosCam_t_e_ta(eTruck01,15,3,34,8,0).
dadosCam_t_e_ta(eTruck01,15,4,36,12,0).
dadosCam_t_e_ta(eTruck01,15,5,36,14,0).
dadosCam_t_e_ta(eTruck01,15,6,86,44,0).
dadosCam_t_e_ta(eTruck01,15,7,34,16,0).
dadosCam_t_e_ta(eTruck01,15,8,42,13,0).
dadosCam_t_e_ta(eTruck01,15,9,71,35,0).
dadosCam_t_e_ta(eTruck01,15,10,82,36,0).
dadosCam_t_e_ta(eTruck01,15,11,53,25,0).
dadosCam_t_e_ta(eTruck01,15,12,80,38,0).
dadosCam_t_e_ta(eTruck01,15,13,69,18,0).
dadosCam_t_e_ta(eTruck01,15,14,95,45,0).
dadosCam_t_e_ta(eTruck01,15,16,69,29,0).
dadosCam_t_e_ta(eTruck01,15,17,53,17,0).

dadosCam_t_e_ta(eTruck01,16,1,179,68,45).
dadosCam_t_e_ta(eTruck01,16,2,92,37,0).
dadosCam_t_e_ta(eTruck01,16,3,84,31,0).
dadosCam_t_e_ta(eTruck01,16,4,57,16,0).
dadosCam_t_e_ta(eTruck01,16,5,46,18,0).
dadosCam_t_e_ta(eTruck01,16,6,132,60,35).
dadosCam_t_e_ta(eTruck01,16,7,92,42,0).
dadosCam_t_e_ta(eTruck01,16,8,67,23,0).
dadosCam_t_e_ta(eTruck01,16,9,15,3,0).
dadosCam_t_e_ta(eTruck01,16,10,105,46,0).
dadosCam_t_e_ta(eTruck01,16,11,57,28,0).
dadosCam_t_e_ta(eTruck01,16,12,130,52,25).
dadosCam_t_e_ta(eTruck01,16,13,61,15,0).
dadosCam_t_e_ta(eTruck01,16,14,141,61,37).
dadosCam_t_e_ta(eTruck01,16,15,69,29,0).
dadosCam_t_e_ta(eTruck01,16,17,65,24,0).

dadosCam_t_e_ta(eTruck01,17,1,128,46,0).
dadosCam_t_e_ta(eTruck01,17,2,42,14,0).
dadosCam_t_e_ta(eTruck01,17,3,40,11,0).
dadosCam_t_e_ta(eTruck01,17,4,42,13,0).
dadosCam_t_e_ta(eTruck01,17,5,34,10,0).
dadosCam_t_e_ta(eTruck01,17,6,82,38,0).
dadosCam_t_e_ta(eTruck01,17,7,74,30,0).
dadosCam_t_e_ta(eTruck01,17,8,29,6,0).
dadosCam_t_e_ta(eTruck01,17,9,69,31,0).
dadosCam_t_e_ta(eTruck01,17,10,55,24,0).
dadosCam_t_e_ta(eTruck01,17,11,69,29,0).
dadosCam_t_e_ta(eTruck01,17,12,80,30,0).
dadosCam_t_e_ta(eTruck01,17,13,82,23,0).
dadosCam_t_e_ta(eTruck01,17,14,90,38,0).
dadosCam_t_e_ta(eTruck01,17,15,53,18,0).
dadosCam_t_e_ta(eTruck01,17,16,67,25,0).

% entrega(<idEntrega>,<data>,<massaEntrega>,<armazemEntrega>,<tempoColoc>,<tempoRet>).
entrega(4439, 20221205, 200, 1, 8, 10).
entrega(4438, 20221205, 150, 9, 7, 9).
entrega(4445, 20221205, 100, 3, 5, 7).
entrega(4443, 20221205, 120, 8, 6, 8).
entrega(4449, 20221205, 300, 11, 15, 20).
%entrega(4398, 20221205, 310, 17, 16, 20).
%entrega(4432, 20221205, 270, 14, 14, 18).
%entrega(4437, 20221205, 180, 12, 9, 11).
%entrega(4451, 20221205, 220, 6, 9, 12).
%entrega(4452, 20221205, 390, 13, 21, 26).
%entrega(4444, 20221205, 380, 2, 20, 25).
%entrega(4455, 20221205, 280, 7, 14, 19).
%entrega(4399, 20221205, 260, 15, 13, 18).
%entrega(4454, 20221205, 350, 10, 18, 22).
%entrega(4446, 20221205, 260, 4, 14, 17).
%entrega(4456, 20221205, 330, 16, 17, 21).

%a armazensEntregas
armazens_entregas(L):- findall(K,entrega(_,_,_,K,_,_),L).

%b addMatosinhos
add_matosinhos(L,LB):-append([5],L,LA),append(LA,[5],LB).

%c nome_camiao
nome_camiao([C1,C2|_],Nome):- dadosCam_t_e_ta(Nome,C1,C2,_,_,_).


:-dynamic custo_min/2.

%c calcula_tempo
calcula_tempo(LC,Final):-
        nome_camiao(LC,Nome),
        bateria_camiao(Nome,CarM,TempR),
        nome_camiao(LC,Nome),
        peso_camiao(Nome,PesoC),
        tempo_recarga(LC,CarM,TempR,RecargaC,PesoC,Nome),
        tempo_extra(LC,ExtraC),
        tempo_entregas(LC,TempoE),
        tempo(LC,Custo,PesoC,Nome),
        somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final).


%d custo
tempo([_],0,_,_).
tempo([C1,C2|LC],Custo,PesoC,Nome):-
    entregas_peso(C1,LE),
    peso_entregas(LE,PesoE),
    PesoC1 is PesoC - PesoE,
    tempo([C2|LC],Custo1,PesoC1,Nome),
    (dadosCam_t_e_ta(_,C1,C2,Tempo,_,_)
    ;dadosCam_t_e_ta(_,C2,C1,Tempo,_,_)),
    peso_camiao(Nome,PesoB),
    Tempo1 is (PesoC1*Tempo)/PesoB,
    Custo is Custo1+Tempo1.

%e bateria_camiao (assumindo que o maximo de carga em e 80%)
bateria_camiao(Nome,CarM1,TempR):- carateristicasCam(Nome,_,_,CarM,_,TempR),CarM1 is CarM*(0.8).

%f peso do camiao (assumindo que possui carga maxima)
peso_camiao(Nome,PesoC):- carateristicasCam(Nome,Tara,CapC,_,_,_), PesoC is Tara + CapC.

%g tempo_extra
tempo_extra([_],0).
tempo_extra([C1,C2|LC],ExtraC):-
        tempo_extra([C2|LC],ExtraC1),
        (dadosCam_t_e_ta(_,C1,C2,_,_,Extra);dadosCam_t_e_ta(_,C2,C1,_,_,Extra)),
        ExtraC is ExtraC1 + Extra.

%h tempo_recarga
tempo_recarga([_],_,_,0,_,_).
tempo_recarga([C1,C2|LC],CarM,TempR,RecargaC,PesoC,Nome):-
        entregas_peso(C1,LE),
        peso_entregas(LE,PesoE),
        PesoC1 is PesoC - PesoE,
        tempo_recarga([C2|LC],CarM,TempR,RecargaC1,PesoC1,Nome),
        (dadosCam_t_e_ta(_,C1,C2,_,Energia,_);
        dadosCam_t_e_ta(_,C2,C1,_,Energia,_)),
        peso_camiao(Nome,PesoB),
        Energia1 is (PesoC1*Energia)/PesoB,
        ((CarM - Energia1 < 20, RecargaC is RecargaC1 + ((80 - (CarM - Energia1))*TempR)/60);RecargaC is RecargaC1 + 0).


%i entregas_peso
entregas_peso(C1,LE):- findall(M,entrega(_,_,M,C1,_,_),LE).

%j tempo_entregas
tempo_entregas([],0).
tempo_entregas([HC|LC],TempoE):-
        tempo_entregas(LC,TempoE1),
        buscar_entregas(HC,LI),
        entregas_tempo(LI,TempoT),
        TempoE is TempoE1 + TempoT.

%k buscar_entregas
buscar_entregas(HC,LI):-findall(Id,entrega(Id,_,_,HC,_,_),LI).

%l entregas_tempo
entregas_tempo([],0).
entregas_tempo([HI|LI],TempoT):-
        entregas_tempo(LI,TempoT1),
        entrega(HI,_,_,_,T,TS),
        TempoT is TempoT1 + (T + TS).

%m peso_entregas
peso_entregas([],0).
peso_entregas([HC1|LC1],PesoE):-
        peso_entregas(LC1,PesoE1), PesoE is PesoE1 + HC1.

%n somar_tudo
somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final):- Final is (RecargaC + ExtraC + TempoE + Custo).

%o seq_custo_min

seq_custo_min(LC,Final):-get_time(Ti),(run;true),custo_min(LC,Final),get_time(Tf),TSol is Tf-Ti,write("Tempo final:"),write(TSol), nl.

run:-
    retractall(custo_min(_,_)),
    assertz(custo_min(_,100000)),
    armazens_entregas(LC),
    permutation(LC,LCPerm),
    add_matosinhos(LCPerm,LCPerm1),
    calcula_tempo(LCPerm1,Final),
    atualiza(LCPerm1,Final),
    fail.

atualiza(LCPerm1,Final):-
  custo_min(_,FinalMin),
  ((Final<FinalMin,!,retract(custo_min(_,_)),assertz(custo_min(LCPerm1,Final)),
    write(Final),nl)
    ;true).

% o write(Custo),nl so para ver a atualizacao do menor custo

Cheers.

brebs · December 3, 2022, 1:58pm

It runs in a couple of seconds, if you replace the permutation line with LC = LCPerm

Do you really need that permutation line? Or could the permutation be moved to after the minimum value has been calculated?

Looks like you could use e.g. min_ratchet at clpBNR Guide to improve performance.

tripsytina · December 3, 2022, 4:07pm

I use the permutation so i can calculate the minimum time comparing all the permutated lists, so probably not.
Is there a way to make permutations without consuming so much time?

kuniaki.mukai · December 3, 2022, 6:36pm

If all permutations need to be generated, N=11 seems the maximum,
where N is the number of elements of the given list for permutations.
As you know, it grows rapidly huge, more worse than the notorius exponential 2^N.

% ?- N = 20, forall(between(1, N, J), (factorial(J, FJ), format("~w! = ~w\n", [J, FJ]))).
%@ 1! = 1
%@ 2! = 2
%@ 3! = 6
%@ 4! = 24
%@ 5! = 120
%@ 6! = 720
%@ 7! = 5040
%@ 8! = 40320
%@ 9! = 362880
%@ 10! = 3628800
%@ 11! = 39916800
%@ 12! = 479001600
%@ 13! = 6227020800
%@ 14! = 87178291200
%@ 15! = 1307674368000
%@ 16! = 20922789888000
%@ 17! = 355687428096000
%@ 18! = 6402373705728000
%@ 19! = 121645100408832000
%@ 20! = 2432902008176640000
%@ N = 20.

tripsytina · December 3, 2022, 6:54pm

Right, but my algorithm for only 6! takes an absurd time(i waited hours and it didnt even worked), i tried to calculate the exponential function and if it was correct my algorithm for 6! would take one hour and 30 minutes.
What i inted to know is if iam using incorrectly something that raises my the algorithm’s time drastically, because i believe it should be able to find the best solution in much less time.
I

peter.ludemann · December 3, 2022, 7:09pm

The number of permutations increases very fast. The only way I know of limiting this is to set up “lazy” constraints that prune the backtracking tree.

An example is here: nerdle/nerdle.pl at cfb3ff2c7b3f9ac488c559b4833ccb51b50bd8d6 · kamahen/nerdle · GitHub

    maplist(constrain(Puzzle), Guesses, Results),
    constrain_black(Puzzle, Guesses, Results),
    puzzle_fill(Puzzle), % generate permutations in Puzzle

where constrain_from_guess/3 uses dif/2 to set up inequalities, which greatly reduce the permutation tree. (This code also has some constraints after puzzle_fill/1; not all constraints can be set up “lazily”)

In your case, where you’re trying to minimize, you might need to use something like nb_setval/2 et al to keep track of the minimum and remove permutations as soon as their vaue is too high.
Another possibility is to use tabling with minimum.

Topic		Replies	Views
Permutations - Infinite Loop Error Help! discussion , how-to	2	486	December 2, 2022
An elegant codes on finding all permutations of a list General how-to , permutations	0	452	June 1, 2023
Help with tabling to avoid infinite left-recursion General	10	1078	December 20, 2019
Late Summer Challenge - Superpermutation in Prolog General	3	1823	September 17, 2019
Random permutations Help!	2	414	October 24, 2021

Permutations - Stuck in a infinite loop

Related topics