Início / coding / Perguntas / 78231796
Accepted
Diallo Francis Patrick
Asked: 2024-03-27 20:43:25 +0800 CST

O Timefold Solver aplica as restrições com base na prioridade/ordem das restrições (de ConstraintProvider) por padrão?

  • 772

O Timefold Solver aplica (e verifica) as restrições em uma ordem (ou prioridade) definida em ConstraintProvider por padrão? Ou, para ser mais exato, como funcionam as restrições do Solver quando ele tenta resolver um problema específico?

Considere o seguinte caso com 2 restrições:

  • Restrição A (com uma implementação complexa)
  • Restrição B (com uma implementação simples; ou seja, verificação simples de uma condição)

Qual é a ordem em que essas duas restrições são aplicadas?

E existe uma maneira de ordenar as restrições em ConstraintProvider para que as restrições sejam aplicadas de forma mais eficiente?

Por exemplo:

Caso a) : A ordem das restrições é Restrição A, Restrição B

Após aplicar a Restrição A (e realizar os movimentos necessários para uma melhor solução), na Restrição B haverá chances de não haver penalização.

Caso b) : A ordem das restrições é Restrição B, Restrição A

Após aplicar a Restrição B (e realizar os movimentos necessários para uma melhor solução), na Restrição A haverá chances de penalizações adicionais.

Espero que as perguntas façam sentido. Caso contrário, sinta-se à vontade para editar esta postagem. Qualquer ajuda será apreciada.

constraints

1 respostas

  1. Best Answer

    Não há ordenação de restrições porque todas as restrições existem num grande balde e não podem ser distinguidas umas das outras, como líquidos misturados numa solução homogénea . Todas as restrições são avaliadas simultaneamente.

    Considere os dois fluxos de restrição:

    A: forEach(Visit.class)
       .penalize(ONE_SOFT)
B: forEach(Visit.class)
       .filter(visit -> !visit.isApplicable())
       .penalize(ONE_HARD)

    Observe que eles compartilham algo em comum:

    forEach(Visit.class)

    Isso significa que o solucionador enviará todos Visitos s primeiro. (E, portanto, não importa quantas restrições você tenha, Visits será processado apenas uma vez!) A partir daí, Visits continuará a:

    A2: penalize(ONE_SOFT)
B2: filter(...)

    Em A2, todas as Visitinstâncias serão encerradas com penalidade. Em B2, entretanto, todas Visitas instâncias que correspondem ao filtro continuam:

    B3: penalize(ONE_HARD)

    E aí, todo Visito processamento finalmente termina.

    Em outras palavras - as restrições constroem um gráfico de nós; as fontes são forEach()nós e os sumidouros são penalidades. E então o solucionador envia todos os fatos e entidades do problema por meio desse gráfico. Esses nós têm uma ordem na qual serão processados, e essa ordem provavelmente estará relacionada à ordem original das restrições que criaram esses nós, mas é amplamente irrelevante - se os nós fossem ordenados de forma diferente, o resultado seria exatamente o mesmo; a única coisa que importa são as arestas entre esses nós. Começamos a partir dos nós de origem e avançamos ao longo das bordas em direção aos nós coletores.

    A partir disso, espero que você possa ver que não há ordem de restrição. Todas as restrições são quebradas e transformadas em uma rede de nó único, que possui penalidades no final. Isso é basicamente o que um algoritmo RETE faz.

    • 1

relate perguntas