회피 부울 함수

이 글에는 출처가 없다 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Evirative Boolean function" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2014년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

수학에서 회피 부울 함수 function (n 변수)는 모든 의사결정 트리 알고리즘의 실행 시간이 정확히 n인 부울 함수다.따라서 함수를 나타내는 모든 결정 트리 알고리즘은 최악의 경우 실행 시간이 n이다.

예

비침습적 부울함수의 예

다음은 세 변수 x, y, z의 부울함수다.

${\displaystyle ~f(x,y,z)~}$	${\displaystyle ~=}$	$(x\displaystyle ~(x\land y)~}$	$(\displaystyle ~\lor ~})$	$(\displaystyle ~(\neg x\land z)~}$
	${\displaystyle ~=}$		$(\displaystyle ~\lor ~})$

(여기서 $\wedge {\displaystyle }$ ${\displaystyle \land}$은(는) 비트의 "및"이고$,{\displaystyle }$ { ${\displaystyle \lor}$은(는) 비트의 "또는"이며$$,$\$ {\$displaystyle \neg}$은(는) 비트의 "not"이다$$.

이 함수는 다음과 같은 두 가지 변수를 정확히 확인하여 해결하는 의사결정 트리가 있기 때문에 회피하지 않는다.알고리즘은 먼저 x의 값을 확인한다. x가 참이면 알고리즘은 y의 값을 확인하여 반환한다.

( ${\displaystyle \mathrm{\neg }}$ ${\displaystyle x}$= ${\displaystyle \text{false}}$ )${\displaystyle \Rightarrow }$ (${\displaystyle \mathrm{\neg }}$ ${\displaystyle x}$ ${\displaystyle \wedge }$ z${\displaystyle }$)${\displaystyle }$= ${\displaystyle \text{false}}$) ${\displaystyle (\neg x={\text{false}})~~\Rightarrow ~~~(\neg$x\$land$ z$)={\text{false}}}}})}})$

x가 거짓일 경우 알고리즘은 z 값을 확인하여 반환한다.

회피 부울 함수에 대한 간단한 예제

다음과 같은 세 가지 변수에 대해 간단한 "및" 함수를 고려하십시오.

${\displaystyle ~f(x,y,z)~}$	${\displaystyle ~=(x\displayy y\j)~}$

최악의 경우 입력(모든 알고리즘에 대해)은 1, 1, 1이다.변수를 확인하는 순서를 선택할 때마다 모든 변수를 확인해야 한다. (일반적으로 모든 의사결정 트리 알고리즘에 대해 다른 최악의 경우 입력이 있을 수 있다는 점에 유의하십시오.)따라서 함수: "및", "또는 (n 변수)는 회피한다.

이진 제로섬 게임

바이너리 제로섬 게임의 경우 모든 평가 기능이 회피적이다.

모든 제로섬 게임에서 게임의 가치는 미니맥스 알고리즘에 의해 달성된다(플레이어 1은 이윤을 극대화하려고 하고, 플레이어 2는 비용을 최소화하려고 노력한다).

2진법의 경우, 최대 함수는 비트 "or"와 같고, 최소 함수는 비트 "and"와 같다.

이 게임의 결정 트리는 다음과 같은 형식이 될 것이다.

• 모든 잎은 {0, 1}에 가치가 있을 것이다.
• 모든 노드가 {"and", "또는"} 중 하나에 연결됨

잎이 n개인 모든 트리의 경우, 최악의 경우 실행 시간은 n(알고리즘이 모든 잎을 확인해야 한다는 의미)이다.

알고리즘이 확인하는 모든 리프에 대해, 잎의 모체가 Or 노드일 경우 0으로, 모체가 And 노드일 경우 1로 응답하는 최악의 입력을 생성하는 적수를 보여줄 것이다.

이 입력(모든 Or 노드의 하위 노드에 대해 0, 모든 And 노드의 하위 노드에 대해 1)은 알고리즘이 모든 노드를 확인하도록 강제한다.

두 번째 예와 같이

• OR 결과를 계산하기 위해서, 만약 모든 아이들이 0이라면, 우리는 그들 모두를 확인해야 한다.
• And 결과를 계산하기 위해서, 만약 모든 아이들이 1이라면 우리는 그들을 모두 확인해야 한다.

참고 항목

• Aanderaa-Karp-Rosenberg 추측, 모든 비경쟁 단조 그래프 속성이 회피적이라는 추측이다.