다음은이 예상치 못한 복잡한 문제에 대한 결정적인 또는 구체적 / 우수한 공격으로 제시되지는 않았지만 과학적 / 이론적 각도 / 일반적인 연구는 아직까지 다루지 않았다.

1 ^일 이 개 일반 영역 / 공지 된 바와 같이 분류된다 “빈 포장” 이것은 2 차원 경우입니다. 수세기 동안 열린 문제 였고 Hales의 컴퓨터 증명으로 “최근에”해결 된 구체 포장에 대한 케플러 의 3D 사례와 같은 수학의 유명한 증거가 있습니다 . 업계에서 매일 사용되는 2d 사례의 예는 칩 레이아웃을 최적화하는 것입니다. 분명히 이것은 문제와 다르지만 이러한 유형의 문제의 복잡성을 나타낼 수 있습니다. 예를 들어 2d 사례가 3d 사례보다 단순하다는 요구 / 지시가있는 이론은없는 것 같습니다. 또한 단순한 직사각형 경계가 다각형 경계 이외의 솔루션을 단순화하는 데 반드시 도움이되는 것은 아닙니다.

계산 규칙 등의 그리드에 배치하는 등의 문제 설명에 “정규 타일링”의 기본 정의 / 구성표가 제공된 경우 분석 솔루션이있을 수 있습니다.이 경우 미적분 방정식을 도출하고 최적으로 찾을 수 있습니다.

문제의 조건은 (직관적으로 직관적 일 수 있음) 분석적인 최적의 솔루션으로 이어지지 않는 것 같습니다. 이것은 비행기 타일링과 관련하여 매우 유사한 일부 문제에 대해 놀라운 일이 될 수 있습니다 (이것은 몇 년 전에 유명한 결과였으며 많은 참조와 지속적인 연구가 있습니다). 결정 가능한 (해결 가능 / 분석) 문제와 결정 불가능한 문제의 주요 차이점은 바둑판 식 배열이 “정규”인지 여부입니다. 위의 문제는 “일반 별”과 관련이 있지만 “일반 타일링”과는 관련이 없습니다. 다른 현재 답변은 일종의 규칙적인 타일링 또는 순서를 가정하지만 “정규 타일링”을 정의하는 것조차 공식적으로 / 수학적으로 매우 까다로울 수 있습니다.

이와 같은 문제는 일반적으로 유전자 알고리즘에 상당히 적합합니다 . 이러한 알고리즘은 많이 개선 될 것 같지 않은 “매우 좋은”패킹을 찾을 수 있으며, 매우 독창적 인 방법을 통해 최적의 한계에 도달 할 수 있지만 (아마도 최적의 작은 오류 퍼센트 내에 있어야 함) 최적입니다.

다음은 일반적으로 직접 적용 할 수있는 참조입니다.

• 유전자 알고리즘의 사용 예. 다각형 / 제이콥 패킹을위한 유전자 알고리즘

• 기하학적 패킹 및 스케일링 문제에 대한 알고리즘
  박사 논문 / Michael Formann 1992, 92p, sec 3.6 스케일링 별 모양의 x- 모노톤 객체 p30

• 임의의 형태 / ARFATH PASHA 2003 대학원 논문 87p에 대한 기하학 빈 포장 알고리즘

• 이 스택 교환 질문도 가깝습니다. 임의의 경계 내에 임의의 다각형을 패킹합니다 . 그것은 임의의 경계를위한 것이다

답변