O que é Rete?

O algoritmo Rete é um algoritmo de correspondência de padrões projetado pelo Dr. Charles L. Forgy da Universidade Carnegie Mellon. Rete é uma palavra latina que significa rede [1]. É um algoritmo muito eficiente para combinar fatos com os padrões nas regras. Compreender o algoritmo Rete facilitará a compreensão de por que escrever regras de uma maneira é mais eficiente do que escrevê-las de outra maneira.

Regras, Conjunto de Regras e Fatos

Um conjunto de regras não é nada mais do que uma base de conhecimento que consiste em uma ou mais regras comerciais (ou simplesmente regras). Cada regra no conjunto de regras representa algum conhecimento. As regras geralmente estão na forma de se-então ou condição-ação. Como as regras se-então são adequadas para o algoritmo Rete, são chamadas de regras Rete. Aqui está uma regra Rete simples

Se a idade > 60 então atribuir estado = "Idoso"

Onde se , então e atribuir são palavras-chave. A parte se representa a condição e a parte então representa a ação. Pode haver mais de uma condição e, nesse caso, as condições devem ser unidas com operadores lógicos. A parte então representa uma ou mais ações. Claramente, a regra de exemplo acima significa que se a idade de uma pessoa for superior a 60 anos, então é um idoso. Se quisermos verificar se uma pessoa é idosa ou não, precisamos de um dado que é a idade da pessoa e esse dado é chamado de fato. À medida que o número de variáveis ou definições únicas aumenta, também aumenta o número de fatos. Por exemplo,

Se a idade > 60 e renda-anual < 12000 então atribuir bônus-mensal = 2000

Para executar a regra acima, precisamos de dois dados ou fatos: um para a idade e outro para a renda-anual. Para verificar o bônus de duas pessoas, precisamos de dois pares de dados, e assim por diante. Este é um caso simples e em situações da vida real podemos ter milhares de fatos nos quais a regra deve operar. E também podemos ter milhares de regras diferentes.

Necessidade do Algoritmo Rete

Um conjunto completo de regras deve ser fornecido ao motor de regras para processamento posterior. O motor de regras combina cada regra (ou seja, condição) no conjunto de regras com os fatos fornecidos para decidir se disparar (ou executar) a regra ou não. Esse processo é chamado de processo de correspondência de padrões e é repetido. Em cada ciclo, a lista de fatos pode ser modificada: novos fatos podem ser adicionados à lista ou os fatos antigos podem ser removidos da lista. Essas mudanças podem fazer com que os padrões anteriormente insatisfeitos sejam satisfeitos. Além disso, durante cada ciclo, o conjunto de regras satisfeitas deve ser mantido e atualizado. Na maioria dos casos, as ações das regras apenas alteram alguns fatos na lista. Isso é chamado de redundância temporal. Se um motor de regras verificar cada regra para direcionar a busca de todos os fatos, mesmo que a maioria deles não seja modificada, então o processo será mais lento. Essa computação desnecessária pode ser evitada lembrando o que já foi correspondido de ciclo a ciclo e calculando apenas as alterações necessárias para os fatos recém-adicionados ou removidos. O algoritmo Rete faz esse trabalho perfeitamente.

Algoritmo Rete: Implementação

O algoritmo Rete é implementado construindo uma rede de nós. Ele é projetado de forma a guardar o estado do processo de correspondência de ciclo a ciclo e recalcular as mudanças apenas para os fatos modificados. O estado do processo de correspondência é atualizado apenas à medida que os fatos são adicionados e removidos. Se os fatos adicionados ou removidos forem em menor número, então o processo de correspondência será mais rápido.

O Ciclo de Inferência

Cada regra tem um ciclo de inferência que consiste em três fases: correspondência, seleção e execução. Na fase de correspondência, as condições das regras são combinadas com os fatos para determinar quais regras devem ser executadas. As regras cujas condições são atendidas são armazenadas em uma lista chamada agenda para disparo. Da lista de regras, uma regra é selecionada para ser executada ou disparada. A estratégia de seleção pode depender da prioridade, recentidade de uso, especificidade da regra, ou outros critérios. A regra selecionada da lista é executada realizando as ações no lado direito da regra. A ação pode ser uma afirmação, executar uma função definida pelo usuário ou incorporada, executar uma tabela de decisões, ou de outra forma. Note que o motor de tabelas de decisões é usado para executar tabelas de decisões.