ผู้ใช้:TornXero/ทดลองเขียน

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

การค้นหาแบบไตรภาค (อังกฤษ: Ternacy 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)

อ้างอิง

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

แหล่งข้อมูลอื่น

• Binary search (can be used to search for where the derivative changes in sign)
• Newton's method in optimization (can be used to search for where the derivative is zero)
• Golden section search (similar to ternary search, useful if evaluating f takes most of the time per iteration)
• Interpolation search
• Linear search