Rumah > Artikel > pembangunan bahagian belakang > 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:
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!