NP 완료 문제가 있습니까?

Question

다음과 같은 문제가 NP 완료인지 여부 또는 단순한 무차별 강제 결합 검사보다 실제적으로 더 좋고/더 쉬운 해결책이 있는지를 확인하기를 바랍니다.

우리 소프트웨어에는 일종의 자원 할당 문제가 있는데 예제로 설명하겠습니다.

하루 교대 근무 중에 4 명이 근무해야한다고 가정 해 봅니다. 이 숫자와 그것이 "day-shift"라는 사실이 우리 데이터베이스에 기록됩니다.

그러나 우리는 누군가 그 장소를 채울 필요가 없으며 청구서에 맞게 몇 가지 요구 사항을 채워야합니다.

이들 중 4 분의 2는 간호사이어야하며 그 중 1 분은 의사 여야합니다.

의사 중 한 명이 특정 팀의 일원이기도합니다.

이

일 교대 : 4
      한 의사
      한 의사, A 팀
      1에서 작업해야

그래서 우리는 정보의 집합을 간호사

위의 내용은 문제가 아닙니다. 문제는 우리가 사람들을 데리러 일일 근무를 시작하고 우리가 지금까지 골랐던 사람들이 실제로 기준을 채울 수 있는지 알아 내려고 할 때입니다.

예를 들어 제임스와 어슐러가 의사이고 존과 메리가 간호사 인 제임스, 존, 어슐러와 메리를 선택한다고합시다.

어슐러는 또한 우리가 법안을 맞게하려고 순서에 따라, 이제

팀 A. 작동, 우리는 우리가 서로 다른 조합을 시도 시작하지 않는 한 우리가 올바른 사람, 또는하지를 가지고 추론 끝낼 수 있습니다.

예를 들어, 목록을 내려 우르술라를 먼저 선택하면 "1 의사"기준과 일치시킬 수 있습니다. 그런 다음 우리는 James에게 간다. 그리고 A 팀에서 일하지 않기 때문에 "A doctor에서 일해야하는 1 명의 의사"에 대한 다른 기준은 그를 채울 수 없다는 것을 알게된다. 다른 두 사람은 간호사이기 때문에 그 기준에 맞지 않습니다.

그래서 우리는 제임스를 역 추적하고 첫 번째로 시도해 봅니다. 그리고 그는 또한 첫 번째 기준에 부합 할 수 있습니다. 그런 다음 어슐러는 그 팀을 필요로하는 기준에 부합 할 수 있습니다.

우리가 모두 시도해 볼 때까지 다른 조합을 시도해야하므로 문제가 발생합니다.이 경우 헤드가 작동하는 총 수를 계산 한 경우에도 아직 채워지지 않은 기준이 있습니다. 필요한 총 헤드 수와 같거나, 적절한 조합을 찾았습니다.

이것이 유일한 해결책입니까, 더 좋은 사람이 될 수 있습니까?

---

편집 : 일부 설명.

이 질문에 대한 의견은이 소수의 사람들과 함께 우리는 무차별 대항력으로 나가야한다는 것을 언급하며, 우리가 할 수있는 일이라고 생각합니다. 같은 차선에서 정렬 최적화 데이터 크기가 작 으면 초기 오버 헤드가 적은 다른 정렬 알고리즘을 선택합니다.

그러나 문제는 이것이 명단 계획 시스템의 일부라는 점입니다.이 시스템은 상당히 많은 사람들이 참여할 수 있습니다. "우리는 낮 근무일 X 명이 필요합니다"와 "우리는 이것을 가지고 있습니다 우리는이 Y 사람들과 어울려야 할 X 사람들을위한 Z 기준의 목록을 갖고 있습니다. 리더가 명단을 조정할 때 실시간으로 동일한 계산을 수행하는 데 며칠이 걸릴 것이므로 신속한 솔루션의 필요성이 제기됩니다.

기본적으로 리더는 누락 된 사람의 수를 나타내는 화면상의 실시간 합계 정보를 하루 종일 전체적으로 볼 수 있으며 몇 명의 사용자가 다양한 기준에 부합하는지 알 수 있습니다. 우리가 가진 것 외에 실제로 우리가 실제로 접한 많은 사람들. 이 디스플레이는 세미 라이브를 업데이트해야합니다. 리더가 "James가 Ursula 대신 Day Shift를 취하고 Ursula가 야간 근무를하는 경우 어떻게해야합니까?"라고 명단을 조정합니다.

지금까지 답변 한 사람들에게 커다란 감사를드립니다. 제약 조건 만족 문제는 우리가 가야 할 방식처럼 들리지만 여기서는 모든 링크와 알고리즘 이름을 자세히 살펴볼 것입니다.

이것은 I에 유래 :)를 사랑하는 이유입니다

Answer 1

당신이 가지고있는 것은 constraint satisfaction problem입니다; NP와 NP와의 관계는 일반적으로 NP이지만 종종 NP 완성이 아니기 때문에 흥미 롭습니다. 즉, 다항식 시간 솔루션을 다루기 쉽습니다.

의견에 언급 된 바와 같이 Knuth's Algorithm X을 (를) 적용 할 수있는 exact cover problem으로 공식화 될 수있는 것처럼 들릴 수 있습니다. 이 압정을 당하면 어떻게 작동하는지 알려주십시오.

Answer 2

당신은 무엇을 설명하는 '룸메이트 문제'살짝 this thesis에 설명되어 있습니다.

나를 괴롭히며 더 나은 링크를 찾고 있습니다.

편집

여기 thesis 다른 상당히 밀도를합니다.

Answer 3

너는 constraint satisfaction problem 인 것처럼 보입니다.

나는 특히 제한 전파 기술을 먼저 살펴 보았습니다. 문제를 관리 가능한 크기로 줄일 수 있습니다.

아무도 기준에 맞지 않으면 어떻게됩니까?

Answer 4

나는 대부분이 bipartite graph matching 문제를 줄이려고 노력할 것입니다. 또한 문제가 NP인지를 증명하기 위해 일반적으로 머무르는 것보다 훨씬 더 복잡합니다. 다항식 솔루션을 찾을 수 없습니다.

Answer 5

귀하의 문제가 NP가 아닌지 확실하지 않습니다. 그런 식의 냄새가 아닙니다.하지만 내가 당신이라면 가장 적은 수를 사용하여 가장 구체적인 것을 채우려는 직책에 대한 요구 사항을 주문하게 될 것입니다. 사람들은이 직위를 채울 수있게 될 것이므로 많은 것을 되돌릴 필요가 없습니다. 순수한 크 누스 네스 (Knuth-ness) 알고리즘 인 알고리즘 X와 조합해서는 안됩니다.

Answer 6

필자의 수학적 지식이 그리 좋지 않기 때문에 다른 이론에 맡기 겠지만, Cassowary/Cassowary.net 또는 NSolver와 같은 도구를 사용하여 문제를 선언적으로 제약 만족 문제로 표현한 다음 해결하는 것이 유용 할 수 있습니다. 제약

이러한 도구에서 제약 조건 전파와 결합 된 심플 렉스 방법은 솔루션 공간을 결정 론적으로 줄이기 위해 자주 사용되며 비용 함수를 고려할 때 최적 솔루션을 찾습니다. 더 큰 솔루션 공간 (지정하는 문제의 크기에 적용되지 않는 것 같음)에는 유전 알고리즘이 사용됩니다.

정확하게 기억한다면 NSolver는 Chun이 홍콩에서 작업 한 실제 간호사 문제 해결의 단순화를 샘플 코드에 포함시킵니다. 그리고 거기에 a paper on the work he did.

Answer 7

당신이 훨씬 쉬울 것 분리 몇 가지 문제를 해결해야 할 것 나에게 소리

:

- A 팀 에서 한 의사 선택 - 모든 팀 에서 다른 의사를 선택 - 간호사 2 명 선택

그래서 세 가지 독립적 인 문제가 있습니다.

명확한 설명이 필요하지만 의사 2 명 (지정된 팀에서 1 명)과 간호사 2 명 또는 지정된 팀의 의사 한 명, 간호사 두 명과 의사 또는 간호사 일 수있는 다른 사람이 있습니까?

Answer 8

몇 가지 질문 :

1. 는 제약 정확히, 또는 단지 약 (그러나 가능한 한 많이)을 만족하는 목표인가?
2. 사람이 여러 팀의 구성원 일 수 있습니까?
3. 가능한 모든 제약 조건은 무엇입니까? (예를 들어, 우리는 여러 팀의 구성원 인 의사가 필요 있을까?)

당신이 제약 정확히을 충족 할 경우에, 나는 즉, 사람이다, 점감 제약 엄격하여 주문 것 (예 : 위의 예에서 의사와 팀 A) 첫 번째을 확인해야합니다!

약이라는 제약 조건을 만족 시키려면 다른 이야기 ... 우리가 할 수없는 것을 결정하는 가중치/중요도 함수를 지정해야합니다. 정확하게 선택할 수있는 여러 가지 가능성이 있습니다.

Answer 9

제약 조건이 여러 개이거나 많으면 Drools Planner (오픈 소스, java)을 살펴보십시오.

브 루트 포스, 지점 및 바인딩과 유사한 기술이 오래 걸릴. 과 같은 결정 성 알고리즘은 가장 큰 교대를 먼저 채우고은 매우 부차적입니다. 메타 휴리스틱 스는 이것을 처리하는 아주 좋은 방법입니다.

Drools Planner의 실제 간호사 수색 사례를 자세히 살펴보십시오. "젊은 간호사는 토요일 밤에 일하고 싶지 않습니다"또는 "일부 간호사는 며칠 동안 계속 일하고 싶지 않습니다"와 같은 많은 제약 조건을 쉽게 추가 할 수 있습니다.