3 차원 공간에서 커버 설정

Question

다음 문제에 대한 알고리즘을 구성하는 데 도움이 필요합니다.

나는 "를 참조하십시오"다른 점 C 수있는 점 G의 세트가있다. C의 모든 커버 G에서 최소한의를 찾는 알고리즘을 필요 (G 반드시 C의 일부가 아닙니다).

동적 프로그래밍으로 해결해야한다고 생각합니다. 그러나 나는 어떤 해결책이나 아이디어에 열려 있습니다.

감사합니다.

편집 1 :

나는 완전히 문제를 이해하지 수 있습니다.

포인트는 지형 높이가있는 3D 표면에 있습니다. 지형은 점 사이의 특정 높이까지 올라갈 수 있으므로 점이 다른 점을 볼 수 없습니다. 직접 시선이있는 한, 거리가 무엇이든 상관없이 서로 볼 수 있습니다.

• 경우 포인트 포인트 B (C에서) 볼 수있는 (G부터) - B은 (에서 C)를 D 볼 수 가리킨 다음 을은 d입니다. 이것이 더 큰 차이를 만드는 지 확실하지 않습니다. 그래서 더 나은 전에를 사용하는 것을 금지 -

• 에만 경우B (에서 C)을 볼 수있다 (G에서) 우리는 모든 C를 커버하기 위해 를 선택해야합니다 욕심 많은 알고리즘.

새로운 정보에 비추어 다른 점이 있으면 계속 생각하십시오.

Answer 1

문제는 Set cover problem입니다. 그것은 NP 완성입니다.

나는 탐욕 로그 (n) 근사 알고리즘을 사용합니다. 그것은 매 단계마다 (C)의 최대 점수를 커버하는 (G)의 요소를 선택합니다.

---

인터넷에서 발견 된 대부분의 강의 노트에는 위에서 설명한 근사 알고리즘 만 표시됩니다.

Lund & Yannakakis (1994)에 의해 입증 된 것처럼 위의 알고리즘보다 훨씬 더 잘 수행하기가 어렵습니다. 위키 백과 문서에서 참조를 찾을 수 있습니다.

집합 커버 문제의 등가 정수 선형 문제 공식을 사용할 수도 있습니다. 그러나 다시 log (n) 근사 알고리즘을 얻습니다.

다른 근사치가 있지만 대부분은 연구 논문이므로 설명이 이해하기 쉽지 않습니다. 당신은 그들이 단지 문제가 NP-완료되거나 알려진 문제 TI의 변형 인 경우 알 수있는 엄지 손가락의 규칙이있는 경우 나도 몰라

---

을 "근사 알고리즘 커버 세트"인터넷 검색을 찾을 수있는 동적 프로그래밍을 사용하는 솔루션이 존재합니다. 하지만 질문을 게시했습니다 here. 사건에 대해

---

때만 ( G에서) 볼 수 B이 때만 모든 정지하기 때문에, 그리 디 알고리즘은 어쨌든 을 선택할 것이다 ( C)에서 포인트는 입니다. 알고리즘이 포인트를 선택하는 순서는 솔루션을 변경하지 않습니다.

---

가 실제로 그 경우 점 점을 볼 수있다 ( G)에서 B ( C부터) - B은 ( C 부터) D을 볼 수 있고 포인트 , 그러면 d을 볼 수 있지만이 문제는 모델 번호 planar graph으로 모델화 할 수 없습니다. 평면 그래프는 문제에 대한 더 좋은 근사 알고리즘을 가지고 있습니다. 그리 디 알고리즘보다 좋습니다.