Closest Pair : Easy Explanation

6 min readDec 14, 2019

สวัสดีครับ นี่เป็นบทความเกี่ยวกับปัญหาสุดคลาสสิคอันหนึ่งที่ชื่อว่า Closest Pair(ปัญหาการหาระยะคู่จุดสั้นสุด) มันก็มีบทความเกี่ยวกับเรื่องนี้ไว้มากมายนะ แต่ด้วยความเป็นนามธรรมของแนวคิดทำให้ไม่เห็นภาพกันเท่าไหร่ ผมก็เลยจะมาลองอธิบายให้มันง่าย ๆ และเห็นภาพกันชัด ๆ ดูครับ มาเริ่มกันเลย

ความรู้พื้นฐานที่ควรมีก่อนอ่านบทความนี้

ความรู้เบสิคใน C/C++(รู้จัก STL C++ และ math function ทั้งหลาย)
รู้จักคำศัพท์ในคณิตศาสตร์บ้าง (เช่นคำว่า ระนาบ จำนวนจริง พิกัด มิติ ฯลฯ)
วิเคราะห์อัลกอรึทึมเป็น (หา Big-O ทั้งหลาย, Tree Recursion)

Problem

มีจุดในระนาบ 2 มิติอยู่ N จุด จงเขียนโค้ดหาระยะทางที่สั้นที่สุดระหว่างคู่จุดใด ๆ

จากโจทย์ มีคำกำกวมอยู่ 2 คำ โปรดทำความเข้าใจให้ตรงกัน ดังนี้

จุด(n.) ในที่นี้หมายถึง เลขจำนวนจริง 2 ตัวคู่กันเพื่อบอกถึงพิกัดแกน x, y
ระยะทาง(n.) ในที่นี้หมายถึง ระยะทางแบบยูคลิด นั่นคือ
ให้ p และ q เป็นจุด โดย p มีพิกัด (p.x, p.y) และ q มีพิกัด (q.x, q.y)
ระยะทางระหว่างจุด p และ q แทนด้วยสัญลักษณ์ dst(p, q)
ซึ่งจะได้

ตัวอย่าง

N = 11 หมายถึง มีจุดอยู่ 11 จุด คือ (-7, 4), (1, -1), (-8, -2), (10, 10), (6, 1), (-5, 9), (1, 1),(-1, 5), (-3, 4), (-7, -6), (6, -3) โอเค มันเยอะ มาดูภาพดีกว่า จะได้ภาพดังนี้

จากภาพ ลองใช้สายตาอันเฉียบแหลมหาระยะทางสั้นสุดจะได้ว่า ระยะทางสั้นสุดมาจากจุด (1, 1) และจุด (1, -1) ดังภาพด้านล่าง

ซึ่งจะได้ระยะสั้นสุดหรือก็คือ dst((1, 1), (1, -1)) = sqrt((1-1)²+(1- (-1))²) = sqrt(0² +2²) = sqrt(4) = 2 ดังนั้นระยะสั้นสุดของคู่จุดใด ๆ ใน 11 จุดนี้คือ 2 นั่นเอง (สังเกตว่าระยะทางอาจเป็นทศนิยมได้ เพราะค่าที่ได้มาจาก sqrt)

จากตัวอย่างมีอะไรให้สังเกตอีก

ถ้ามี 2 จุดใด ๆ อยู่ในตำแหน่งเดียวกัน เราจะได้ว่า ระยะทางสั้นสุดคือ 0 เสมอ ซึ่งการตรวจสอบแบบนี้ทำได้ไม่ยากเย็นนัก (ใช้ data structure พวก hash หรือ set ก็ได้)

ทีนี้ หากรับประกันว่าไม่มีคู่จุดไหนซ้ำกันเลย จะมีขั้นตอนกระบวนการในการหาระยะทางดังกล่าว ทุกกรณีได้อย่างไร

Solution I: Brute Force

วิธีนี้คือลองเลือกทุกคู่จุดแล้วดูว่าระยะทางของคู่จุดไหนน้อยสุด ก็ตอบอันนั้นก็จะได้โค้ดง่าย ๆ ดังนี้

Code C/C++: Brute Force Solution for Closest Pair

คุยกันก่อนไปต่อ
จากโค้ดด้านบน ผมใช้ไวยากรณ์ภาษา C และ C++ ผสมกันอย่างเละ รวมถึงมีการเขียน Interface ด้วยว่าให้รับอะไรบ้าง หากท่านใดไม่เข้าใจโค้ดเลย ให้ไปศึกษาก่อนมาอ่านบทความนี้นะครับ เพราะต่อไปโค้ดจะซับซ้อนขึ้นนิสนุง

มากันต่อ จากโค้ด Brute force ผลลัพธ์การรันจะเป็นดังนี้ (ต่อไปจะมีแค่โค้ด เพราะผลลัพธ์มันจะเหมือน ๆ กันหมด)

ผลลัพธ์การรัน มีการใส่ input และแสดง output พร้อม interface ต่าง ๆ ดังภาพ

เห็นไหมว่า การโค้ดด้วยวิธีนี้ ผลลัพธ์ก็ถูกต้องตามที่ต้องการ แบบนี้เราก็ถือว่าแก้ปัญหาเสร็จแล้วสิ เย่ ~~

ภั๊ววววว //เสียงตบหน้า …ตื่นครับทุกคน นี่มันพึ่งเริ่มต้น มาวิเคราะห์เวลาการทำงานกันก่อน จากโค้ดเอาเป็นว่ามันได้เวลาทำงานเป็น O(N²) เพราะมี for loop สองชั้น แต่ละชั้นก็ทำงานอย่างมาก N รวม ๆ ละก็ N² ครั้ง (อันนี้วิเคราะห์ง่าย)

แล้วยังไงล่ะ? …ก็ถ้าสมมติว่ามีจุดจำนวน 500000 จุด แล้วต่อให้คอมพิวเตอร์ทำงานในร้อยล้านคำสั่งต่อวินาทีได้(ซึ่งค่ดเร็ว) ถามว่าจะใช้เวลาเท่าไหร่? ….คำตอบก็คือ 500000² / 10⁸ = 2500 วิ หรือ 41 นาทีกว่า ๆ … ขุ่นพระ แค่อยากรู้ว่าคู่จุดไหนสั้นสุด ต้องรอเกือบชั่วโมงเลย จะยอมหรอฮะ( =3=)

เอาล่ะ ปูมาขนาดนี้แล้วก็ต้องมีวิธีดี ๆ แหละนะ

Solution II: Divide and Conquer

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

อ่านแล้วก็ยังไม่เข้าใจ งั้นเราไปดูสไลด์ภาพกันครับ (อ่านคำบรรยายในภาพเอานะ)

สไลด์อธิบายแนวคิดแบบ Divide and Conquer

จากที่เห็นในสไลด์ สามารถนำมาจับกับแนวคิดของ Divide and Conquer ได้ดังนี้

ส่วนที่เรียกว่า แบ่ง(Divide): สไลด์หน้า 7–8
ส่วนที่เรียกว่า การเอาชนะ(Conquer) หรือเรียกว่ารวมปัญหา (Combine): สไลด์หน้า 9–12

นำไอเดียนี้มาเขียนเป็นขั้นตอนวิธี(Algorithm) ตามโค้ดเทียมได้ดังนี้

pseudo code for closest pair using divide and conquer

จากโค้ดเทียมนี้ ส่วนที่กำกวมและ“งง-งวย”ที่สุดคงจะเป็นขั้นตอนการ Combine ว่ามันทำยังไงถึงหาระยะสั้นสุดของข้ามฝั่งได้ เดี๋ยวเราก็จะมาคุยกันที่ตัวนี้แหละครับ

ก่อนอื่นเลย จากโค้ดเทียม การแบ่งจุดของขั้นตอน FirstHalf กับ SecondHalf เราจะใช้ไอเดียของการดูจำนวนจุด คนละครึ่ง(ตามที่นำเสนอไปในสไลด์) โดยเป็นการแบ่งตามแกน x นั่นเอง ดังนั้นก่อนเรียกใช้ ClosestPair() ต้องทำการเรียงจุด p ทุกจุดตามแกน x มาก่อนนะฮะ (ถ้ามีแกน x เท่ากัน จะเรียงยังไงก็ได้)

ต่อมา มาคุยถึงขั้นตอนการรวมคำตอบหรือการ Combine กัน ถ้าสมมติได้รูปการแบ่งตามภาพนี้

ภาพแสดงการหาระยะสั้นสุดระหว่างจุดข้ามฝั่งแบบ ลุยจับคู่ ภาพที่ 1

แล้วเราลองจับคู่ระหว่างแต่ละจุดในฝั่งซ้าย ไปคู่กับ แต่ละจุดในฝั่งขวา แล้วหาระยะสั้นสุดดู

ภาพแสดงการหาระยะสั้นสุดระหว่างจุดข้ามฝั่งแบบ ลุยจับคู่ ภาพที่ 2

จากภาพ ถ้าเรานำมาวิเคราะห์เวลาแบบ Tree Recursion จะได้ว่า T(N) = 2T(N/2) + O(N²) = O(2*N²) = O(N²) ซึ่งเห็นเลยว่าช้าไม่ต่างจากวิธีแรกเลย แถมยังยุ่งยากกว่าเสียอีก

ที่เป็นแบบนั้นเพราะเราไม่ได้เอาคำตอบของฝั่งซ้ายและขวา(dL, dR)มาพิจารณาร่วมเลยนั่นเอง ทีนี้มาคิดหาคำตอบข้ามฝั่งโดยเอาคำตอบซ้ายขวามาช่วยแก้กันบ้าง

จากภาพด้านล่าง สมมติให้ d เป็นระยะน้อยสุดระหว่าง dL กับ dR จะได้ว่าเส้นข้ามฝั่งที่จะหาก็ควรน้อยกว่าหรือเท่ากับ d ซึ่งพอคิดดู ๆ แล้วก็จะพบว่าคู่จุดที่มันจะข้ามฝั่งและระยะทางน้อยกว่าหรือเท่ากับ d ก็ต้องอยู่ในแถบขอบเขตสีฟ้า(Strip) เท่านั้น เพราะถ้ามันไม่อยู่ในขอบเขตนั้น ระยะของเส้นข้ามฝั่งก็จะมากกว่า d แน่ ๆ อย่างน้อยก็ 2*d แล้ว ซึ่งก็จะไม่ได้ระยะสั้นสุดของทุกจุดชัวร์ ๆ ดังนั้นดูแค่ในขอบเขตสีฟ้านะครับ

ภาพแสดง idea การคิดข้ามฝั่งโดยใช้คำตอบซ้ายและขวามาช่วยแก้

ด้วยการสังเกตตรงนี้ ทำให้เราสามารถลดจำนวนการค้นไปได้เยอะมาก(หรอ?) ซึ่งพอดีใจไปสักพักก็จะคิดกรณีที่ทำให้ทำงานช้าเหมือนเดิมได้ดังภาพต่อไปนี้

คือมีการแบ่งจำนวนจุดออกเป็นครึ่ง ๆ เท่ากันของฝั่งซ้ายขวา จุดที่อยู่บนเส้นคือจุดฝั่งซ้าย เป็นตัวบอกว่าฉันแบ่งให้นะและฉันอยู่ตรงกลางด้วย พอมาคิดหา dL กับ dR แล้วตีขอบเขตแถบสีฟ้าของคู่จุดที่น่าจะได้คำตอบสั้นกว่า d ดู ก็จะได้ดังภาพ

สังเกตว่า ทุกจุดที่จะอยู่ในแถบสีฟ้าได้นั้น ต้องมีระยะจากจุดแบ่งตามแกน x ไม่เกิน d เท่านั้น กล่าวคือ จุด(point)ที่ i อยู่จะอยู่ในแถบสีฟ้าได้ ก็ต่อเมื่อ|point[i].x - midPoint.x| ≤ d โดย midPoint คือจุดตรงกลางที่แบ่งจำนวนจุดออกเป็นซ้ายขวาในจำนวนที่เท่า ๆ กัน ทีนี้เมื่อต้องการค้นหาระยะของคู่จุดข้ามฝั่งจากกรณีที่ยกมา จะได้ว่า

จุดแทบจะทั้งหมดหรือทั้งหมดอยู่ในแถบสีฟ้า ถ้าเราใช้วิธีที่เอาแต่ละจุดในฝั่งซ้ายไปจับกับคู่แต่ละจุดในฝั่งขวา มันก็ไม่ต่างจากวิธีลุยดูทุกคู่อยู่ดี ดังนั้นจะทำอย่างไรล่ะ

สังเกตว่าระยะจากจุด ๆ หนึ่ง(ดูจากจุดด้านบน ลงด้านล่าง) มันจะลงไปจับคู่กับจุดข้างล่างมันได้ ก็ต่อเมื่อระยะในแกน y ของจุดนั้นและจุดที่จับคู่ด้วยมันไม่เกิน d อย่าลืมว่า d คือระยะที่น่าจะสั้นสุดตอนนี้ แต่ใครที่มีระยะมากกว่าระยะน่าจะสั้นสุด มันก็ไม่มีทางสั้นสุดแน่ ๆ ฉะนั้นสำหรับจุด ๆ หนึ่ง จะพิจารณาว่าจับคู่ได้ไหมตราบเท่าที่ระยะห่างในแกน y ของจุดนั้น ๆ จับคู่กับจุดข้างล่างไม่เกิน d ก็พอนะครับ //รู้สึกอธิบายวน ๆ

กล่าวคือ … เราจะสร้างขอบเขตการตรวจสอบที่จำเป็นตามอนิเมชั่นในสไลด์ด้านล่างนี้ครับ (มีกล่องสี่เหลี่ยมขนาดกว้าง 2d หน่วย สูง d หน่วย แล้วสแกนจากจุดบนสุดไปล่างสุด)

ภาพแสดงการสร้างขอบเขตการตรวจสอบที่รัดกุมมากขึ้น

จากอนิเมชั่นกวน ๆ จะเห็นได้ว่า สิ่งที่เราต้องทำมีอยู่ 2 อย่าง

ต้องดูจุดจากด้านบนลงมาด้านล่าง (อาจเรียงข้อมูลตามแกน y ก่อนละค่อยไล่ดู)
เลื่อนกล่องเพื่อพิจารณาระยะของคู่จุดในกล่องนั้นที่อาจจะสั้นกว่า d ได้

สังเกตว่า จำนวนการเลื่อนกล่อง จะเท่ากับ จำนวนจุดในแถบสีฟ้าเลย ซึ่งแต่ละกล่องจะมีการคำนวณระยะของคู่จุดไม่เกิน 8 คู่แค่นั้นเอง(อ้างอิงจากในสไลด์อนิเมชั่น เดี๋ยวค่อยแสดงให้เห็นว่า ทำไมมีแค่ 8 คู่จุดเอง) ซึ่งก็จะได้โค้ดเทียมดังนี้

d = min(dL, dR)  // สมมติว่า d คือระยะคู่จุดฝั่งซ้ายขวาสั้นสุดที่รู้ตอนนี้
Let strip เป็น array ที่เก็บจุดในแถบสีฟ้า โดยเรียงตามแกน y แล้ว
for cur = 0 to |strip|-1 {                     // ดูทีละจุดในแถบสีฟ้า
   for nxt = cur+1 to |strip|-1 {              // ดูจุดต่อไป(ด้านล่าง)
       if |strip[cur].y - strip[nxt].y| >= d { 
           break // ตรงจุดนี้จะทำให้เราไม่ต้องคำนวณจุดที่ไม่จำเป็น
       }
       d = คำนวนค่าระยะของจุด strip[cur] และ strip[nxt] เทียบกับ d เดิม
       // โดย d จะเก็บระยะคู่จุดสั้นสุดเป็นคำตอบแบบข้ามฝั่งต่อไป
   }
}

ดังนั้น จากทั้งหมดทั้งมวลนี้ เราก็จะได้ระยะข้ามฝั่งของทุกคู่จุดแล้วนั่นเอง ซึ่งก็จะสามารถตอบคำถามว่า ระยะสั้นสุดของคู่จุดใด ๆ มีค่าเท่าไหร่ได้แล้ว

ทีนี้มาวิเคราะห์เวลาการทำงานกัน (ขอให้ดีกว่า N²) การเดิม เรามีจุด N จุด แล้วแบ่งทีละครึ่ง แล้วไปหาคำตอบของแต่ละครึ่ง จากนั้นรวมคำตอบโดยหาคู่จุดข้ามฝั่งด้วยวิธีเลื่อนกล่อง จะได้ T(N) = 2T(N/2) + #เวลาการเลื่อนกล่องอย่างดี

ซึ่งถ้าเราทำตามอนิเมชั่นกวน ๆ อันเดิม ที่ต้องเรียงจุดในแทบตามแกน y ก่อน เพื่อดูทีละจุดจากบนลงล่างได้ ซึ่งจะใช้เวลาเรียงมากสุดคือ O(N log N) จากนั้นทำการเลื่อนกล่อง ซึ่งมีจำนวนการเลื่อนเท่ากับจำนวนจุดในแถบ และจุดในแถบก็มีมากสุด N จุด(มีจุดทั้งหมด) และแต่ละจุดก็จะมีการจับคู่ได้มากสุด 8 คู่(เป็นค่าคงที่) ดังนั้นจะได้เวลาในการเลื่อนเป็น O(8*N) = O(N) สรุป จะได้ #เวลาการเลื่อนกล่องอย่างดี = O(N log N) + O(N) = max (O(N log N), O(N)) = O(N log N)

ทำให้ได้ T(N) = 2T(N/2) + O(N log N) หากใช้สมการแทนรูปตามลิงก์นี้ก็จะได้ T(N) = O(N log² N) // หรือจะใช้ Tree Recursion วิเคราะห์ดูก็ได้

ก็จะได้โค้ดสำหรับแนวคิดที่จะทำงานในเวลา O(N log² N) ดังนี้

Code C/C++: Divide and Conquer Solution for Closest Pair

เมื่อกลับมาที่สภาพแวดล้อมร้อยล้านคำสั่งของเรา เมื่อให้ N = 500000 จากเดิมที่ใช้เวลาเกือบชั่วโมง จะเหลือแค่ 500000 * log²(500000) / 10⁸ = 0.539 วิ!!! ขุ่นพระ ไม่ถึงวิด้วยซ้ำอะครับ นี่แหละครับ พลังของการเปลี่ยนแนวคิด
เอาล่ะ ทั้งหมดที่กล่าวถึงเรื่องของเวลาเป็นเพียงการประมาณเท่านั้น ยังไงซะในสภาพล้อมจริงก็ยังมีปัจจัยอะไรอีกหลาย ๆ อย่างเช่นความแรงของคอม ระบบปฎิบัติการที่ใช้ ภาษาที่เขียนโค้ด จำนวนคำสั่งต่อวิของ CPU ก็เยอะแยะอะครับ

ต่อมา ก็มาถึงคำถามที่ทุกรอคอย(มั้ง) ว่าทำไมการเลื่อนกล่องในแต่ละรอบ ถึงมีคู่จุดที่จะเปรียบเทียบกันไม่เกิน 8 จุดแค่นั้นเอง โม้ให้เชื่อเล่น ๆ ป่าว… ก็มาอ่านเหตุผลดูกันครับ ขออธิบายด้วยสไลด์ดังต่อไปนี้

ที่นี้ ถ้าพูดถึงการแก้ปัญหา ผมก็ขอจบไว้เพียงเท่านี้ครับเพราะแนวคิดสำหรับปัญหานี้ มันหมดละ หลัก ๆ คือแบ่งปัญหาเป็นครึ่ง ๆ ละแก้ที่ละส่วน จากนั้นเอามารวมโดยพิจารณาเฉพาะจุดที่จำเป็นก็พอ จบ ซึ่งจริง ๆ แล้วเราจะแบ่งกี่ส่วนก็ได้นะ แต่ก็จะเขียนโค้ดให้แบ่งและรวมลำบากขึ้น อีกอย่างพอวิเคราะห์เวลาออกมาแล้วก็ได้ O(N log² N) เท่าเดิมด้วย //คิดจาก T(N) = C*T(N/C) + O(N log N) เมื่อ C ≥3 จะได้ T(N) = O(N log² N) เสมอ(ลองใช้ Tree Recursion ทดเล่น ๆ ดูก็ได้)

ฉะนั้นสำหรับผู้อ่านที่ต้องการรู้เพียงไอเดีย แนวคิดแก้ปัญหา รวมถึงหน้าตาโค้ดเบื้องต้น แนะนำให้หยุดอ่านเพียงเท่านี้ครับ เพราะต่อไปจะเป็นเรื่องไม่จำเป็นสำหรับบริบททั่วไปหน่อย ๆ (แต่ผมแนะนำให้อ่านนะ ฮ่า ๆ ๆ รู้สึกขัดแย้งในตัวเอง)

Improve algorithm

ต่อมาเราจะมาพูดถึงการทำให้เวลามันเหลือ O(N log N) กันครับ

จากอัลกอเดิมของเรา จะเห็นได้ว่าเราเสียเวลาไปกับ #เวลาการเลื่อนกล่องอย่างดีที่ใช้ไปคือ O(N log N) ทำให้ T(N) รวม ๆ เป็น O(N log² N) จากการเห็นตรงนี้ทำให้เราจะมาพยายามทำให้ #เวลาการเลื่อนกล่องอย่างดีเหลือเพียง O(N) เพราะมันจะได้ T(N) รวม ๆ เหลือแค่ O(N log N) //ใช้ Tree Recursion วิเคราะห์ดูก็ได้

จริง ๆ แล้วเราไม่จำเป็นต้องเรียงจุดในขอบเขตสีฟ้าตามแกน y ทุกรอบที่มีการเรียก ClosestPair()เลยก็ได ้เราทำเพียงแค่เรียงครั้งเดียว แล้วนำสิ่งที่เรียงไปใช้ก็พอ

กล่าวคือ เมื่อได้รับจุดมา ให้ทำตามขั้นตอนต่อไปนี้
1. สร้างอาร์เรย์ที่มีจุดเรียงตามแกน x สมมติว่าชื่อ xsort
2. สร้างอาร์เรย์ที่มีจุดเรียงตามแกน y สมมติว่าชื่อ ysort
3. เรียก ClosestPair()โดยส่ง xsort และ ysort เป็น input argument

ในขั้นตอนการ divide ก็ทำการคิดเหมือนเดิม คือแบ่งซ้ายแบ่งขวา โดยมีจุดตรงกลาง(midPoint) เป็นตัวแบ่ง จากนั้นในขั้นตอนการ Combine เราเพียงแค่นำ ysort มาใช้ตรง ๆ ตามโค้ดเทียมดังนี้

Let strip is Array[Point]       // สร้างรายการเก็บจุดไว้ ชื่อว่า strip
for each point p in ysort {     // ดูจุดแต่ละจุดใน ysort
    if |p.x - midPoint.x| < d { // ดูว่าจุดนั้น ควรอยู่ใบแถบสีฟ้าไหม
      append p to strip         // ถ้าควรก็เอาไปต่อในรายการ strip
    }
}
// เพียงเท่านี้รายการของจุดที่อยู่ในแถบสีฟ้าก็จะเรียงตามแกน y
// โดยไม่ต้องเสียเวลา sort อีกรอบแล้วนั่นเอง

ต่อมา พูดถึงในรายละเอียดของการ Divide กันต่อ เนื่องจากเราต้องส่ง xsort และ ysort ไปในการเรียก ClosestPair()ในแต่ละครั้ง ซึ่งก่อนแบ่งปัญหาไปทางซ้ายและขวา ก็ต้องจัดจุดใน ysort ของซ้ายและขวาให้มีแกน x อยู่ฝั่งที่ถูกต้องด้วย จะได้โค้ดเทียมดังนี้

Input xsort[0...n-1], ysort[0...n-1] // รับ xsort และ ysort มาเวียนเกิด
mid = floor(n/2)                     // หาพิกัดตรงกลางตามแกน x เพื่อแบ่ง
midPoint = xsort[mid]                // เก็บจุุดตรงกลางไว้(ตามพิกัดตรงกลาง)
xL = xsort[0...mid]                  // แบ่งจุดฝั่งซ้ายตามแกน x
xR = xsort[mid+1...n-1]              // แบ่งจุดฝั่งขวาตามแกน x
Let yL and yR are the Array[Point]   // ให้ yL และ yR เป็นรายการเก็บจุด
for each point p in ysort {          // ดูแต่ละจุด p ใน ysort
    if p.x <= midPoint.x {           // ดูว่าจุดนั้นอยู่ในฝั่งซ้ายไหม
      append p to yL                 // ถ้าอยู่ก็ให้ yL เก็บจุดนั้นไว้
    } else {                         
      append p to yR                 // ถ้าไม่ใช่ก็ให้ yR เก็บจุดนั้นไว้
    }
}
// เพียงเท่านี้รายการ yL และ yR ก็จะเก็บจุดฝั่งซ้ายและฝั่งขวาที่แยกตามจุดตรงกลางของแกน x
// โดยแต่ละรายการก็เรียงตามแกน y โดยไม่ต้อง sort อีกรอบแล้วนั่นเอง
dL = ClosestPair(xL, yL)             // จากนั้นก็นำไปแก้ทุกจุดในฝั่งซ้าย
dR = ClosestPair(xR, yR)             // และทุกจุดในฝั่งขวาแล้วนั่นเอง

นำแนวคิดการแบ่งและการรวมเหล่านี้ไปประยุกต์ใช้ในอัลกอเดิม ซึ่งกระบวนการทั้งหมดจะใช้เวลาเพียง O(N) เท่านั้น //มาจากการดูทีละจุดใน ysort เพื่อแบ่งซ้ายขวา และดูทีละจุดใน ysort เพื่อสร้างแถบสีฟ้า ซึ่งจำนวนจุดที่ดูก็มี N จุดนั่นเอง

จากแนวคิดทั้งหมด จะได้โค้ดดังนี้

Code C/C++: Divide and Conquer Solution for Closest Pair

จากโค้ดด้านบน จะเห็นได้ว่า แต่ละคำสั่งใน ClosestPair() ใช้เวลา O(N) ทั้งนั้น ทำให้เวลารวมของทั้งฟังก์ชันเป็น T(N)=2T(N/2) + O(N) = O(N log N) ซึ่งเร็วในระดับที่ดีมากแล้วนั่นเอง เย่~~~

เอาล่ะ สำหรับท่านผู้ที่อ่านมาถึงตรงนี้ ผมขอกราบขอบพระคุณเป็นอย่างสูงจริง ๆ และผมก็ต้องขอหยุดการเล่าไว้แต่เพียงเท่านี้ครับ //จริง ๆ ก็อยากเขียนต่อ แต่กลัวว่ามันจะยาวไปไม่ไหวแล้ว

Summary

จากปัญหาที่ใช้เวลา O(N²) เรานำแนวคิดของ Divide and Conquer มาจับก็จะได้ O(N log² N) แล้วนำไป optimize ด้วยทริคบางอย่างจนได้ O(N log N) ทั้งหมดที่ทำมานี้ ล้วนเกิดจากการพยายามที่จะทำให้อะไร ๆ มันดีขึ้น

ปัญหา Closest Pair of Point ได้สอนเราว่า การจะออกแบบอัลกอรึทึมที่ดีได้นั้นบางครั้งก็ต้องทำควบคู่ไปกับการวิเคราะห์อัลกอริทึมนะครับ :)

Postscript

โดยภาพรวมแล้วปัญหา Closest Pair เป็นการใช้ Divide and Conquer ที่แบ่งยาก และก็รวมยากครับ แต่ปัจจุบันนี้เราได้ค้นพบวิธีแก้ปัญหานี้ในเวลา O(N log N) แต่มีความเร็วในทางปฎิบัติดีกว่าวิธี Divide and Conquer อย่างมาก โค้ดก็สั้นกว่า เข้าใจก็ง่ายกว่า โดยใช้ท่าที่ชื่อว่า Line Sweep Algorithm หากว่าสนใจกันไว้ผมจะกลับมาเขียนต่อครับ