การค้นหาแบบไตรภาค
การค้นแบบไตรภาค (อังกฤษ: Ternary search) เป็นกลวิธีหนึ่งในสาขาวิชาวิทยาการคอมพิวเตอร์ สำหรับค้นหาค่า มากสุดหรือน้อยสุด ของฟังก์ชันฐานนิยมเดียว (อังกฤษ: unimodal function) โดยการค้นแบบไตรภาคกำหนดว่า หากแบ่งช่วงของโดเมนของฟังก์ชันออกเป็นสามช่วงคือ ช่วงที่หนึ่ง สอง และสามแล้ว ค่ามากสุดหรือน้อยสุดของฟังก์ชันดังกล่าวจะต้องอยู่ในช่วงที่สองของโดเมน จากนั้นก็ทำการกำหนดขอบเขตของช่วงใหม่โดยทำการแบ่งช่วงที่สองของเดิมเป็นทั้งหมดสามช่วงอีกครั้งหนึ่งและทำการวนซ้ำตามขั้นตอนเดิม กลวิธีการค้นแบบไตรภาคนี้ เป็นหนึ่งในตัวอย่างการใช้แนวคิดขั้นตอนวิธีแบบแบ่งแยกและเอาชนะ (อังกฤษ: Divide and Conquer)
การทำงาน แก้
ยกตัวอย่างเช่น หากเราต้องการจะหาค่ามากสุดของฟังก์ชัน f(x) และเรารู้ว่าค่ามากสุดดังกล่าวอยู่ในช่วงของ A และ B แล้ว แสดงว่าจะต้องมีค่า x บางค่า ที่
- สำหรับ a,b ทุกค่า ซึ่ง A ≤ a < b ≤ x แล้ว จะมี f(a) < f(b) และ
- สำหรับ a,b ทุกค่า ซึ่ง x ≤ a < b ≤ B แล้ว จะมี f(a) > f(b)
เวลาการทำงาน แก้
T(n) = T(2/3 * n) + c
Θ(log n)
ตัวอย่างขั้นตอนวิธีแบบเรียกซ้ำ แก้
# สร้างฟังก์ชันแบบเรียกซ้ำชื่อ ternarySearch
# left,right ระบุขอบซ้ายและขวาของช่วง
def ternarySearch(f, left, right, absolutePrecision):
#ค่ามากสุด หรือ น้อยสุด จะอยู่ระหว่างช่วง left และ right
if (right - left) < absolutePrecision:
return (left + right)/2
leftThird = (2*left + right)/3
rightThird = (left + 2*right)/3
if f(leftThird) < f(rightThird):
return ternarySearch(f, leftThird, right, absolutePrecision)
return ternarySearch(f, left, rightThird, absolutePrecision)
อ้างอิง แก้