ขั้นตอนวิธีออนไลน์

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

ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีออนไลน์ (อังกฤษ: online algorithm) เป็นขั้นตอนวิธีที่สามารถประมวลผลข้อมูลนำเข้าที่ค่อย ๆ ส่งมาเรื่อย ๆ ได้ ซึ่งแตกต่างจากขั้นตอนวิธีออฟไลน์ (อังกฤษ: offline algorithm) ซึ่งต้องรอให้รับข้อมูลนำเข้าให้หมดเสียก่อนถึงจะเริ่มประมวลผลได้ ตัวอย่างเช่นสำหรับปัญหาการเรียงข้อมูลนั้น การเรียงลำดับแบบเลือก (ขั้นตอนวิธีออฟไลน์) จะต้องรอรับข้อมูลนำเข้าให้หมดเสียก่อน จากนั้นจึงเริ่มค่อยเริ่มขั้นตอนวิธี ซึ่งจะแตกต่างจากการเรียงลำดับแบบแทรก (ขั้นตอนวิธีออนไลน์) ซึ่งสามารถนำข้อมูลตัวถัดไปที่อ่านจากข้อมูลนำเข้ามาทำการเรียงลำดับได้เลย

เนื่องจากระหว่างการดำเนินการขั้นตอนวิธีออนไลน์จะไม่รู้ข้อมูลนำเข้าทั้งหมด ขั้นตอนวิธีออนไลน์จึงจะต้องตัดสินใจการเลือกบางอย่างซึ่งหากเลือกผิดอาจทำให้คำตอบไม่ดีที่สุดได้ การศึกษาขั้นตอนวิธีออนไลน์จึงมุ่งเน้นไปที่การตัดสินใจของตัวขั้นตอนวิธีเพื่อให้ผลลัพธ์ออกมาดีที่สุดเท่าที่จะเป็นไปได้

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