Penetrance를 사용한 예 & State-space 휴리스틱 검색에서 분기 요소

다음 검색 트리를 고려하십시오. 휴리스틱 검색 알고리즘은 루트 노드에서 검색을 시작합니다. 확장되지 않은 노드는 회색으로 표시됩니다.

어떤 이유로 휴리스틱은 가장 왼쪽에있는 하위 트리로 안내됩니다. 실제로 목표 노드가 녹색으로 표시된 맨 오른쪽 하위 트리에있을 때

확장 된 것은 빨간색으로 표시됩니다. 가장 왼쪽에있는 매력적인 하위 트리가 막 다른 골목으로 밝혀진 후 휴리스틱은 운 좋게도 목표를 향해 직접 안내되고 있습니다. 이전 그림의 상황에서 목표에 도달하기 전에 총 3 개의 새 노드를 확장합니다.

위 그림에서 목표까지의 경로 길이는 $ 3 $입니다. $ 17 $의 확장 노드가 있습니다. 따라서 penetrance 는 $ 3 / 17 \ 약 0.43 $입니다.

분기 계수 가 최대 수입니다. 예를 들어 이진 트리의 분기 계수는 각 노드에 최대 2 개의 하위 항목이 있으므로 $ 2 $입니다. 마찬가지로 위의 검색 트리에서 분기 계수는 $ 3 $입니다.

무엇을 관심이있는 것처럼 보이는 것은 분기 요소가 아니라 유효 분기 요소 $ B ^ * $입니다. 확장 된 노드의 총 수가 $ T $이고 목표 경로의 길이가 $ L $ 인 경우 (이것은 일반적으로 s 깊이 ), $ B ^ * $는 $ T + 1 $ 노드를 포함하기 위해 $ L $의 균일 한 깊이 트리가 가지는 분기 인자입니다. 따라서

$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$

If 검색에서 얻은 값, 즉 $ T = 17 $ 및 $ L = 3 $를 플러그인하면 $ B ^ * \ approx 2.165 $가됩니다. 이것은 방정식을 사용하여 얻는 것과 똑같은 값입니다. 이는 단지 동일한 것을 다른 표현 일뿐입니다.

효과적인 분기 요소는 인스턴스마다 다를 수 있지만 충분히 어려운 문제에 대해서는 일정합니다. 잘 설계된 휴리스틱은 $ B의 값을 갖습니다. ^ * $가 $ 1 $에 가깝기 때문에 상당히 큰 문제를 저렴하게 해결할 수 있습니다.

댓글

• $ B $에 대한 공식을 풀면 $ B \ approx 2.165 $를 얻습니다. 그 값의 해석이 무엇인지 궁금합니다. 모든 내부 노드의 평균 분기 계수에 가깝지만 동일하지는 않습니다. ' li>
• @MAcad 실제로 관심있는 것은 분기 요소가 아니라 휴리스틱의 품질을 특성화 할 수있는 유효 분기 요소입니다. I ' 내 답변을 업데이트하겠습니다.
• @Juho 분기 인자 공식을 사용하면 LHS에서 많은 숫자를 테스트하고 계산하여 다음과 같이 RHS와 동일한 지 확인합니다. B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 같지 않음 T = 17 따라서 B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 결과가 T에 가까워 지므로 결과 T에 도달 할 때까지 B = 2.1 등을 테스트 할 수 있습니다 !!!! 이 공식은 다음과 같이 사용할 수 있다고 생각합니다 :))))