2017-01-31 7 views
-1

정수 입력 배열이 규칙 세트와 "일치"하는지 여부를 결정하고 싶습니다.복잡한 필터 규칙을 유사한 형식으로 줄임

Matcher 입력 데이터에 대한 규칙을 설명하는 헬퍼 메소드들의 세트로부터 세우는

매처. 이 규칙은 정수의 배열에 기본적으로 논리 게이트 있습니다

AND(1, 2) // Requires both 1 AND 2 be present in the input array. 
OR(3, 4, 5) // Requires that 3 OR 4 OR 5 be present in the input array. 
NOR(6, 7) // Requires that neither 6 NOR 7 be present in the input array. 
XOR(8, 9) // Requires that either 8 (X)OR 9 be present in the input array, but not both. 

따라서, 내가 말할 수있는, 입력 배열을 지정해 : 내가 만들 수

[0, 1, 2, 3] 

Matcher 같은 :

AND(OR(0, 1), AND(1, 2) NOR(4)) 

입력이 다음을 만족하기 때문에 입력과 일치합니다.

OR(0, 1) // 0 or 1 is present 
AND(1, 2) // Both 1 and 2 are present 
NOR(4) // 4 is not present 

그리고 이들 각각은 누적 적으로 AND 규칙을 만족합니다.

문제는

는 여전히 규칙을 설명하는 가장 간단하고 기본적인 형태에 매처 (matcher)를 줄일 필요가있다. 예를 들면, 상기 정합 주어진 샘플 감소 될 수있다 :

rules = { 
    or: [1, 2], 
    xor: [], // No XORs 
    nor: [4] 
} 

각 정수 rulerule 또는 S로 구성된 서브 규칙의 세 가지 배열을 갖는다.

1이 반드시 필요하기 때문에 OR이 비어 있습니다. 이는 만족해야하므로 OR(0, 1) => [0, 1]이 중복됨을 의미합니다. 이제

input = [1, 2, 5, 9, 11, 12, 13, 14, 17] 

XOR(OR(AND(1, 2), NOR(3, 4), XOR(3 11), AND(11, 14)), AND(1, 5, 17)) 

, 많은 양의 :

Matcher 이후의 (나는 기본 규칙 사이의 동등성을 판단 할 수 있어야합니다) 내가에 도착하면, 그것은 조금 더 복잡하게 비교해야 그것의 중복 및/또는 모순, 그래서 내가 할 수있는 생각은 처음으로 그것을 나무 같은 구조로 배치하고, 다음 그것을 재발행하고 불필요한 항목을 줄일 수 있습니다. 이 작업을 수행하는 더 좋은 방법에 대한 아이디어가 있습니까?

저는 특히 결정론적인 것을 말합니다 (동일한 최종 축소 형을 산출하는 입력 규칙의 집합). 이 문제를 표현하는 더 좋은 방법이 있다면, 저는 관심이 있습니다. 규칙이 모순되면 예외를 파기하고 감속시키는 것이 좋습니다. 이는 프로그램에서 가끔씩 사용하기위한 것이므로 성능에 별 문제가되지 않습니다.

+0

그래서 이것은 NP 완성이고 해결할 가능성이없는 만족할만한 문제의 사례 일 수 있다고 알려졌습니다. – AniSkywalker

답변

1

여기서 실제로 다루는 내용은 propositional logic입니다. 정수 배열이 입력 배열에 있는지에 따라 false 또는 true 인 제안을 고려하십시오.

제약 조건 (XOR, AND 등)은 만족할만한 논리적 공식을 형성합니다. 실제로 주어진 공식에 대해 그것이 만족 스러운지 알아내는 것은 사실상 어렵습니다. 그러나 처음에는 주어진 입력이 수식을 만족시키는 지 여부 만 확인하면되기 때문에 걱정하지 않아도됩니다.

실제로 불만을 제기하는 것은 두 개의 명제식이 동일한 지 여부를 결정할 수있는 방법입니다. 이것은 똑같이 어렵다는 것을 알게됩니다 : https://math.stackexchange.com/questions/1050127/how-to-efficiently-determine-if-any-two-propositional-formulas-are-equivalent