ผู้ใช้:Kaiimook/กระบะทราย

ปัญหาการหาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด[แก้]

ปัญหาการหาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด (Closest pair problem) เป็นหนึ่งในงานวิจัยทางด้านเรขาคณิตคำนวณ (Computational Geometry) จากปัญหานี้ถ้าใช้วิธีการหาระยะทางที่ใกล้ที่สุดกับจุดทุกๆ จุด นั้นจะต้องใช้เวลาเป็น Θ(n2) จากเวลาการทำงานยังเป็นเวลาที่สูง จึงได้ทำการแก้ปัญหานี้ซึ่งใช้วิธีการแบ่งแยกและเอาชนะ (Divide and Conquer) โดยที่เวลาการทำงานเป็น O(nlogn) และอัลกอริทึมนี้เป็นอัลกอริทึมแบบอนุกรมที่ดีที่สุดสำหรับปัญหานี้

ลักษณะของปัญหา[แก้]

โจทย์ : ให้จุด N จุด ซึ่งอยู่บนระนาบ คำตอบ : หาระยะทางระหว่างคู่จุดที่ใกล้กันที่สุด โดยมีสูตรการหาระยะทางระหว่างจุด 2 จุด คือ di.j =sqrt[(x_i-x_j)² + (y_i-y_j)² ]{2}

ปัญหารูปแบบต่างๆ[แก้]

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

วิธีการแก้ปัญหาแบบ 2 มิติ[แก้]

ขั้นตอนวิธีการแบบบรูทฟอร์ซ (Brute force) : ทำการตรวจสอบระยะทางในทุกๆจุด และนำมาคำนวณหาระยะทางที่มีค่าน้อยที่สุด เป็นวิธีที่ธรรมดาที่สุด โดยตรวจสอบทั้งหมด n(n-1)/2 คู่ และใช้เวลาการทำงานเป็น Θ(n2)

รหัสเทียม :[แก้]

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

ขั้นตอนวิธีการแบบแบ่งแยกและเอาชนะ (Divide and Conquer) :

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

ลำดับขั้นตอน :[แก้]

ให้ x เป็นค่าน้อยที่สุดจากระยะทางที่หาได้จากข้อ 2)
พิจารณาจากจุดทุกๆจุดซึ่งอยู่บริเวณที่ห่างจากเส้นกั้นกลาง 2 ฝั่ง ด้วยความยาวไม่เกิน x
เรียงลำดับระยะห่างของจุดทุกๆจุดในบริเวณนั้น โดยเก็บข้อมูลเป็นพิกัดทั้งแนวนอนและแนวตั้ง ซึ่งเป็นการทำให้สามารถระบุได้ว่าจุดใดอยู่ทางฝั่งซ้ายหรือฝั่งขวา
สร้างกรอบสี่เหลี่ยม ขนาด x * 2x ขึ้นมาบนพื้นที่นั้น ใช้เลื่อนไปตามจุด n คู่ เพื่อนหาระยะที่ใกล้กันที่สุด

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

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

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

วิธีการนี้ใช้เวลาการทำงานเป็น Θ(nlogn)

มาจาก t(n) = 2t(n/2) + Θ(n) = Θ(nlogn) โดย 2t(n/2) มาจากการเรียกซ้ำใน 2 รอบ ในพื้นสี่ฝั่งซ้ายและฝั่งขวา และ Θ(n) มาจากการเอาสี่เหลี่ยมเทียบกับจุดจำนวน n คู่

การนำไปใช้งาน[แก้]

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