최소 거리를 가진 2 포인트 사이의 매핑을 찾기 위해 더 나은 알고리즘이 필요합니다.

Question

문제: 나는 두 개의 겹치는 2D 모양, a와 b를 가지고 있으며, 각 모양은 픽셀 수가 같지만 모양이 다릅니다. 모양의 일부는 겹치며 겹치지 않는 각 조각이 있습니다. 내 목표는 모든 비 초당 픽셀을 모양 A로 겹치지 않는 픽셀로 이동하는 것입니다. 각 모양의 픽셀 수는 동일하기 때문에 1-1의 매핑을 찾을 수 있어야합니다. 픽셀. 제한 사항은 이동 한 모든 픽셀로 이동하는 총 거리를 최소화하는 매핑을 찾고 싶다는 것입니다.

무차별 부대 : 이 문제를 해결하기위한 무자비한 힘 접근 방식은 분명히 문제가되지 않습니다. 왜냐하면 나는 N이 있다고 생각하는 모든 가능한 매핑의 총 거리를 계산해야하기 때문입니다! (여기서 n은 한 가지 모양으로 겹치지 않는 픽셀의 수입니다) 맵핑의 각 지점 쌍에 대해 거리를 계산하는 계산은 O (n * n!) 또는 유사한 것을 제공합니다.

역 추적 : 내가 생각할 수있는 유일한 "더 나은"솔루션은 역 추적을 사용하는 것이 었습니다. 여기서 지금까지 최소값을 추적하고 특정 매핑을 평가할 때 언제든지 최소값에 도달하거나 초과하면 계속 진행하는 것이 었습니다. 다음 매핑에. 조차도 O (n!)보다 더 나을 수는 없습니다.

또한 단순히 간단하게 매핑하는 "명백한"접근 방식이 가장 가까운 이웃에 대한 지점에 대한 접근 방식이 항상 최적의 솔루션을 생성하는 것은 아닙니다.

더 간단한 접근? : 보조 질문으로서, 실현 가능한 솔루션이 존재하지 않는 경우, 각각의 비 초당 섹션을 작은 영역에 분할하고 이러한 영역을 매핑하여 매핑 횟수를 크게 줄일 수 있습니다. 두 영역 사이의 거리를 계산하기 위해 질량 중심 (지역의 픽셀 위치의 평균)을 사용합니다. 그러나 이것은 거의 최적의 대답을 얻기 위해 파티션을하는 방법에 대한 문제를 제시합니다.

모든 아이디어가 감사합니다 !!

Answer 1

이것은 최소 일치 문제이며 일반적으로 어려운 문제라는 것이 맞습니다. 그러나 2D 유클리드 이당 최소 일치 경우 O (n²)에 가깝게 해결할 수 있습니다 (링크 참조).

또한 살펴보십시오 평면에서 이중 파파트 및 비 바이퍼 타이트 일치에 대한 근사 알고리즘 A O ((n/ε)^1.5*log^5 (n)) (1+ε)-랜덤 화 된 근사 체계.

Answer 2

당신은 고려할 수 있습니다 시뮬레이션 어닐링 이것을 위해. 각 픽셀에 대해 [x] -> b [y]를 무작위로 할당하여 시작하고 제곱 거리의 합을 계산합니다. 그런 다음 x <-> y 매핑을 무작위로 교체하십시오. 그런 다음 새로운 매핑이 더 좋으면 Q가 더 높고 시간이 지남에 따라 0으로 향하는 확률 Q로 이것을 받아들이도록 선택하십시오. 더 나은 설명은 Wikipedia 기사를 참조하십시오.

Answer 3

1. 픽셀을 모양 a로 정렬 : 'x'의 순서가 높아지면 'y'가 안정됩니다.
2. 모양 B의 픽셀을 정렬 : 'x'의 순서가 감소한 다음 'y'를 증가시킵니다.

동일한 인덱스의 맵 픽셀 : 정렬 된 목록에서 A의 첫 번째 픽셀은 B의 첫 번째 픽셀에 맵핑됩니다. 이것은 당신이 찾고있는 매핑이 아닙니다.