두 세트의 최대 거리를 최소화하는 알고리즘을 찾으십시오. Greedy 알고리즘보다 우수합니다.

Question

여기 흥미로운하지만 복잡한 문제가 있습니다.

두 세트의 점이 있다고 가정합니다. 하나의 집합 A는 정규 1D 또는 3D 그리드처럼 일부 공간 격자에 점을 포함합니다. 다른 세트 B는 임의로 간격을두고 공간 격자와 동일한 크기의 점을 포함합니다. 수학적으로, 우리는 두 세트를 정렬하고 A와 B 사이의 거리에 대해 대응하는 행렬을 구성 할 수 있습니다. 예를 들어, A (i, j)는 B의 A와 j의 거리를 나타낼 수 있습니다.

어떤 순서가 주어지면 행렬이 생깁니다. 그런 다음 행렬의 대각선 요소 (i, i)는 A의 점 i와 B의 점 i 사이의 거리입니다. 문제는 최대 거리가 가능한 한 작은 재 배열/색인 생성을 찾는 방법입니다. 행렬 형식에서 가능한 큰 작은 대각선 요소를 어떻게 재정렬/색인 생성을 찾을 수 있을까요? 자신의

주 :

1. 가정하자 세트 A는 행렬의 행에 대응하고, 설정 B 행렬의 열이다. 그런 다음 행렬 재정렬은 행/열 순열을 수행한다는 것을 의미합니다. 그러므로, 우리의 문제는 가장 큰 대각 요소를 최소화하기위한 좋은 순열을 찾는 것과 같습니다.

2. 욕심 많은 알고리즘이 선택 될 수 있습니다. 하지만 가장 큰 대각선 요소를 최소화하는 이상적인 완벽한 재정렬을 찾으려고합니다.

Answer 1

당신이 언급되는 재정렬는 본질적으로 다른 세트의 각 지점에 가장 가까운을 찾으려고 노력 대응 문제 즉이다. 욕심 많은 알고리즘은 정상적으로 작동합니다. 찾고있는 거리는 일반적으로 Hausdorff distance이라고합니다.