แบบจำลองฝ่ายตรงข้าม
ในวิทยาการคอมพิวเตอร์อัลกอริทึมแบบออนไลน์จะวัดความสามารถในการแข่งขันกับแบบจำลองศัตรู ที่แตกต่างกัน สำหรับอัลกอริทึมแบบกำหนดได้ ศัตรูจะเหมือนกับศัตรูแบบปรับตัวได้แบบออฟไลน์ สำหรับอัลกอริทึมแบบออนไลน์แบบสุ่ม ความสามารถในการแข่งขันอาจขึ้นอยู่กับแบบจำลองศัตรูที่ใช้
ศัตรูร่วมกัน
ศัตรูทั่วไปสามประเภท ได้แก่ ศัตรูที่ไม่รู้ตัว ศัตรูออนไลน์ที่ปรับตัวได้ และศัตรูออฟไลน์ที่ปรับตัวได้
ศัตรูที่ไม่รู้เรื่องบางครั้งเรียกว่าศัตรูที่อ่อนแอ ศัตรูประเภทนี้รู้รหัสของอัลกอริทึม แต่ไม่รู้ผลลัพธ์แบบสุ่มของอัลกอริทึม
ศัตรูออนไลน์ที่ปรับตัวได้บางครั้งเรียกว่าศัตรูระดับกลาง ศัตรูประเภทนี้ต้องตัดสินใจด้วยตนเองก่อนที่จะได้รับอนุญาตให้รู้การตัดสินใจของอัลกอริทึม
ศัตรูแบบปรับตัวได้แบบออฟไลน์บางครั้งเรียกว่าศัตรูที่แข็งแกร่ง ศัตรูประเภทนี้รู้ทุกอย่าง แม้กระทั่งตัวสร้างเลขสุ่ม ศัตรูประเภทนี้แข็งแกร่งมากจนการสุ่มไม่สามารถช่วยต่อต้านได้
ผลลัพธ์ที่สำคัญ
จาก S. Ben-David, A. Borodin , R. Karp , G. TardosและA. Wigdersonเราได้ข้อมูลดังนี้:
- หากมีอัลกอริทึมแบบสุ่มที่สามารถแข่งขันได้ในระดับ α กับคู่ต่อสู้แบบปรับตัวได้แบบออฟไลน์แล้ว ก็ย่อมมีอัลกอริทึมแบบกำหนดที่สามารถแข่งขันได้ในระดับ α เช่นกัน
- ถ้า G เป็นอัลกอริทึมแบบสุ่มที่แข่งขันได้ในระดับ c กับคู่ต่อสู้แบบปรับตัวได้ทางออนไลน์ และมีอัลกอริทึมแบบสุ่มที่แข่งขันได้ในระดับ d กับคู่ต่อสู้แบบไม่รู้ตัวแล้ว G จะเป็นอัลกอริทึมแบบสุ่มที่แข่งขันได้ในระดับ (c * d) กับคู่ต่อสู้แบบปรับตัวได้แบบออฟไลน์
ดูเพิ่มเติม
ลิงก์ภายนอก
- บรรณานุกรมบทความเกี่ยวกับอัลกอริทึมออนไลน์