2^n 조합에서 가장 좋은 순서 찾기

Question

제조 환경에서 사용할 간단한 학교용 소프트웨어를 개발해야합니다.

이

는 시나리오 :

내가 크기의 목록을 제공하고 있습니다 - 예를 들어 내가 24 "X 30"보드, 30 "X 30", 30 "의 X가 각각의 크기는, 보드를 반영 48 "등등. 이 보드는 원자재를 자르는 과정의 부산물입니다.

원료는 두 가지 유형의 보드 크기 (60 "x 120"및 48 "x 96")로 제공됩니다.

그들은 원료에서 판재를 자르기위한 최선의 방법을 알고 싶어합니다. "가장 좋은"방법은 원료와 잔류 물이 가장 적은 방법으로 정의됩니다. 그들은 또한 사용될 원재료의 양을 알고 싶어합니다. 예를 들어 30 "60"x 120 "의 보드와 48"x 96 "3의 보드.

보드를 수평 또는 수직으로 절단 할 수 있습니다. 즉, 24 "x 30"을 24 "x 30"또는 30 "x 24"로자를 수 있습니다.

전체적으로 (같은 크기 일 수도있는) 총 50 개의 보드가 제공되는 경우 2^50 가지 조합을 사용할 수 있습니다. 이것은 수천 개의 다른 소프트웨어에서 소프트웨어를 실행하기 때문에 너무 길어 보입니다. 보드 크기.

누구나이 시나리오에 적합한 알고리즘을 알고 있는지 궁금합니다.

감사합니다.

Answer 1

& 패킹 문제를 절단 직사각형 2D 클래식 간단한 알고리즘은 그러나 Wang's algoritm

이며, 순수 왕의 알고리즘은 모든 상처 하나에서 모든 방법을 여행 할 경우, 즉 패턴을 최적의 단두대 절단 패턴을 생성 할 수있다 잔여 물자의 반대 가장자리에 가장자리. 그것은 많은 애플리케이션을 위해 단두대 절단 재잘는 충분 간주됩니다, 그러나 다음과 같은 일

+---------+---+ 
|   | | 
+---+-----+ | 
| |  | | 
| |  | | 
| +-----+---+ 
| |   | 
+---+---------+ 

같은 비 단두대 패턴을 생성 할 수 없습니다. 따라서 알고리즘을 고려하는 것이 좋습니다 (매우 간단하므로).

은 시뮬레이션 어닐링 기술을 기반으로 대략적인 무작위 알고리즘이있다 (자세한 설명은 비 단두대 패턴을 생성 할 수 있습니다 Simulated Annealing for VLSI Design 책 (그물에 그것을 찾을 수 없습니다)에서 찾을 수 있습니다 .

어쨌든 이러한 문제에 대한 정확한 해결책을 찾는 것은 대개 다양한 변형을 생성 및 분석하기 위해 상당한 양의 계산이 필요하기 때문에 대부분의 경우 실용적이지 못하다. 사람들은 좋은 근사/휴리스틱 알고리즘을 고수하기를 선호하지만, Wang의 알고리즘은 검색 속도를 높이는 발견 적 필터 (최적의 솔루션을 잃어 버리고 "거의"최적의 솔루션으로 대체 할 위험에 처해 있음)로 사용자 정의 할 수 있습니다.

Answer 2

가장 먼저 생각해 볼 점은 Bin Packing 알고리즘을 사용하여 팩에 주어진 원자재 중 많은 수의 보드를 사용할 수 있다는 것입니다.

Genetic Algorithm을 시도해보고 최상의 커팅 패턴을 검색 할 수도 있습니다. GA는 Bin Packing Algorithm처럼 지속적으로 효과적 일 수 있지만, GA에서 실행 시간을 정할 수는 있습니다. 예를 들어 일정 시간이 지난 후에 최상의 솔루션을 선택하십시오.

그러나 나는 공장이 동일한 크기의 재료로 배치 프로세스를 수행하는 경향이 있다고 생각하기 때문에 실제 절단 전에 실행되는 (아마도 더 느린 것은 무엇인지) 빈 포장 알고리즘을 허용하는 것이 가장 좋습니다. 일어난다.

Answer 3

이것은 어려운 문제이며 cutting stock problem과 매우 유사합니다. bin packing problem도 참조하십시오.