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

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

แก้

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


อ้างอิง

แก้


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

แก้