NP 완전하다고 의심되는이 문제를 나타내는 모델을 찾으십시오.

Question

(NDA 문제를 피하기 위해이 질문의 세부 사항을 변경했습니다. 문자 그대로 취하면 더 나은 방법이 있습니다. 이 이론적 회사를 운영하십시오.)

회사 A가 제조하는 총 1000 개의 제품 중 200 개의 다른 제품을 저장하고 분배 할 수있는웨어 하우스 그룹이 있습니다. 각 창고에는 200 개의 제품이 재고되어 있으며, 주문 된 재고가 보유하고있는 재고로 채워집니다.

도전 과제는 각 창고가 자급 자족해야한다는 것입니다. 창고에 지정된 임의의 수의 제품 (일반적으로 5-10)에 대한 주문이 있습니다. 그런 다음 창고는 주문에 필요한 제품을 포장하고 함께 배송합니다. 창고에서 사용할 수없는 품목의 경우 주문을 발송하기 전에 품목을 창고에 개별적으로 인도해야합니다.

그래서 문제는 가능한 한 많은 수의 주문을 포장하고 개별 품목을 주문할 필요없이 최상의 창고/제품 구성을 결정하는 데 있습니다.

예를 들어

(스타킹 5 제품 라인의 수 사용하는 제품 편지로 표현 각, 창고) :

Warehouse 1: [A, B, C, D, E] 
Warehouse 2: [A, D, F, G, H] 

Order: [A, C, D] -> Warehouse 1 
Order: [A, D, H] -> Warehouse 2 
Order: [A, B, E, F] -> Warehouse 1 (+1 separately ordered) 
Order: [A, D, E, F] -> Warehouse 2 (+1 separately ordered) 

목표는 미래에 개별적으로 주문한 제품의 수를 최소화하기 위해 기록 데이터를 사용하는 것입니다. 창고가 특정 방식으로 설정되면 소프트웨어는 최소한의 오버 헤드로 주문을 처리 할 수있는 창고를 결정합니다.

이것은 즉시 기계 학습 스타일 문제로 나를 공격합니다. 그것은 잘 알려진 특정 NP-Complete 문제의 조합처럼 보이지만, 그 중 어느 것도 제대로 적합하지는 않습니다.

이 유형의 문제를 나타내는 모델이 있습니까? 만약 내가 제대로 이해하고

Answer 1

, 당신은 문제를 분리해야합니다 :

• 각 창고
• 가 첫 번째 문제에 대한 주문

최선의 창고를 얻기 미리 구매해야하는지 예측, 나는 netflix prize을 가리킨다. 이것은 거의 같은 문제 였고, 훌륭한 해결책이 제시되었다. (내 데이터 마이닝 핸드북이 집에 있는데 정확한 키워드를 Google에 기억하지 못합니다. 미안합니다. "데이터 마이닝 시간 시리즈"로 시도하십시오.)

둘째로, 이것은 프롤로그의 문제입니다., 얻을 수있는 규칙을 확인 이미 0

에 제품을 소유하기위한 비용을 설정 고객

에 근접 나도 몰라위한

• 별도로
• 이 비용을 설정 항목을 주문에 대한 비용을 설정 제품은 : 당신이 그것을이없는 경우 모든 제품 얻을 수있는 규칙을 확인
• 을 할 경우 그것을 얻을, 그것을 구입 :이 규칙의 비용을 얻을
• 위의 규칙, foreach는 제품을
• Prolog에게 부드럽게 해결책을 물어보십시오. 그것이 충분하지 않다면, 더 많이 물어보십시오.

프롤로그를 사용하고 싶지 않다면 거기에 몇 가지 제약 라이브러리가 있습니다. 그냥 구글 "제약 라이브러리 <insert your programming language here" "

Answer 2

종종 첫 번째 부분 (함께 자주 주문되는 항목)은 공동 발생 문제로 알려져 있으며 데이터 마이닝 관련 문헌의 큰 부분을 차지합니다. (내 기억은 문제가 NP에 있지만 아주 좋은 근사 알고리즘이 있다는 것입니다.)

만족스러운 자료가 있으면 자료를 창고에 할당해야합니다. 이것은 세트 커버링 문제와 비슷하지만 완전히 동일하지는 않습니다. 이 문제는 NP 하드입니다.