Comment résoudre le problème de paire de points la plus proche en PHP en utilisant la méthode diviser pour régner et obtenir la solution optimale ?

Comment utiliser la méthode diviser pour régner pour résoudre le problème de paire de points la plus proche en PHP et obtenir la solution optimale ?

Le problème des paires les plus proches consiste à trouver les deux paires de points les plus proches sur un plan donné. Ce problème est très courant en géométrie computationnelle et a de nombreuses solutions. L’une des méthodes couramment utilisées est diviser pour régner.

La méthode diviser pour mieux régner est une méthode permettant de diviser un problème en sous-problèmes de plus petite taille et de résoudre le problème d'origine en résolvant les sous-problèmes de manière récursive. Dans le problème de la paire de points la plus proche, nous pouvons utiliser la méthode diviser pour régner pour trouver efficacement la solution optimale.

Voici les étapes à suivre pour utiliser la méthode diviser pour mieux régner afin de résoudre le problème de la paire de points la plus proche :

1. Saisissez un ensemble de points, où chaque point est représenté par (x, y).
2. Triez la collection de points en fonction de la coordonnée x.
3. Si le nombre de points est inférieur ou égal à 3, utilisez directement la méthode de la force brute pour résoudre le problème de la paire de points la plus proche. Autrement dit, calculez la distance entre deux points et trouvez la plus petite distance.
4. Divisez l'ensemble de points en deux sous-ensembles à peu près égaux, appelés respectivement gauche et droite.
5. Appelez la méthode diviser pour régner de manière récursive pour trouver les paires de points les plus proches respectivement à gauche et à droite. Noté (left_min, left_max) et (right_min, right_max).
6. Prenez la paire de points avec la plus petite distance entre left_min et right_min et calculez la distance entre eux, enregistrée sous la forme min_distance.
7. Trouvez tous les points de l'ensemble de points dont la distance de coordonnée x par rapport à la ligne médiane est inférieure à min_distance et triez-les en fonction de leur coordonnée y.
8. Parmi ces points, utilisez la méthode de balayage linéaire pour calculer la distance entre chaque point et jusqu'à 6 points suivants, et trouvez la distance minimale.
9. Renvoie la paire de points avec la plus petite distance entre left_min et right_min, et la plus petite distance obtenue par balayage linéaire.

Ce qui suit est un exemple de code utilisant le langage PHP pour implémenter la méthode diviser pour régner afin de résoudre le problème de paire de points la plus proche :

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));
}

Ce qui précède sont des étapes détaillées et des exemples de code spécifiques pour utiliser la méthode diviser pour régner pour résoudre le problème de la paire de points la plus proche. En divisant le problème en sous-problèmes à plus petite échelle et en résolvant les sous-problèmes de manière récursive, nous pouvons résoudre efficacement le problème de paire de points le plus proche et obtenir la solution optimale. Grâce à une conception et à une optimisation raisonnables des algorithmes, l’efficacité et les performances de la résolution de problèmes peuvent être améliorées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!