ปัญหาการอัปเดตรายการ

ปัญหา การอัปเดตรายการหรือปัญหาการเข้าถึงรายการเป็นแบบจำลองง่ายๆ ที่ใช้ในการศึกษาการวิเคราะห์เชิงแข่งขันของอัลกอริทึมออนไลน์โดยกำหนดให้มีชุดของรายการในลิสต์ที่ต้นทุนในการเข้าถึงแต่ละรายการเป็นสัดส่วนกับระยะห่างจากหัวลิสต์ เช่นลิสต์แบบเชื่อมโยงและมีลำดับการร้องขอการเข้าถึง ปัญหาคือการคิดค้นกลยุทธ์ในการจัดเรียงลำดับใหม่ของลิสต์เพื่อให้ต้นทุนรวมของการเข้าถึงน้อยที่สุด การจัดเรียงลำดับใหม่สามารถทำได้ทุกเมื่อ แต่จะมีค่าใช้จ่าย แบบจำลองมาตรฐานประกอบด้วยการดำเนินการจัดเรียงลำดับใหม่สองแบบ:

การสลับตำแหน่งของรายการที่เข้าถึงได้โดยอิสระไปยังตำแหน่งใดก็ได้ข้างหน้าตำแหน่งปัจจุบัน
การแปลงค่าแบบเสียค่าใช้จ่ายของต้นทุนต่อหน่วยสำหรับการแลกเปลี่ยนสินค้าสองรายการที่อยู่ติดกันในรายการ

ประสิทธิภาพของอัลกอริธึมขึ้นอยู่กับการสร้างลำดับคำขอโดยฝ่ายตรงข้ามภายใต้แบบจำลองฝ่ายตรงข้าม ต่างๆ

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

นอกเหนือจากการใช้งานดั้งเดิมแล้ว ปัญหาดังกล่าวได้รับการเสนอแนะว่ามีความคล้ายคลึงอย่างมากกับปัญหาการปรับปรุงบริบทโดยรวมและความสามารถในการบีบอัดหลังจากการแปลง Burrows–Wheeler (BWT ) หลังจากการแปลงนี้ ไฟล์มักจะมีบริเวณขนาดใหญ่ที่มีความถี่สูงในระดับท้องถิ่น และประสิทธิภาพการบีบอัดจะดีขึ้นอย่างมากด้วยเทคนิคที่มักจะย้ายอักขระที่เกิดขึ้นบ่อยไปทางศูนย์ หรือไปทางด้านหน้าของ "รายการ" ด้วยเหตุนี้ วิธีการและรูปแบบต่างๆ ของ Move-to-Front และการนับความถี่จึงมักใช้ตามอัลกอริทึม BWT เพื่อปรับปรุงความสามารถในการบีบอัด

แบบจำลองฝ่ายตรงข้าม

ศัตรูคือหน่วยงานที่มีสิทธิ์เลือกลำดับการร้องขอ $\sigma$ สำหรับอัลกอริทึมALGนั้น ขึ้นอยู่กับว่า $\sigma$ สามารถเปลี่ยนแปลงได้ตามกลยุทธ์ของALG โดย ฝ่ายตรงข้ามจะได้รับพลังอำนาจที่แตกต่างกัน และประสิทธิภาพของALGจะถูกวัดเทียบกับฝ่ายตรงข้ามเหล่านั้น

ศัตรูที่ไม่รู้เรื่องจะต้องสร้างลำดับคำขอทั้งหมดขึ้นมาเอง $\sigma$ ก่อนที่จะเรียกใช้ALGและชำระราคาออฟไลน์ที่เหมาะสมที่สุด $OPT(\sigma )$ ซึ่งเมื่อเปรียบเทียบกับ $ALG(\sigma )$

ศัตรูออนไลน์ที่ปรับตัวได้จะสามารถส่งคำขอครั้งต่อไปโดยอิงจากผลลัพธ์ก่อนหน้าของอัลกอริธึมออนไลน์ แต่จะชำระค่าคำขออย่างเหมาะสมและทางออนไลน์

ฝ่ายตรงข้ามแบบปรับตัวได้ที่ทำงานแบบออฟไลน์จะสามารถทำการร้องขอครั้งต่อไปโดยอิงจากผลลัพธ์ก่อนหน้าของอัลกอริธึมออนไลน์ได้ แต่จะต้องจ่ายค่าใช้จ่ายแบบออฟไลน์ที่เหมาะสมที่สุด

อัลกอริทึมแบบออฟไลน์

การ วิเคราะห์เชิงแข่งขันสำหรับปัญหาการอัปเดตรายการจำนวนมากดำเนินการโดยไม่มีความรู้เฉพาะเจาะจงเกี่ยวกับลักษณะที่แน่นอนของอัลกอริทึมออฟไลน์ที่เหมาะสมที่สุด (OPT) มีอัลกอริทึมที่ทำงานในเวลา O( n²m ( ^m - 1)!) และพื้นที่ O( m !) โดยที่ nคือความยาวของลำดับคำขอและmคือความยาวของรายการ^{[ 1 ]} อัลกอริทึมออฟไลน์ที่เหมาะสมที่สุดที่เป็นที่รู้จักซึ่งขึ้นอยู่กับความยาวของลำดับคำขอทำงานในเวลา O(m²(m-1)!n) ซึ่งอ้างโดย ดร. ศรีคริชนัน ดิวาการัน ในปี 2557 ^{[ 2 ]}

โดยทั่วไปแล้ว การสลับตำแหน่งแบบเสียค่าใช้จ่ายนั้นจำเป็นสำหรับอัลกอริทึมที่เหมาะสมที่สุด ลองพิจารณาลิสต์ ( a , b , c ) โดยที่aอยู่ที่หัวของลิสต์ และลำดับคำขอc , b , c , bอัลกอริทึมแบบออฟไลน์ที่เหมาะสมที่สุดโดยใช้การแลกเปลี่ยนฟรีเท่านั้นจะมีค่าใช้จ่าย 9 (3+3+2+1) ในขณะที่อัลกอริทึมแบบออฟไลน์ที่เหมาะสมที่สุดโดยใช้การแลกเปลี่ยนแบบเสียค่าใช้จ่ายเท่านั้นจะมีค่าใช้จ่าย 8 ดังนั้น เราจึงไม่สามารถใช้การสลับตำแหน่งฟรีเพียงอย่างเดียวสำหรับอัลกอริทึมแบบออฟไลน์ที่เหมาะสมที่สุดได้

ปัญหาการอัปเดตรายการที่เหมาะสมที่สุดได้รับการพิสูจน์แล้วว่าเป็นปัญหาNP -hardโดย( Ambühl 2000 )

อัลกอริทึมออนไลน์

อัลกอริทึมออนไลน์ALGมีอัตราส่วนการแข่งขันcถ้าสำหรับอินพุตใดๆ มันทำงานได้ดีอย่างน้อยเท่ากับ แย่กว่า OPT cเท่า กล่าวคือ ถ้ามีอยู่จริง $\alpha \geq 0$ โดยที่สำหรับลำดับคำขอที่มีความยาวจำกัดทั้งหมด $\sigma$ , $ALG(\sigma )-c.OPT(\sigma )\leq \alpha$ อัลกอริทึมออนไลน์อาจเป็นแบบกำหนดได้หรือแบบสุ่ม และปรากฏว่าการสุ่มในกรณีนี้สามารถช่วยได้อย่างแท้จริงในการป้องกันศัตรูที่ไม่รู้ตัว

กำหนดได้แน่นอน

อัลกอริทึมเชิงกำหนดส่วนใหญ่เป็นรูปแบบต่างๆ ของอัลกอริทึมสามแบบนี้ :

MTF (Move to front): หลังจากเข้าถึงรายการใดรายการหนึ่งแล้ว ให้ย้ายรายการนั้นไปไว้ด้านหน้าสุดของรายการโดยไม่เปลี่ยนแปลงลำดับของรายการอื่นๆ
ทรานส์ (สลับตำแหน่ง): หลังจากเข้าถึงรายการใดรายการหนึ่งแล้ว ให้สลับตำแหน่งของรายการนั้นกับรายการที่อยู่ก่อนหน้าทันที
FC (จำนวนความถี่): สำหรับแต่ละรายการ ให้บันทึกจำนวนครั้งที่เข้าถึงรายการนั้น เมื่อมีการเข้าถึงรายการใด ให้เพิ่มจำนวนครั้งที่เข้าถึงรายการนั้น และจัดเรียงลำดับรายการใหม่ตามลำดับความถี่ที่ลดลง

โปรดสังเกตว่าทั้งหมดนี้ใช้การสลับตำแหน่งแบบอิสระเท่านั้น ปรากฏว่าทั้ง TRANS และ FC ไม่สามารถแข่งขันได้ ในผลลัพธ์คลาสสิกที่ใช้การวิเคราะห์วิธีศักยภาพ( Sleator & Tarjan 1985 )พิสูจน์แล้วว่า MTF สามารถแข่งขันได้ในระดับ 2 การพิสูจน์นี้ไม่จำเป็นต้องมีความรู้เกี่ยวกับ OPT อย่างชัดเจนแต่จะนับจำนวนการผกผัน กล่าวคือ องค์ประกอบที่ปรากฏในลำดับตรงกันข้ามในรายการของ MTF และ OPT

อัลกอริทึมเชิงกำหนดใดๆ ก็ตามจะมีค่าขอบล่างเท่ากับ $2-{\frac {2}{l+1}}$ สำหรับรายการที่มีความยาวlและ MTF นั้นเป็นอัลกอริธึมการอัปเดตรายการแบบกำหนดได้ที่ดีที่สุด ประเภทของศัตรูไม่สำคัญในกรณีของอัลกอริธึมแบบกำหนดได้ เพราะศัตรูสามารถรันสำเนาของอัลกอริธึมแบบกำหนดได้ด้วยตนเองเพื่อคำนวณลำดับที่เลวร้ายที่สุดล่วงหน้าได้

สุ่ม

พิจารณาอัลกอริทึมแบบสุ่ม อย่างง่ายต่อไปนี้ :

นิดหน่อย: สำหรับแต่ละรายการในลิสต์ ให้เก็บค่าบิตไว้ กำหนดค่าเริ่มต้นให้กับบิตทั้งหมดแบบสุ่มและสม่ำเสมอเป็น 0 หรือ 1 เมื่อมีการเข้าถึงรายการใดรายการหนึ่ง ให้เปลี่ยนค่าบิต ถ้าค่าเป็น 1 ให้ย้ายรายการนั้นไปไว้ด้านหน้าสุด มิฉะนั้นไม่ต้องทำอะไร

อัลกอริทึมนี้แทบจะไม่เป็นแบบสุ่มเลย - มันทำการเลือกแบบสุ่มทั้งหมดในตอนเริ่มต้น ไม่ใช่ระหว่างการทำงาน ปรากฏว่า BIT ทำลายขอบเขตของความแน่นอน - มันดีกว่า MTF เมื่อเผชิญหน้ากับศัตรูที่ไม่รู้ตัว มันมีความสามารถในการแข่งขัน 7/4 มีอัลกอริทึมแบบสุ่มอื่นๆ ที่ทำงานได้ดีกว่า BIT ในปี 1995 Albers และคณะได้นำเสนออัลกอริทึมแบบสุ่มที่มีอัตราส่วนการแข่งขัน 1.6 ^{[ 3 ]} Boris Teia ได้พิสูจน์ขอบเขตล่างของ 1.5 สำหรับอัลกอริทึมการอัปเดตรายการแบบสุ่มใดๆ^{[ 4 ]}

ปัญหาที่เกี่ยวข้อง

ปัญหาการอัปเดตรายการที่อาจมีการแทรกและลบองค์ประกอบเรียกว่าปัญหาการอัปเดตรายการแบบไดนามิก ซึ่งแตกต่างจากปัญหาการอัปเดตรายการแบบคงที่ที่อนุญาตให้เข้าถึงเฉพาะองค์ประกอบในรายการเท่านั้น ขอบล่างของ $2-{\frac {2}{l+1}}$ ใช้ได้กับแบบจำลองไดนามิกเช่นกัน

นอกจากนี้ยังมีโมเดลต้นทุนที่แตกต่างกันอีกด้วย ในโมเดลต้นทุนแบบเต็มตามปกติ การเข้าถึงองค์ประกอบที่ตำแหน่งi จะ มีต้นทุนiแต่การเปรียบเทียบครั้งสุดท้ายนั้นหลีกเลี่ยงไม่ได้สำหรับอัลกอริทึมใดๆ กล่าวคือ มี องค์ประกอบ i-1ตัวขวางทางi อยู่ ในโมเดลต้นทุนแบบบางส่วน ต้นทุนการเปรียบเทียบครั้งสุดท้ายเหล่านี้ซึ่งรวมกันแล้วเท่ากับจำนวนองค์ประกอบในลำดับการร้องขอจะถูกละเลย สำหรับต้นทุนของการสลับตำแหน่งที่เสียค่าใช้จ่ายนอกเหนือจากหนึ่งหน่วยจะใช้โมเดลP ^d

ดูเพิ่มเติม

หมายเหตุ

↑ N. Reingold และ J. Westbrook. อัลกอริทึมแบบออฟไลน์ที่เหมาะสมที่สุดสำหรับกฎการอัปเดตรายการและการแบ่งหน้า รายงานทางเทคนิค YALE/DcS/TR-805 มหาวิทยาลัยเยล นิวเฮเวน รัฐคอนเนตทิคัต สิงหาคม 1990
↑ Divakaran, Srikrishnan (2014-04-30). "อัลกอริทึมแบบออฟไลน์ที่เหมาะสมที่สุดสำหรับการอัปเดตรายการ". arXiv : 1404.7638 [ cs.DS ]
↑ Albers, Susanne; Von Stengel, Bernhard; Werchner, Ralph (1995). "อัลกอริทึม BIT และ TIMESTAMP แบบผสมผสานสำหรับปัญหาการอัปเดตรายการ" Information Processing Letters . 56 (3): 135– 139. doi : 10.1016/0020-0190(95)00142-Y .
↑ Teia, Boris, ขอบเขตล่างสำหรับอัลกอริทึมการอัปเดตรายการแบบสุ่ม, Inf. Process. Lett. (1993), หน้า 5-9

[1] N. Reingold และ J. Westbrook. อัลกอริทึมแบบออฟไลน์ที่เหมาะสมที่สุดสำหรับกฎการอัปเดตรายการและการแบ่งหน้า รายงานทางเทคนิค YALE/DcS/TR-805 มหาวิทยาลัยเยล นิวเฮเวน รัฐคอนเนตทิคัต สิงหาคม 1990

[2] Divakaran, Srikrishnan (2014-04-30). "อัลกอริทึมแบบออฟไลน์ที่เหมาะสมที่สุดสำหรับการอัปเดตรายการ". arXiv : 1404.7638 [ cs.DS ]

[3] Albers, Susanne; Von Stengel, Bernhard; Werchner, Ralph (1995). "อัลกอริทึม BIT และ TIMESTAMP แบบผสมผสานสำหรับปัญหาการอัปเดตรายการ" Information Processing Letters . 56 (3): 135– 139. doi : 10.1016/0020-0190(95)00142-Y .

[4] Teia, Boris, ขอบเขตล่างสำหรับอัลกอริทึมการอัปเดตรายการแบบสุ่ม, Inf. Process. Lett. (1993), หน้า 5-9

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]