응답 세트 프로그래밍에서 이것을 어떻게 인코딩합니까?

Question

나는 세트 프로그래밍에 답하는 완전히 초보자이며 다소 간단한 질문으로 어려움을 겪고 있습니다. 프로그램은 clingo로 작성되어야합니다.

그래서 여기에 질문이 있습니다.

추상 인수 프레임 워크는 인수 집합 A와 인수 간의 공격 관계 R ⊆ AXA로 구성됩니다. 두 인수 a1 및 a2에 대해 (a1, a2) ∈ R이면 a1이 a2를 공격한다고 말합니다. 하나가 인수 a1을 인정하면 인수 a2에 의심을 던집니다. 공식적으로, 인수 E ⊆ A의 하위 집합은 다음 두 조건이 충족되면 안정적입니다.

1. E의 인수는 E의 다른 인수를 공격하지 않습니다.
2. E 외부의 모든 인수는 E의 인수에 의해 공격을받습니다.

응답 집합을 통해 주어진 인스턴스에서 안정적인 인수 하위 집합을 식별하는 ASP 프로그램을 작성합니다. 인스턴스는 각각 A와 R에 해당하는 두 개의 술어 argument / 1 및 attack / 2를 통해 제공됩니다.

다음은 그 예입니다.

argument (a).    
argument (b).    
argument (c).    
argument (d).    
attack (a,b).    
attack (b,c).    
attack (d,c).

유효한 출력 :

choose (a) choose (d)

이것은 분명히 잘못된 것입니다.

choose(X)  :- argument(X), attack(X,Y).

나는 이것에 접근하는 방법을 전혀 모른다.

도와주세요.

Answer 1

간단한 3 단계 해결 방법은 다음과 같습니다.

1. 사실 설명 (확인)
2. 결과적으로 원하는 것을 생성하지만 프로그램을 선택하십시오.
3. 적용되지 않는 솔루션에 대한 규칙 제공

따라서 2로 시작하십시오.

가능한 결과를 생성합니다. 간단한 말로 생각해보십시오. 모든 논쟁에 대해 제가 선택하든 아니든.
는 수도 있고되지 않을 부분이 subsum으로 해결 될 수있다 {}.

{choose(X)} :- argument(X).

또는 더 간단합니다. 인수에서 부분합을 선택합니다.

{choose(X):argument(X)}. 

Potassco 및 #show choose/1., 공명 모드로 솔루션을 확인 하겠습니다 enumerate all.

Answer: 1

Answer: 2
choose(b)
Answer: 3
choose(c).
..
Answer: 15
choose(a) choose(b) choose(c)
Answer: 16
choose(a) choose(b) choose(c) choose(d)
SATISFIABLE

모든 조합이 발견됩니다. 잘못된 것을 제거 할 시간입니다. 다시 한 번 : 간단한 말로 생각해보십시오 . 하나가 다른 하나를 공격하는 두 가지 주장을 선택하는 것은 불가능합니다. (머리가 열려 있으면 False로 읽습니다.)

:- choose(X), attack(X,Y), choose(Y).

Now check it again:

Answer: 1

Answer: 2
choose(a)
Answer: 3
choose(d)
Answer: 4
choose(a) choose(d)
Answer: 5
choose(c)
Answer: 6
choose(a) choose(c)
Answer: 7
choose(b)
Answer: 8
choose(b) choose(d)
SATISFIABLE

Now we need to make sure every not choosen argument is attacked by a at least one choosen element:

1 {choose(Y):attack(Y,X)} :- argument(X), not choose(X).

Reads: For every argument X, which is not choosen, the number of choosen arguments which attack it, is at least one.

Lets check it:

Answer: 1
choose(a) choose(d)
SATISFIABLE

Nice.

Since the contraints are normally formulated with an empty head, lets reformulate the last rule:

:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

Reads: There is no argument X, which is not choosen and has maximum 0 choosen arguments, which attack X. It gives the same output.

Complete code:

argument (a;b;c;d).   
attack (a,b).    
attack (b,c).    
attack (d,c).

{choose(X):argument(X)}.
:- choose(X), attack(X,Y), choose(Y).
:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

#show choose/1.