Na programação de restrições, existem modelos que levam em consideração o número de alterações de variáveis?

10

Considere um modelo de CSP em que a alteração do valor de uma variável específica seja cara. Existe algum trabalho em que a função objetivo também considere o número de alterações no valor da variável durante o processo de busca?

Um exemplo: a variável dispendiosa para alterar pode estar no controle de outro agente e há alguma sobrecarga em envolver esse agente para alterar a variável. Outro exemplo: a variável participa de uma das restrições e a satisfação dessa restrição envolve chamar uma função cara (como um simulador), por exemplo, é a restrição é um elemento caro. função de cálculo. Portanto, e são variáveis ​​caras para alterar.f x yz=f(x,y)fxy

algorithms constraint-programming amit
fonte
11
A função objetivo fala sobre os valores finais do CSP e não tem conhecimento do processo de pesquisa. Portanto, nas formulações padrão, as alterações nessas variáveis ​​não são expostas ao modelo CSP. Alguns solucionadores, como o Choco, fornecem heurísticas para orientar o processo de pesquisa. Alguns deles podem até ser definidos pelo usuário. Talvez seja esse o lugar para mudar a maneira como a pesquisa é feita.
perfil completo de Dave Clarke
11
Mas por que a função objetivo refletia o quanto era caro apresentar a solução? Você não deve comparar as soluções pela utilidade delas posteriormente no domínio do problema? Ou o tempo para a solução faz parte do problema do mundo real?
Raphael
11
Parece que você está no cenário de satisfação de restrições distribuídas e parece que está procurando heurísticas.
perfil completo de Dave Clarke

Respostas:

4

xycosts(x,y)≤Bvocêdget. Essa formulação tende a se encaixar perfeitamente nas estruturas existentes como uma restrição adicional. Obviamente, pode ser difícil especificar a função de custo e o orçamento permitido de forma a obter soluções significativas - isso dependerá do problema específico que você está tentando resolver.

usuario
fonte