부울 만족도에 대한 클래스 스케줄링 [다항식 시간 단축]

부울 만족도에 대한 클래스 스케줄링 [다항식 시간 단축]

이론적/실제적인 문제가 있는데 어떻게 관리해야 할지 현재로서는 알 수 없습니다. 다음과 같습니다.

저는 유전 알고리즘을 사용하여 모델이 존재할 때 모델을 찾고 C의 CNF 문제가 아닐 때 모순을 증명할 수 있는 SAT 해결사를 만듭니다.

문제처럼 : SAT 문제기으다같음문보입다럼니제처종류의은과.제 목표는 이 해결사를 사용하여 다양한 NP-완전 문제에서 해결책을 찾는 것입니다.기본적으로 저는 다양한 문제를 SAT로 변환하고, 해결사로 SAT를 해결한 다음 솔루션을 원래 문제에 적합한 솔루션으로 변환합니다.

저는 이미 N*N 스도쿠와 N-퀸 문제에 성공했지만, 여기 제 새로운 목표가 있습니다: 수업 스케줄링 문제를 SAT로 줄이는 것입니다. 하지만 저는 수업 스케줄링 문제를 SAT 이후에 쉽게 변환하기 위해 어떻게 공식화해야 할지 모르겠습니다.

목표는 분명히 몇 달 안에 다음과 같은 일정의 그림을 생성하는 것입니다.

안타깝게도 SAT를 줄이지 않고 수업 일정을 해결할 수 있는 소스 코드를 찾았습니다 :/

저는 또한 일반적인 계획에 관한 기사들을 발견했습니다(예: http://www.cs.rochester.edu/users/faculty/kautz/papers/kautz-satplan06.pdf ).

그러나 이 기사에 사용된 계획 도메인 정의 언어는 수업 일정 문제를 나타내기에는 너무 일반적인 것 같습니다.:/

SAT로 줄이고 SAT 솔루션(존재하는 경우 ^^)을 클래스 일정으로 변환하기 위해 효율적으로 클래스 일정을 공식화하는 방법에 대한 아이디어가 있습니까?

저는 기본적으로 어떤 제안이든 할 수 있습니다. 현재로서는 어떻게 표현해야 할지, 어떻게 문제를 줄일 수 있을지, 어떻게 SAT 솔루션을 일정으로 변환해야 할지 전혀 모르겠습니다.

---

후속 질문: 부울 만족도에 대한 수업 스케줄링 [다항 시간 단축] 파트 2

먼저 문제를 공식화한 후 SAT로 줄이려고 합니다.

클래스 스케줄링 문제를 다음과 같이 정의합니다.

Input = { S1,S2,....,Sn | Si = {(x_i1, y_i1), (x_i2, y_i2) , ... , (x_ik, y_ik) | 0 <= x_ij < y_ij <= M } } 

: 이고, 각는 ( 입스집고이, 스는클열 (x,y) 형간린 (x,y) 식의다 (x,) 집격니 열린) 구간 집합입니다.
(M은 "주말"을 설명하는 상수입니다.)

출력: true는 일부 세트가 존재하는 경우에만 해당됩니다.

R = { (x_1j1, y_1j1) , ..., (x_njn, y_njn) | for each a,b: (x_aja,y_aja) INTERSECTION (x_bjb,y_bjb) = {} }

비공식적으로: 각 구간 쌍 사이의 교차점이 비어 있도록 구간이 할당된 경우에만 true입니다.

---

SAT로 축소:

각 구간에 대해 부울 변수를 정의합니다.V_ij
이를 바탕으로 공식을 정의합니다.

F1 = (V_11 OR V_12 OR ... OR V_1(k_1)) AND .... AND (V_n1 OR V_n2 OR ... OR V_n(k_n))

비공식적으로, F1은 각 클래스의 간격 중 적어도 하나가 "만족"하는 경우에만 만족됩니다.

정의Smaller(x,y) = true만일의 경우에만if x <= y¹
간격이 겹치지 않도록 사용하겠습니다.
(x1,y1)과 (x2,y2)가 겹치지 않도록 하려면 다음이 필요합니다.

x1 <= y1 <= x2 <= y2 OR  x2 <= y2 <= x1 <= y1

입력 보증이 보장되기 때문에x1<=y1, x2<=y2다음으로 감소:

y1<= x2 OR y2 <= x1

또한 소규모 절과 부울 절을 사용합니다.

Smaller(y1,x2) OR Smaller(y2,x1)

이제 처리할 새 절을 정의하겠습니다.

클래스 a, b 및 구간 c, d의 각 쌍에 대해 (cin a, d in b)

G_{c,d} = (Not(V_ac) OR Not(V_bd) OR Smaller(y_ac,x_bd) OR Smaller(y_bd,x_ac))

비공식적으로 구간 경계 중 하나를 사용하지 않으면 절이 충족되고 완료됩니다.그렇지 않으면 둘 다 사용되므로 두 구간 사이에 중복이 없는지 확인해야 합니다.
이렇게 하면 두 c, d가 모두 "선택"되어 있으면 중복되지 않으며, 각 구간 쌍에 대해서도 마찬가지입니다.

이제 최종 공식을 만들어 보십시오.

F = F1 AND {G_{c,d} | for each c,d}

이 공식은 다음을 보장합니다.

1. 각 클래스에 대해 적어도 하나의 간격이 선택되었습니다.
2. 각 두 구간 c,d - c와 d를 모두 선택하면 서로 겹치지 않습니다.

작은 노트:이 공식을 사용하면 각 클래스에서 1개 이상의 구간을 선택할 수 있지만, t>1개의 구간이 있는 솔루션이 있을 경우 솔루션의 정확도를 변경하지 않고도 t-1을 쉽게 제거할 수 있습니다.

마지막으로, 선택된 구간은 우리가 정의한 부울 변수 V_ij입니다.

---

예:

Alebgra = {(1,3),(3,5),(4,6)} Calculus = {(1,4),(2,5)}

F를 정의합니다.

F1 = (V1,1 OR V1,2 OR V1,3) AND (V2,1 OR V2,2)

G를 정의합니다.

G{A1,C1} = Not(V1,1) OR Not(V2,1) OR  4 <= 1 OR 3 <= 1 //clause for A(1,3) C(1,4)
         = Not(V1,1) OR Not(V2,1) OR false = 
         = Not(V1,1) OR Not(V2,1)
G{A1,C2} = Not(V1,1) OR Not(V2,2) OR  3 <= 2 OR 5 <= 1 // clause for A(1,3) C(2,5)
         = Not(V1,1) OR Not(V2,2) OR false = 
         = Not(V1,1) OR Not(V2,2)
G{A2,C1} = Not(V1,2) OR Not(V2,1) OR  5 <= 1 OR 4 <= 3 //clause for A(3,5) C(1,4)
         = Not(V1,2) OR Not(V2,1) OR false = 
         = Not(V1,2) OR Not(V2,1)
G{A2,C2} = Not(V1,2) OR Not(V2,2) OR  5 <= 2 OR 5 <= 3 // clause for A(3,5) C(2,5)
         = Not(V1,2) OR Not(V2,2) OR false = 
         = Not(V1,2) OR Not(V2,2)
G{A3,C1} = Not(V1,3) OR Not(V2,1) OR  4 <= 4 OR 6 <= 1 //clause for A(4,6) C(1,4)
         = Not(V1,3) OR Not(V2,1) OR true= 
         = true
G{A3,C2} = Not(V1,3) OR Not(V2,2) OR  6 <= 2 OR 5 <= 4 // clause for A(4,6) C(2,5)
         = Not(V1,3) OR Not(V2,2) OR false = 
         = Not(V1,3) OR Not(V2,2)

이제 최종 공식을 보여드릴 수 있습니다.

    F = (V1,1 OR V1,2 OR V1,3) AND (V2,1 OR V2,2) 
        AND  Not(V1,1) OR Not(V2,1) AND Not(V1,1) OR Not(V2,2)
        AND  Not(V1,2) OR Not(V2,1) AND Not(V1,2) OR Not(V2,2)
        AND  true AND Not(V1,3) OR Not(V2,2)

위의 내용은 다음과 같은 경우에만 충족됩니다.

V1,1 = false
V1,2 = false
V1,3 = true
V2,1 = true
V2,2 = false

그리고 그것은 일정을 나타냅니다.원하는 대로 대수=(4,6); 미적분=(1,4).

---

공식에 대한 상수로 매우 쉽게 계산할 수 있으며, 그러한 상수의 다항식 수가 있습니다.

언급URL : https://stackoverflow.com/questions/28983729/class-scheduling-to-boolean-satisfiability-polynomial-time-reduction