정렬 결정 트리를 생성하는 프로그램을 작성하려면 어떻게해야합니까?

Question

클래스에서 우리는 3 개의 원소 (a, b, c)를 정렬하기위한 간단한 의사 결정 트리가 주어졌습니다. 이 보면서

, 그것은 나에게 의미가 있습니다. 나는 그것을 따라갈 수 있었다.

그러나, 지금은 4 개 요소 (A, B, C, D) 내가 결정 트리에 접근 사투를 벌인거야 단지 24

까지 총 잎의 수에 대한 의사 결정 트리를 확인해야합니다 각 지점에서 비교할 요소를 추적하는 데 도움이되는 방법론적인 방법.

더 큰 의사 결정 트리의 구성에 접근하기위한 체계적인 방법은 무엇입니까? 나는 방법을 알았다면 가능한 리프 구조를 뱉어내는 프로그램을 기꺼이 쓸 것입니다.

Answer 1

알고리즘의 종류는 Charles Forgy가 설명했습니다. Rete algorithm을 참조하십시오. (죄송합니다. WP의 기사는 분명히 빠른 답변이 아니지만 좋은 시작일 수 있습니다.)

Answer 2

S orting Networks을 살펴볼 수 있습니다. 주어진 입력 수에 대한 최적의 정렬 네트워크를 의사 결정 트리로 변환 할 수 있어야한다고 생각합니다.

또는 주어진 정렬 알고리즘을 사용하여 단계별로 수행하여 비교할 때마다 새 분기를 만들 수 있습니다. 트리의 하단에있는 모든 24 개 가능한 정렬 순서를 배치합니다 : 예를 들어, 병합 - 정렬 형 접근 방식을 취함으로써 -

마지막으로, 당신은 역으로이 작업을 수행 할 수 있습니다. 비교를 선택하고 잎을 결과에 따라 두 세트로 나눕니다. 분기마다 리프가 하나만있을 때까지 각 분기마다 반복적으로 반복합니다.