분할 및 정복 방법을 사용하여 PHP에서 가장 가까운 점 쌍 문제를 해결하고 최적의 솔루션을 얻는 방법은 무엇입니까?

PHP에서 가장 가까운 점 쌍 문제를 해결하고 최적의 솔루션을 얻기 위해 분할 및 정복 방법을 사용하는 방법은 무엇입니까?

가장 가까운 쌍 문제는 주어진 평면에서 가장 가까운 두 점 쌍을 찾는 것을 의미합니다. 이 문제는 계산 기하학에서 매우 일반적이며 많은 해결책이 있습니다. 일반적으로 사용되는 방법 중 하나는 분할 정복입니다.

분할 정복 방법은 문제를 더 작은 크기의 하위 문제로 나누고, 하위 문제를 재귀적으로 해결하여 원래 문제를 해결하는 방법입니다. 가장 가까운 점 쌍 문제에서는 분할 정복 방법을 사용하여 최적의 솔루션을 효율적으로 찾을 수 있습니다.

다음은 분할 정복 방법을 사용하여 가장 가까운 점 쌍 문제를 해결하는 단계입니다.

1. 점 집합을 입력합니다. 여기서 각 점은 (x, y)로 표시됩니다.
2. x 좌표에 따라 포인트 컬렉션을 정렬합니다.
3. 점 수가 3보다 작거나 같으면 직접 무차별 대입법을 사용하여 가장 가까운 점 쌍 문제를 해결합니다. 즉, 두 점 사이의 거리를 계산하고 가장 작은 거리를 찾는 것입니다.
4. 점 집합을 각각 왼쪽과 오른쪽이라고 하는 두 개의 대략 동일한 하위 집합으로 나눕니다.
5. 분할 및 정복 방법을 재귀적으로 호출하여 각각 왼쪽과 오른쪽에서 가장 가까운 점 쌍을 찾습니다. (left_min, left_max) 및 (right_min, right_max)로 표시됩니다.
6. left_min과 right_min 사이의 거리가 가장 작은 점 쌍을 선택하고 그 사이의 거리를 계산하여 min_distance로 기록합니다.
7. 정중선으로부터 x 좌표 거리가 min_distance보다 작은 점 집합에서 모든 점을 찾아 y 좌표에 따라 정렬합니다.
8. 이러한 점 중에서 선형 스캔 방법을 사용하여 각 점과 최대 6개의 후속 점 사이의 거리를 계산하고 최소 거리를 찾습니다.
9. left_min과 right_min 사이의 거리가 가장 작고 선형 스캔으로 얻은 거리가 가장 작은 점 쌍을 반환합니다.

다음은 가장 가까운 점 쌍 문제를 해결하기 위해 분할 정복 방법을 구현하기 위해 PHP 언어를 사용하는 코드 예제입니다.

function closestPair($points) {
  $n = count($points);
  
  // 升序排序
  usort($points, function($a, $b){
    return $a['x'] - $b['x'];
  });
  
  // 少于等于3个点直接暴力求解
  if ($n <= 3) {
    return bruteForce($points);
  }
  
  // 分成两个子集合
  $mid = floor($n / 2);
  $left = array_slice($points, 0, $mid);
  $right = array_slice($points, $mid);
  
  // 递归调用分治法
  $leftPair = closestPair($left);
  $rightPair = closestPair($right);
  
  // 找到距离最小的点对
  $delta = min($leftPair['distance'], $rightPair['distance']);
  $minPair = ($leftPair['distance'] < $rightPair['distance']) ? $leftPair : $rightPair;
  
  // 找到中线附近距离小于delta的点
  $strip = [];
  foreach ($points as $point) {
    if (abs($point['x'] - $points[$mid]['x']) < $delta) {
      $strip[] = $point;
    }
  }
  
  // 按照y坐标排序
  usort($strip, function($a, $b){
    return $a['y'] - $b['y'];
  });
  
  // 线性扫描
  $stripPair = stripScan($strip, $delta);
  
  // 返回距离最小的点对
  return ($minPair['distance'] < $stripPair['distance']) ? $minPair : $stripPair;
}

function bruteForce($points) {
  $n = count($points);
  $minDistance = PHP_INT_MAX;
  $minPair = [];
  
  for ($i = 0; $i < $n; $i++) {
    for ($j = $i+1; $j < $n; $j++) {
      $distance = distance($points[$i], $points[$j]);
      if ($distance < $minDistance) {
        $minDistance = $distance;
        $minPair = [$points[$i], $points[$j]];
      }
    }
  }
  
  return [
    'distance' => $minDistance,
    'pair' => $minPair
  ];
}

function stripScan($strip, $delta) {
  $n = count($strip);
  $minDistance = $delta;
  $minPair = [];
  
  for ($i = 0; $i < $n-1; $i++) {
    for ($j = $i+1; $j < $n && ($strip[$j]['y'] - $strip[$i]['y']) < $minDistance; $j++) {
      $distance = distance($strip[$i], $strip[$j]);
      if ($distance < $minDistance) {
        $minDistance = $distance;
        $minPair = [$strip[$i], $strip[$j]];
      }
    }
  }
  
  return [
    'distance' => $minDistance,
    'pair' => $minPair
  ];
}

function distance($a, $b) {
  return sqrt(pow(($b['x'] - $a['x']), 2) + pow(($b['y'] - $a['y']), 2));
}

위는 분할 정복 방법을 사용하기 위한 자세한 단계와 구체적인 코드 예제입니다. 가장 가까운 점 쌍 문제를 해결합니다. 문제를 더 작은 규모의 하위 문제로 나누고 하위 문제를 재귀적으로 해결함으로써 가장 가까운 점 쌍 문제를 효율적으로 해결하고 최적의 솔루션을 얻을 수 있습니다. 합리적인 알고리즘 설계 및 최적화를 통해 문제 해결의 효율성과 성능을 향상시킬 수 있습니다.

위 내용은 분할 및 정복 방법을 사용하여 PHP에서 가장 가까운 점 쌍 문제를 해결하고 최적의 솔루션을 얻는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!