어제 제가 답변을 찾을 수 없다는 질문이 떠 올랐습니다.유전 알고리즘이 다른 동등한 크기의 원으로 채우기
우리는 임의의 크기의 직사각형을 가지고 있으며 반경이 다른 원도 있습니다. 각 원의 수가 제한되어 있습니다. 각 원에는 지정된 비용이 있습니다. 우리는 가장 작은 비용에 접근하여 그 사각형으로 직사각형을 완전히 채우고 싶었습니다.
이제 유전자 알고리즘을 사용하여이 문제를 해결하고 싶지만 웹에서 어떤 문제도 발견되지는 않을 것입니다. 이는 제 문제와 동일합니다.
아무도 아이디어가 있습니까?
문제는 Knapsack 문제와 관련이 있습니다. 최대 값을 갖는 항목 그룹을 선택하려는 가중치 W 및 값 V가있는 N 개의 항목 집합 중 가중치의 합계가 일부 제한값보다 낮게 유지됩니다 .
그러나 문제는 더 복잡합니다. 무게 제한의 평가는 단순한 추가가 아니고 서클의 배열에 달려 있기 때문입니다. 나는 이것으로 해결할 또 다른 NP 어려운 문제라고 생각한다. 가능한 경우 알려주는 제한 조건에 대한 빠른 근사값을 찾아야합니다 (가끔씩 가능할 수도 있음을 알려줄 수도 있음).
컨테이너 내부의 객체 배열은 패킹 문제로 설명 될 수 있습니다. circle packing 및 관련 문헌을 살펴볼 수 있습니다. 간단한 휴식은 직사각형을 기반으로 할 수도 있습니다. 서클을 직사각형으로 취급하는 경우 사용할 수있는 직사각형 패킹을위한 빠른 방법이 있습니다. 서클의 크기가 매우 다른 경우에는 휴식 시간이 길어질 수 있습니다.
원 포장에 대해 읽었지만 도움이되지 않습니다. 제 문제에는 빈 공간이 없어야합니다. 그러나 포장에서 겹치지 않아 빈 공간이 생길 수 있습니다. – saman
나는 귀하의 문제가 포장 문제가 아닌 커버링 문제가된다는 것을 알고 있습니다. 이것에 대한 좋은 정보를 찾기가 어렵습니다. 예를 들어 많은 문제를 다룹니다. 정사각형을 덮는 균질 동그라미의 최소 반경이 있습니다. 주어진 서클의 수가 사각형을 채울 수 있는지 평가하는 데 좋은 페이지를 찾지 못했습니다. 직관적으로, 나는 그것이 NP 완전한 문제라고 말할 것이다. – Andreas
감사합니다 Andrease. 귀하의 정보는 매우 유용했습니다. – saman