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

จากวิกิพีเดีย สารานุกรมเสรี

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

การทำงาน[แก้]

ยกตัวอย่างเช่น หากเราต้องการจะหาค่ามากสุดของฟังก์ชัน f(x) และเรารู้ว่าค่ามากสุดดังกล่าวอยู่ในช่วงของ A และ B แล้ว แสดงว่าจะต้องมีค่า x บางค่า ที่

  • สำหรับ a,b ทุกค่า ซึ่ง A ≤ a < bx แล้ว จะมี f(a) < f(b) และ
  • สำหรับ a,b ทุกค่า ซึ่ง xa < 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)


อ้างอิง[แก้]


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