Modify-Cost

Modify-Cost

por Marcela Ortega -
Número de respostas: 14
Olás
Meu EP ainda não está funcionando e estou confusa sobre a função Modify-Cost.

Primeiro, encontro o caminho ótimo inicial, daí vou percorrendo esse caminho até verificar que o custo da célula a para célula b não era o esperado.
A partir daí, devo chamar a Modify-Cost.
Pelo que entendi, c(b,a) é o custo novo encontrado, então, se o b já não estava mais na lista, devo coloca-lo.

Eu entendi errado? Meu robô está passando pela parede. mostrando a língua
Ah! Não entendi porque a função devolve get-kmin.

Alguém pode me ajudar?
Professor, se a pergunta "quebrar as regras" do uso do PACA, por favor, me avise.

Outra coisa, alguém sabe se a entrega ficou para amanhã ou para o dia da prova?

Muito obrigada!
Em resposta à Marcela Ortega

Re: Modify-Cost

por Thiago Figueiredo da Silva -

Não sei se isso ajuda para o seu caso ou se quebro as regras.

Mas acho que seria necessário atualizar o h(b) também, senão ele continua achando que aquele é o melhor caminho.

Em resposta à Thiago Figueiredo da Silva

Re: Modify-Cost

por Willian Gigliotti -
Então

c(a,b) é o custo de ir para a vindo de b (Isso me deixou confuso durante um tempo)

No artigo ele faz uso da função auxiliar INSERT(X, Hnew) e ela faz umas verificações para acidionar corretamente as coisas.

quem entra na OPEN list é a parede, depois com com as chamadas da PROCESS-STATE a posição nova do robo acaba entrando na OPEN e o custo é propagado para o resto dos estados.




Também estou com uns problemas com o meu, para um mapa pequeno (8x8) ele rodou sem problemas... para um maior (16x16) ele vai bem, desviando bonitinho, mas uma hora ele seca a OPEN list sem achar o melhor caminho triste


Para que dia realmente é o EP? cada dia que entro na página da entrega tem uma data difernete :P
Em resposta à Willian Gigliotti

Re: Modify-Cost

por Marcela Ortega -
Obrigadas. sorriso

Eu fiz a função Insert como está no paper, mas ainda não encontrei o erro.
Em resposta à Marcela Ortega

Re: Modify-Cost

por Marcela Ortega -
Olás de novo

Quando o custo de a->b é atualizado, a célula da parede (b) é colocada na fila.
Após a execução do modify-cost, na primeira chamada do o process-state, a célula b que é selecionada (pelo menos é isso que acontece aqui).

A minha dúvida é: qual execução da função process-state deve alterar o caminho (alterar backpointers(a)) ?
Não sei se é quando 'a' , 'b' ou algum possível vizinho de 'a' é retirado da fila (faz o papel de X no pseudo código).

Se alguém puder me responder isso, eu agradeço MUITO! sorriso
obrigadas
Em resposta à Marcela Ortega

Re: Modify-Cost

por Thiago Figueiredo da Silva -

Não sei se mudei demais o algoritmo, mas pra mim no caso de mudar o custo de A para B, eu colocaria o A na fila.

Aí a mudança do backpointer do A aconteceria na primeira execução dele, se possível. Se ele tivesse que voltar no caminho ele atualizaria o backpointer do "pai" dele e colocaria o A de volta na fila.

Bom, acho que é isso. Se falei alguma besteira, alguém corrija.

Em resposta à Marcela Ortega

Re: Modify-Cost

por Willian Gigliotti -

Faz sentido que o estado 'b' seja a primeira selecionada pela process-state, pois ela tem o menor K, já que seria o próximo estado do caminho ótimo, mas não sei se da para garantir isso.

Quando o estado 'b' é seleciondo pela process-state ela coloca o estado a na OPEN list através da linha L11 e L13, porém ela não muda o backpointer de 'a'. Nesse ponto h(a) = infinito , pois b(a) = b, e k(a) é k(b) + 1

(Na minha implementação eu usei c(x,y) = 1 se vizinhos e c(x,y) = inf se x é parede )

Como k(a) é quase tão baixo quanto k(b) ele tem grandes chances de ser chamado em seguida pela process-state, então o b(a) é alterado na linha L7 pois passa pelo if da linha L4 ( Kold < h(a) )

Então, respondendo a sua pergunta, b(a) é alterado quando 'a' é retirado da fila, mas pode acontecer dele ser modificado novamente, pois algum outro vizinho de a pode entrar na OPEN list.

Em resposta à Willian Gigliotti

Re: Modify-Cost

por Thiago Figueiredo da Silva -
Acho que no fim tanto faz um ou outro, já que um vai colocar o outro na lista se for necessário.
Mas não vejo muito sentido em colocar o B, já que o backpointer do A que precisa ser mudado. O custo do B pro b(B) continua o mesmo, e não vai ser necessário mudar.
Em resposta à Thiago Figueiredo da Silva

Re: Modify-Cost

por Willian Gigliotti -
É que quando você coloca o B na lista, ele não atualiza apenas o A, mas sim todos os vizinhos C de B tal que b(C) = B
Em resposta à Willian Gigliotti

Re: Modify-Cost

por Thiago Figueiredo da Silva -
Talvez seja o jeito como implementei, mas continuo não vendo muito sentido.

O único que precisará ser mudado é o A. Os outros que tem o backpointer em B não vão ter seus custos alterados, então não seria necessário mudar.
Em resposta à Thiago Figueiredo da Silva

Re: Modify-Cost

por Paulo Cheadi Haddad Filho -
Ainda não consegui entender o h(G,X)

Como ele estima o custo? Percorrendo o caminho de G até X e somando?
Se for, ele não deveria fazer isso pra todos os caminhos possíveis?

Ou eu tô viajando por completo...?
Em resposta à Paulo Cheadi Haddad Filho

Re: Modify-Cost

por Willian Gigliotti -

Como inicialmente o robo não sabe da existência de obstáculos ele imagina o melhor dos mundos (não existem obstáculos) inicialmente o h(G,X) é a distância de norma 1 entre G e X. Conforme o algorítmo vai sendo executado ele vai aperfeiçoando o valor de h(G,X) (através da função INSERT).

A propósito, consegui resolver meu problema do robo louco...

Se alguém estiver usando a HEAP do python para a fila de prioridade das KEYs, cuidado, a função min(lista) não retorna o mesmo elemento que a função heapq.heappop(lista).

Se você quer acessar o menor elemento da heap basta acessar lista[0] :P

Em resposta à Willian Gigliotti

Re: Modify-Cost

por Paulo Cheadi Haddad Filho -
Oi Willian!

O tal mundo perfeito pode ter mais de um caminho, não?

Considerando que o tal custo é 0 quando é possível caminhar entre duas casas vizinhas e "prohibitively large" pros obstáculos, a menos q o robô (X) e o objetivo (G) estejam na mesma linha do labirinto vão existir alguns caminhos possíveis.

Então refaço as minhas perguntas: como escolher a qual dos caminhos possíveis se refere h(G,X). Se isso não fizer sentido, q parte do experimento eu deixei de perceber?

Obrigado!