ดูต้นฉบับสำหรับ ปัญหาการหาคู่ของจุดที่ใกล้กันที่สุด

{{ลิงก์ไปภาษาอื่น}}

'''ปัญหาการหาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด''' ({{langx|en|closest pair problem}}) เป็นหนึ่งในงานวิจัยทางด้าน[[เรขาคณิตคำนวณ]] ([[:en:Computational Geometry|Computational Geometry]]) จากปัญหานี้ถ้าใช้วิธีการหาระยะทางที่ใกล้ที่สุดกับจุดทุกๆ จุด นั้นจะต้องใช้เวลาเป็น Θ (n<sup>2</sup>) จากเวลาการทำงานยังเป็นเวลาที่สูง จึงได้ทำการแก้ปัญหานี้ซึ่งใช้[[ขั้นตอนวิธีแบ่งแยกและเอาชนะ]] โดยที่เวลาการทำงานเป็น <math>O (n \log n)</math> และขั้นตอนวิธีนี้เป็นขั้นตอนวิธีแบบอนุกรมที่ดีที่สุดสำหรับปัญหานี้

== ลักษณะของปัญหา ==
:โจทย์ : ให้จุด N จุด ซึ่งอยู่บนระนาบ
:คำตอบ : หาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด
:โดยมีสูตรการหาระยะทางระหว่างจุด 2 จุด คือ d<sub>i.j</sub> = ((x<sub>i</sub>-x<sub>j</sub>)<sup>2</sup> + (y<sub>i</sub>-y<sub>j</sub>)<sup>2</sup>)<sup>1/2</sup>
== ปัญหารูปแบบต่างๆ ==
* 	จุดทั้งหมดเรียงตัวอยู่ในแนว 1 มิติ นั่นคือ จุดทุกๆจุด เรียงตัวกันบนเส้นตรงเส้นเดียวกัน
* 	จุดทั้งหมดเรียงตัวอยู่บนระนาบ 2 มิติ 
== วิธีการแก้ปัญหาแบบ 2 มิติ ==
=== 1.	ขั้นตอนวิธีการแบบบรูทฟอร์ซ (Brute force) ===
ทำการตรวจสอบระยะทางในทุกๆจุด และนำมาคำนวณหาระยะทางที่มีค่าน้อยที่สุด 
==== รหัสเทียม ====
<source lang="text">
 closetPair ( x[1…n], y[1…n] )
   min = infinity
   for ( i=1…n)
    for ( j= (i+1) …n)
     dx = | x[i] – x[j]
| dy = | y[i] – y[j]
| d = sqrt (dx2 + dy2 )
     if ( f<min ) min = d
 return min
</source>

=== 2.	ขั้นตอนวิธีการแบบแบ่งแยกและเอาชนะ (Divide and Conquer) ===
* การแบ่งแยก คือ การมองปัญหาใหญ่ๆ ออกเป็นปัญหาย่อยๆ ซึ่งในปัญหานี้คือการมองพื้นที่ทั้งหมดออกเป็น 2 ส่วน โดยที่แต่ละส่วนมีจำนวนจุดใกล้เคียงกัน 
* การเอาชนะ คือ การหาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด ในพื้นที่แต่ละด้าน โดยใช้[[ความสัมพันธ์เวียนเกิด|ขั้นตอนวิธีการเรียกซ้ำ]] (Recursive)
* การรวมกัน คือ การหาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด ซึ่งจุดทั้ง 2 จุดอยู่บนพื้นที่คนละด้านกัน
==== ลำดับขั้นตอน ====
* ให้ x เป็นค่าน้อยที่สุดจากระยะทางที่หาได้จากการเรียกซ้ำ
* พิจารณาจากจุดทุกๆจุดซึ่งอยู่บริเวณที่ห่างจากเส้นกั้นกลาง 2 ฝั่ง ด้วยความยาวไม่เกิน x
* เรียงลำดับระยะห่างของจุดทุกๆจุดในบริเวณนั้น โดยเก็บข้อมูลเป็นพิกัดทั้งแนวนอนและแนวตั้ง ซึ่งเป็นการทำให้สามารถระบุได้ว่าจุดใดอยู่ทางฝั่งซ้ายหรือฝั่งขวา
* สร้างกรอบสี่เหลี่ยม ขนาด x * 2x ขึ้นมาบนพื้นที่นั้น ใช้เลื่อนไปตามจุด n คู่ เพื่อนหาระยะที่ใกล้กันที่สุด

::'''สี่เหลี่ยมขนาด x * 2x ใช้เพื่อตรวจหาระยะทางระหว่างจุดคู่ที่ใกล้กันที่สุดจากพื้นที่ตรงเส้นกั้นกลาง'''

* คำตอบที่ถูกต้อง คือ ระยะที่น้อยที่สุดจากการระยะทางที่ได้จากจุด 2 จุดที่ได้มาจากการคำนวณจากพื้นที่ 2 ฝั่งและพื้นที่ตรงกลาง 
::'''ระยะทางระหว่างจุดคู่ที่ใกล้กันที่สุด 3 ระยะ ที่ได้มาจากการคำนวณจากพื้นที่ 2 ฝั่งและพื้นที่ตรงกลาง'''

==== รหัสเทียม ====
<source lang="text">
 ClosestPair (ptsByX, ptsByY, n) 
  if (n = 1) return ∞
  if (n = 2) return distance (ptsByX[0], ptsByX[1]) 

  // มองลักษณะเป็นปัญหาย่อย (การแบ่งแยก) 
  mid ← dn/2e − 1
  คัดลอกค่าจาก ptsByX[0 . . . mid] ไปไว้ที่อาเรย์ XL ตำแหน่งที่ x
  คัดลอกค่าจาก ptsByX[mid+1 . . . n − 1] ไปไว้ที่อาเรย์ XR ตำแหน่งที่ x

  คัดลอกค่าจาก ptsByY ไปไว้ที่อาเรย์ Y L และ Y R ตำแหน่งที่ y , s.t
   XL และ Y L อ้างถึงจุดๆเดียวกัน เช่นเดียวกันกับ XR และ Y R

  // ขั้นตอนวิธีการเรียกซ้ำเพื่อหาระยะทางที่ใกล้กันที่สุด (การเอาชนะ) 
  distL ← ClosestPair (XL, Y L, dn/2e)
  distR ← ClosestPair (XR, Y R, bn/2c) 

  // นำมารวมกัน 
  midPoint ← ptsByX[mid] 
  lrDist ← min (distL, distR) 
  สร้างอาเรย์ yStrip ในลำดับที่ y (เพิ่มขึ้น) 
   สำหรับจุด p ใดๆ ใน ptsByY s.t. |p.x − midPoint.x| < lrDist

   minDist ← lrDist
  for (j ← 0; j ≤ yStrip.length − 2; j++) {
   k ← j + 1
   while (k ≤ yStrip.length − 1 and yStrip[k].y − yStrip[j].y < lrDist) {
    d ← distance (yStrip[j], yStrip[k]) 
    minDist ← min (minDist, d) 
    k++
    } 
   } 
  return minDist
</source>

== ประสิทธิภาพการทำงาน ==
* '''ขั้นตอนวิธีการแบบบรูทฟอร์ซ''' 
เป็นวิธีที่ธรรมดาที่สุด โดยทำการตรวจสอบทั้งหมด n (n-1)/2 คู่ และใช้เวลาการทำงานเป็น Θ (n<sup>2</sup>)
* '''วิธีการแบบแบ่งแยกและเอาชนะ''' 
มีการมองปัญหาใหญ่เป็นปัญหาย่อยๆ ทำให้เป็นวิธีที่ใช้เวลาน้อยที่สุด นั่นคือใช้เวลาการทำงานเป็น Θ (nlogn) มาจาก t (n) = 2t (n/2) + Θ (n)  = Θ (nlogn) โดย 2t (n/2) มาจากการเรียกซ้ำใน 2 รอบ ในพื้นสี่ฝั่งซ้ายและฝั่งขวา และ Θ (n) มาจากการเอาสี่เหลี่ยมเทียบกับจุดจำนวน n คู่ 

== การนำไปใช้งาน ==
ปัญหาการหาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด ถูกนำไปประยุกต์ใช้ในงานหลากหลายด้าน หลากหลายแอปพลิเคชัน (Application) เช่น นำไปใช้ในระบบควบคุมการจราจรทางอากาศหรือทางทะเลซึ่งในการควบคุมนั้นจำเป็นต้องรู้ว่ามียานพาหนะ 2 ลำไหนที่อยู่ใกล้กันที่สุดเพื่อที่จะป้องกันการชนกันได้ เป็นต้น

== อ้างอิง ==
* Jeremy Buhler (2011), Fast Closest-Pair Algorithm, ''Faculty of Engineering of Washington University in St.Louis,'' http://classes.cec.wustl.edu/~cse241/handouts/closestpair.pdf {{Webarchive|url=https://web.archive.org/web/20110813164032/http://classes.cec.wustl.edu/~cse241/handouts/closestpair.pdf |date=2011-08-13 }}
* Robert Sedgewick, Kevin Wayne (2007), Geometric Algorithms, ''Department of Computer Science,Princeton University,'' http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf

[[หมวดหมู่:ขั้นตอนวิธีเชิงเรขาคณิต|ปัญหาการหาคู่ของจุดที่ใกล้กันที่สุด]]