제약 조건을 가진 이진 순열 생성

Question

의사 스케줄링 응용 프로그램을 작성 중입니다. cplex/lindo와 같은 선형 프로그래밍 및 솔버를 사용하여 모델을 해결하고 있습니다. 몇 가지 모델링 제한으로 인해 야간 교대조를위한 바이너리 패턴을 생성해야합니다.

일반적으로 우리는 한 달 일정을 생성하므로 야간 근무를 위해 30 일 동안 패턴을 생성해야한다고 생각해보십시오.

야간 근무에는 야간 근무가 계속되는 경우 의사가 다음 5 일 동안 일할 수없는 것과 같은 제약이 있습니다. 따라서 제한은 몇 가지 예입니다.

111000001111100000111110000011 Valid 
111000001100000000111110000011 Valid 
111010001111101000111110000011 Invalid 

일부 정의 된 값보다 작은 연속적인 것들의 수 시작 전 간단한 알고리즘을 시도 일부 규정치 등

우선 미만이어야되어야 패턴들의 수와 같은 다른 제약들이있다 형식 0을 사용하고 비트 연산자를 사용하여 다음 순열을 얻고 다음 순열을 확인하고 유효하지 않으면 모든 순열을 검사하여 다음 순열을 얻고 유효하지 않은 패턴을 무시합니다. 이 패턴은 길이가 30 비트이므로 (2 = 1073741824) 패턴 수가 너무 많아 내 간단한 알고리즘을 검사하지 않습니다. 나는 모든 유효한 패턴을 발견하는 데 24 시간 이상이 걸릴 것으로 생각합니다.

이제 내 질문에 내가 시간을 효율적으로 적용 제약의 모든 순열을 찾아 주어진 문제에 대한 사용하여야한다 알고리즘

1. 은?

2. 이 문제는 정확한 커버 문제입니까? 내가 겪고있는 문제에 대한 링크를 춤처럼 적용 할 수 있습니까?

3. 이 문제에 대해 제안하는 해결책에 대한 링크를 제공하십시오.

Answer 1

나는 매우 좋은 해결책이 발견했다 "컴퓨터 프로그래밍의 예술 - 볼륨 4A - 조합 적 알고리즘, 도널드 크 누스에 의해 제 1 부"섹션 "7.2.1.2 알고리즘 G (일반 순열 생성기) 그것에서 저자. 기술을 설명합니다 원치 않는 블록을 무시합니다. 실현 가능한 영역의 트리 증분 세대와 알고리즘을 구현하고 모든 infeasible 경로를 우회합니다. 예를 들어 노드 0 값으로 시작하는 것과 같은 방식으로 구현할 예정이 노드는 두 자녀 0과 1 그리고 모든 노드는 새로운 자식 노드가 추가 될 때마다 자식 0과 1을가집니다. 우리는 제약 조건을 준수하지 못하면 제약 조건 세트를 검사합니다. 자식 노드를 추가하지 마십시오. 예를 들어 알고리즘이 레벨 5에서 ​​노드를 추가하려고한다면 레벨 5에서 ​​결과 문자열은 11101이고 11101 끝의 야간 이동 제한 "101"은 야간 근무 규칙을 준수하지 않고 값 1의 레벨 5 노드를 추가하지 않습니다. 루트 노드가있을 때까지 자식 노드를 계속 추가합니다. 그래서 결국 우리는 불필요한 블록을 건너 뛰기 때문에 가능한 영역 만 가질 것입니다. 이 방법으로 나는 불가능한 영역을 결코 만지지 않을 것입니다.