PHP で分割統治法を使用して最近接点ペア問題を解決し、最適な解を得るにはどうすればよいですか?

分割統治法を使用して PHP の最近接点ペア問題を解決し、最適な解を得るにはどうすればよいですか?

最近接ペア問題とは、指定された平面上で 2 つの最も近い点のペアを見つけることを指します。この問題は計算幾何学では非常に一般的な問題であり、多くの解決策があります。一般的に使用される方法の 1 つは分割統治です。

分割統治法は、問題をより小さな部分問題に分割し、その部分問題を再帰的に解決することで元の問題を解決する方法です。最近点ペア問題では、分割統治法を使用して最適解を効率的に見つけることができます。

以下は、分割統治法を使用して最近接点ペア問題を解決する手順です。

1. 点のセットを入力します。各点は (x, y)。
2. x 座標に従ってポイント コレクションを並べ替えます。
3. 点の数が 3 以下の場合は、総当たり法を直接使用して最近点ペア問題を解決します。つまり、2 点ごとに距離を計算し、最小距離を見つけます。
4. 点セットを、それぞれ左と右と呼ばれる 2 つのほぼ等しいサブセットに分割します。
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 中国語 Web サイトの他の関連記事を参照してください。