1
2D의 점 집합이 있습니다. 쌍 사이의 거리 총계가 최대가되도록 그러한 점 쌍을 만들 수있는 알고리즘이 필요합니다.가장 먼 지점의 최적 쌍
동적 프로그래밍, 욕심 많은 접근 방식이 작동하지 않는다고 생각합니다. 선형 프로그래밍 또는 헝가리 알 고를 사용할 수 있습니까? 또는 다른 어떤?
A
답변
1
정수 선형 프로그래밍을 사용할 수 있습니다. 다음은 예시적인 제형은 :
가 distrinct 점 i 및 j 각 순서화 쌍 (즉 같은 i<j) i 및 j 함께 그룹화 점 IFF x[ij]=1위한 이진 변수 x[ij] 소개.
d[ij] (i<j)의 모든 거리를 계산하십시오.
각 점이 정확히 한 쌍으로되어있는 제약 조건 (예 : forall j, sum_[i<j] x[ij] = 1)에 따라 sum_[i<j] d[ij]*x[ij]을 최대화하는 것이 목적입니다.
이 점은 3d 점에서도 작동합니다. 두 점 사이의 거리 만 있으면됩니다.
+0
감사합니다. 선생님, 선형 프로그래밍의 경우 알고리즘의 복잡도는 적어도 O (n * n)입니다. 이 할당 문제로서, 헝가리어 알고리즘의 lil 수정은 O (N)의 문제를 해결할 수 있습니다. – Prince
+0
복잡성 분석에 동의하지 않습니다. 정수형 선형 프로그래밍은 분명히 다항식이 아닙니다. 나는 이것을 위해 헝가리 알고리즘을 사용할 수 있다고 생각하지 않는다. 그래프는 이원적이지 않다. 그것은 (가중치가있는) 최대 완전 매칭 알고리즘처럼 보입니다. Edmond의 알고리즘 : https://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm (특히 참조 번호 10은 정확히 원하는 것으로 보입니다). –
헝가리 방식을 어떻게 적용 할 수 있는지 설명해 주시겠습니까? 나는 그것을 보지 않는다. 호기심에서 벗어나 : 해결하려는 것은 무엇입니까? – Ali
문제는 정수형 선형 프로그램으로 공식화 될 수 있지만 성능은'O (exp (N)) '가됩니다. – Ali
@OP 다항식 알고리즘에 대한 강력한 이유가없는 한, IP는 잘 동작해야합니다. 이 문제를 여러 번 극단적으로 해결해야합니까? 휴리스틱 스를 사용할 수 있습니까? – raoulcousins