Preciso de um exemplo de como calcular a penetrância e fator de ramificação da árvore de pesquisa em pesquisa heurística em espaço de estado. As definições são as seguintes. Penetração $ P $ é definida por
$ \ qquad \ displaystyle P = \ frac {L} {T} $
e fator de ramificação $ B $ é definido por
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
onde $ L $ é o comprimento do caminho da raiz até a solução e $ T $ o número total de nós expandidos.
Resposta
Considere a seguinte árvore de pesquisa. Seu algoritmo de pesquisa heurística inicia a pesquisa no nó raiz. Nós não expandidos são marcados em cinza.
Por algum motivo, a heurística está sendo direcionada para a subárvore mais à esquerda, quando na verdade o nó da meta está na subárvore mais à direita, marcada com verde.
Nós que têm expandidos são marcados em vermelho. Depois que a atraente subárvore mais à esquerda acabou se revelando um beco sem saída, a heurística agora está sendo guiada diretamente para o objetivo. A partir da situação da figura anterior, expandiremos um total de três novos nós antes de chegar à meta.
Pela figura acima, o comprimento do caminho para a meta é $ 3 $. Existem $ 17 $ nós expandidos. Portanto, a penetrância é $ 3/17 \ aproximadamente 0,43 $.
O fator de ramificação é o número máximo de sucessores de qualquer nó. Por exemplo, o fator de ramificação de uma árvore binária é $ 2 $, pois cada nó tem no máximo dois filhos. Da mesma forma, na árvore de pesquisa acima, o fator de ramificação é $ 3 $.
O que você parece estar interessado não no fator de ramificação, mas no fator de ramificação efetivo $ B ^ * $ que é uma maneira para caracterizar a qualidade de uma heurística. Se o número total de nós expandidos for $ T $, e o comprimento do caminho para a meta for $ L $ (isso é mais comumente conhecido como s profundidade ), então $ B ^ * $ é o fator de ramificação que uma árvore uniforme de profundidade $ L $ teria para conter $ T + 1 $ nós. Portanto,
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Se se você inserir os valores que obtivemos na pesquisa, ou seja, $ T = 17 $ e $ L = 3 $, você obterá $ B ^ * \ approx 2.165 $. Este é exatamente o mesmo valor que você obtém usando sua equação; é apenas uma representação diferente para a mesma coisa.
O fator de ramificação efetivo pode variar entre as instâncias, mas é algo constante para problemas difíceis o suficiente. Uma heurística bem projetada teria um valor de $ B ^ * $ perto de $ 1 $, permitindo que problemas razoavelmente grandes sejam resolvidos de forma razoavelmente barata.
Comentários
- Resolvendo a fórmula para $ B $, você obtenha $ B \ approx 2,165 $. Gostaria de saber qual é a interpretação desse valor. Ele ' está próximo do fator de ramificação médio de todos os nós internos, mas não é o mesmo.
- @MAcad Na verdade, o que você está interessado, não é o fator de ramificação, mas o fator de ramificação eficaz que é longe de caracterizar a qualidade de uma heurística. I ' atualizarei minha resposta.
- @Juho eu acho que se eu usar a fórmula do fator de ramificação, testarei muitos números no LHS e os calcularei e verificarei a igualdade com RHS da seguinte forma: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 diferente de T = 17, portanto, precisamos testar B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 o resultado próximo de T então podemos testar B = 2,1 e assim por diante até chegar ao resultado T !!!! Acho que esta fórmula pode ser usada assim :))))