1
안녕하세요. 다른 n 개의 객체와 함께 주어진 모양의 알고리즘을 찾고 있습니다. 빈 (bin) 패킹 알고리즘을 보았지만 주어진 컨테이너 안에 모든 객체를 완벽하게 맞추려고합니다. 내 경우 엔 다음과 같습니다 
2d에서 n 개의 다른 객체로 도형을 덮는 알고리즘
누군가가 나를 도울 수 있거나 나를 인도 할 수있는 경우이 문제에 대한 정보를 얻을 수있는 곳이 좋습니다.
A
답변
1
부분적으로 질문에 대답하려면 NP-이 문제이므로 Partition 문제의 기하학적 일반화 문제입니다. 목록 정수 {a_1,...,a_n}의 및 해당 문제 인스턴스 {1,...,n} 각 i 및 타겟 치수
1 * a_i
의 n 사각형을 사용하여 생성 될 수
S := (a_1 + ... + a_n)/2
taget 합 주어 크기 영역
2 * S.
더 작은 직사각형은 이 예는 Partition의 인스턴스가 동일한 총량의 두 개의 하위 집합으로 분할하는 것을 허용하는 경우에만 큰 직사각형에 맞습니다.
1
이 문제는 세트 커버 문제에서 매우 쉽게 줄일 수 있습니다. link
이러한 그림이 그려지는 가상의 그리드 평면을 고려하십시오. 이제 큰 그림에서 격자 사각형의 우주 집합 U을 구성하십시오.
이제 작은 그림의 각각에 대해 U의 부분 집합 인 유사한 세트가 생성됩니다. U에없는 이러한 요소에서 요소를 제거하십시오.
이제 방금 만든 n 개의 하위 집합을 사용하여 U에 대한 집합 표지가 필요합니다. 가장 작은 세트 커버를 찾고 있다면 NP- 완료.
세트 커버 문제에 대한 대략적인 해결책을 선택하실 수 있습니다.
모양과 객체에 대해 알려진 어떤관련 문제
- 1. 거칠기 감소 : 도형을 매끄럽게하는 알고리즘
- 2. 알고리즘 - 주어진 사각형 영역을 덮는 사각형의 수를 찾으십시오.
- 3. Dubois를 사용하여 2D에서 3D로 변환 Anaglyph 알고리즘
- 4. 전처리 n 개의 * 로그를 사용하여 트리 (N) 알고리즘
- 5. MapBox : 도형을 제거하고 다른 도형을 그리는 방법?
- 6. n 개의 공백에있는 4 개의 객체의 순열에 대한 재귀 알고리즘
- 7. O (2^n * n) 배낭 알고리즘
- 8. O (N) 정렬 알고리즘
- 9. UIAlertView를 다른 뷰로 덮는 방법?
- 10. 충돌 탐지를위한 O (n^log n) 알고리즘
- 11. 거리의 n * n 행렬에 대한 질문 알고리즘
- 12. n 차원 매칭 알고리즘
- 13. 다항식을 power n 알고리즘
- 14. O (n) 정렬 알고리즘
- 15. 2^n 복잡도 알고리즘
- 16. n 점을 등거리에 배치하기위한 알고리즘
- 17. 두 개의 다른 객체로 콤보 박스 채우기
- 18. n 개의 객체와 javascript를 결합합니다.
- 19. 동일한 다중 사각형을 사용하여 직선형 폴리곤을 덮는 알고리즘
- 20. 특정 알고리즘 정렬 N 소자
- 21. N 개의 문자열에서 공통 부분 문자열을 찾는 알고리즘
- 22. 좌표를 얻는 N * N 여왕 알고리즘
- 23. n 개의 1 비트 수에 대한 덧셈 알고리즘
- 24. O (fib n) 복잡도 알고리즘?
- 25. n 차원 보간법 C++ 알고리즘
- 26. 트리에서 가장 큰 n 개의 노드를 찾는 알고리즘
- 27. 사각형을 n 개의 작은 사각형으로 분할하고 각 중심을 계산하는 알고리즘
- 28. 알고리즘 : n 개의 난수의 합계가 정수 K와 같은지 확인하십시오.
- 29. N 개의 정렬되지 않은 그룹으로 부분 정렬하는 효율적인 알고리즘
- 30. 알고리즘 : 마지막 n 개의 고유 번호를 순서대로 기억하십시오.
? 예 : 그들은 모두 볼록합니까? – Henrik
미안하지만, 당신이 볼록 함을 의미하는 것을 이해하지 못합니다, 미안하지만이 문제에 대해서는별로 좋지 않습니다. 모양은 html5 캔버스로 그려져 원, 사각형 등이 될 수 있습니다. 다른 모든 객체는 직사각형이 될 것입니다. – Alex