내가 해결하기 위해 노력하고 있어요 문제는 :최소 영역 기하학적 커버
는 서클을 중심으로 할 수있는 평면과 필요 N 라인 세그먼트의 세트 M 포인트의 집합을 감안할 때 원으로 덮여 있다면 선분에 대한 최소 면적 원 커버를 찾으십시오. 즉, 모든 N 개의 선분이 덮여 서클의 전체 면적이 최소화되도록 원과 중심 (M 점에서 선택)의 반지름을 찾습니다.
선 세그먼트는 원의 바깥 쪽이 아닌 경우 덮여 있습니다.
논문이나 코드 또는 근사 알고리즘에 대한 지침은 유용 할 것입니다.
편집 : 그냥 선분이 가장 잘 여러 개의 원이 적용된다 (끝으로 이동) 원래의 접근 방식은 아마도 사건을 커버하지 않는 것을 깨달았다. 그래서 나는 그것이 원의 경계에 선 세그먼트를 자르고, 대신 선분의 포인트를 반복하는 것이 좋습니다 생각 :
주요 아이디어는 어떤 경우 든 필요한 것을 계속하는 것입니다. 겹치는 서클은 어떻게 계산됩니까? 영역이 합쳐 지거나 병합됩니까? 나중에 반복 한 단계로 돌아갈 때, 비용 휴리스틱 어떤 종류의 아마
원래 제안했다 ... 결과를 개선 할 수있을 것입니다 :
감사합니다. 나는 그것을 시도 할 것이다. 욕심 많은 접근 방식을 사용하여 최소 면적 커버로 한 번에 각 선 세그먼트를 덮는 방법을 생각해 냈습니다.가장 작은 원으로 덮기 시작하고 선분이 완전히 덮일 때까지 반지름에서 작업하십시오. 그런 다음 결과의 합집합을 취하십시오. 하지만 겹치는 서클에서는 작동하지 않을 수 있습니다. – LostInTheFrequencyDomain
질문에 답하기 : 중복 된 원이 비용으로 합산됩니다. – LostInTheFrequencyDomain
이것에 대해 좀 더 생각한 후에, 어떤 형태의 *가 최적의 솔루션 (가능한 한 빨리 다루기)에 필요한 것일 수 있습니다. 제안 된 휴리스틱이 작동하지 않는 예제를 구성하는 것이 상대적으로 쉽습니다 잘. 이를 위해 나머지 비용에 대한 하한을 계산하는 것이 유용 할 수 있습니다 .... –
귀하의 문제는 NP 하드이므로 근사 알고리즘을 해결해야합니다. –
제안 된 발견 적 방법 - 모든 선분 끝점의 중심에 가장 가까운 가능한 중심 집합에서 점을 찾아서 중심으로 사용하십시오. 원의 반지름은 그 중심에서 가장 먼 선분 끝점까지의 거리입니다. 대부분의 경우를 다루지 만 항상 최적의 답을 줄 수 있음을 증명할 수는 없습니다. 특히, 다른 모든 선들과 정말 멀리 떨어져있는 한 선분이 있으면, 사물을 상당히 왜곡시킬 수 있습니다. – twalberg
해결책을 모르겠습니다. 서클의 가능한 센터가 이미 제공됩니다. 그 센터에 서클을 배치하고 세그먼트가 커버되도록 반경을 선택하고 싶습니다. – LostInTheFrequencyDomain