การค้นหาแบบไตรภาค

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

 การทำงาน 

ยกตัวอย่างเช่น หากเราต้องการจะหาค่ามากสุดของฟังก์ชัน 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)

 อ้างอิง 

 บทที่ 3 การหาค่าเหมาะสมที่สุดของฟังก์ชันตัวแปรเดียว(Single Variable Optimization)

 แหล่งข้อมูลอื่น 
 ต้นไม้ค้นหาแบบทวิภาค
 การค้นโดยการประมาณช่วง

หมวดหมู่:ขั้นตอนวิธีการค้นหา
หมวดหมู่:การหาค่าเหมาะที่สุดทางคณิตศาสตร์