업계에서는 직물, 목재, 금속 등 소재의 가장 효율적인 사용을 계산해야하는 경우가 종종 있습니다. 따라서 시작점은 X 모양입니다. 주어진 치수, 다각형 및/또는 곡선으로 만들어지고, 목표는 주어진 치수의 다른 다각형입니다.표면의 최대 모양 중첩
현재 많은 CAM 제품군이 이것을 구현한다고 가정하지만, 내부 또는 내부 메모리 사용 경험이없는 경우 공간의 가장 효율적인 사용을 찾기 위해 어떤 종류의 계산 알고리즘이 사용됩니까? 누군가가 저를이 주제를 다루는 책이나 다른 참고 자료로 안내 할 수 있습니까?
, 나는 별도의 대답에 여기 내 연구 결과를 덤프하기로 결정했다.
이것은 실제로 포장 문제이며, 더 정확하게 말하면 중첩 문제입니다. 문제는 수학적으로 NP 하드이므로 현재 사용중인 알고리즘은 경험적 접근법입니다. 사소한 문제 세트를 제외하고 선형 시간에 문제를 해결할 수있는 솔루션이없는 것 같습니다. 재료 사용률이 좋은 솔루션을 얻으려면 복잡한 하드웨어 문제를 해결하는 데 몇 분에서 몇 시간이 걸립니다. 셰이프의 중첩 기능을 제공하는 수 많은 상용 소프트웨어 솔루션이 있지만 오픈 소스 솔루션을 찾을 수 없었기 때문에 알고리즘이 실제로 구현 된 것을 볼 수있는 실제 사례는 없습니다.
코펜하겐 대학의 Benny Kjær Nielsen (Nielsen)이 작성한 논문에서 역사적인 해결 방법으로 중첩 및 스트립 중첩 문제에 대한 훌륭한 설명을 찾을 수 있습니다.
일반적인 접근법은 최상의 중첩 솔루션을 찾기 위해 여러 알려진 알고리즘을 혼합하여 사용하는 것으로 보입니다. 이러한 알고리즘은 다음과 같습니다 (가이드 /이 Iterated) 지역 검색, 빠른 네이버 검색 에는-맞춤 다각형 및 싸움이 치열 추론을 기반으로하지 않습니다. 알고리즘의 작동 방식에 대한 사진과 함께이 주제에 대한 훌륭한 논문을 찾았습니다. 또한 다른 소프트웨어 구현의 벤치 마크도있었습니다. 이 논문은 S. Umetani et al (Umetani)에 의한 2006 년 국제 심포지엄에서 발표되었다.이루어진 하이브리드 소둔을 및 유전 알고리즘을 시뮬레이트
비교적 새로운 아마도 현재까지 가장 좋은 방법은 하이브리드 유전자 알고리즘 (HGA)를 기반으로하여 설명되었지만 Wu Qingming 외 우한 대학교 (Quanming). 그들은 MatLab에서 Visual Studio, SQL 데이터베이스 및 GAOT (genetic algorithm optimization toolbox)를 사용하여이를 구현했습니다.
2 차원 공간뿐만 아니라 3 차원 공간에 대해서도 정의 된 다양한 문제와 연구가있는 패킹의 유명한 컴퓨터 과학 영역을 말하는 것입니다.
정의 된 문제에 사용할 수있는 그물에는 상당한 재료가 있지만 검색 할 문제의 이름을 알 필요가 없다는 것을 알기 위해 찾으십시오.
일부 패키지는 경험적 appraoch (필자가 생각하는 것)를 채택 할 수도 있고 일부는 절대적인 정답을 얻기 위해 모든 가능성을 계산할 수있는 길이로 갈 수도 있습니다. 앤드류는 그의 대답에 올바른 방향으로 나를 지적 나를 위해 문제를 명명 한 후
는
Umetani의 링크 된 종이는 이제 404입니다. 제목은 무엇 때문에 사람들이 Google에서 읽을 수 있습니까? –
제목은 실제로 링크 위에 있습니다. :) 깨진 링크를 업데이트했습니다. – Fuu