Bagaimana untuk menyelesaikan masalah pasangan mata terdekat dalam PHP menggunakan kaedah bahagi dan takluk dan dapatkan penyelesaian yang optimum?

Bagaimana untuk menggunakan kaedah bahagi dan takluk untuk menyelesaikan masalah pasangan mata terdekat dalam PHP dan mendapatkan penyelesaian yang optimum?

Masalah pasangan terdekat merujuk kepada mencari dua pasangan titik terdekat pada satah tertentu. Masalah ini sangat biasa dalam geometri pengiraan dan mempunyai banyak penyelesaian. Salah satu kaedah yang biasa digunakan ialah divide and conquer.

Kaedah divide and conquer ialah kaedah membahagikan masalah kepada sub-masalah yang lebih kecil dan menyelesaikan masalah asal dengan menyelesaikan sub-masalah secara rekursif. Dalam masalah pasangan mata terdekat, kita boleh menggunakan kaedah bahagi-dan-takluk untuk mencari penyelesaian optimum dengan cekap.

Berikut ialah langkah-langkah untuk menggunakan kaedah bahagi dan takluk untuk menyelesaikan masalah pasangan mata terdekat:

1. Masukkan set titik, di mana setiap titik diwakili oleh (x, y).
2. Susun pungutan mata mengikut koordinat x.
3. Jika bilangan mata kurang daripada atau sama dengan 3, terus gunakan kaedah brute force untuk menyelesaikan masalah pasangan mata terdekat. Iaitu, hitung jarak antara setiap dua titik dan cari jarak terkecil.
4. Bahagikan set titik kepada dua sub-set yang kira-kira sama, dipanggil kiri dan kanan masing-masing.
5. Panggil kaedah bahagi dan takluk secara berulang untuk mencari pasangan mata terdekat di kiri dan kanan masing-masing. Ditandakan sebagai (min_kiri, min_kiri) dan (min_kanan, min_kanan).
6. Ambil pasangan mata dengan jarak terkecil antara kiri_min dan kanan_min, dan hitung jarak antara mereka, direkodkan sebagai jarak_min.
7. Cari semua titik dalam set titik yang jarak koordinat-xnya dari garis tengah kurang daripada jarak_min, dan susun mengikut koordinat-y mereka.
8. Di antara titik ini, gunakan kaedah imbasan linear untuk mengira jarak antara setiap titik dan sehingga 6 titik berikutnya, dan cari jarak minimum.
9. Mengembalikan pasangan mata dengan jarak terkecil antara kiri_min dan kanan_min, dan jarak minimum yang diperoleh melalui imbasan linear.

Berikut ialah contoh kod yang menggunakan bahasa PHP untuk melaksanakan kaedah bahagi dan takluk untuk menyelesaikan masalah pasangan titik terdekat:

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

Di atas adalah contoh kod yang menggunakan kaedah bahagi dan takluk untuk menyelesaikan masalah pasangan mata terdekat Langkah terperinci dan contoh kod khusus. Dengan membahagikan masalah kepada sub-masalah berskala lebih kecil, dan dengan menyelesaikan sub-masalah secara rekursif, kita boleh menyelesaikan masalah pasangan titik terdekat dengan cekap dan mendapatkan penyelesaian yang optimum. Melalui reka bentuk dan pengoptimuman algoritma yang munasabah, kecekapan dan prestasi penyelesaian masalah boleh dipertingkatkan.

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah pasangan mata terdekat dalam PHP menggunakan kaedah bahagi dan takluk dan dapatkan penyelesaian yang optimum?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!