418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริืทึมแบบตะกละ I

ข้อ 1

[Kleinberg & Tardos 4.3] บริษัทรถบรรทุกบริษัทหนึ่งจัดการส่งพัสดุจากกรุงเทพฯ ไปสุไหงโกลก รถบรรทุกคันหนึ่งสามารถบรรทุกน้ำหนักได้ไม่เกิน W หน่วย ในวันหนึ่งๆ บริษัทจะได้รับกล่องพัสดุมาทีละกล่อง โดยกล่องที่ $i\,$ จะมีน้ำหนัก $w_{i}\,$ บริษัทมีนโยบายว่าของจะต้องถูกส่งตามลำดับที่บริษัทได้รับมา (กล่าวคือของที่มาก่อนจะต้องไม่ไปถึงหลังจากกล่องที่มาทีหลัง) ดังนั้นบริษัทจึงใช้อัลกอริทึมแบบ greedy ในการจัดของลงรถบรรทุกดังต่อไปนี้: บริษัทจะพยายามเอาของใส่รถบรรทุกคันหนึ่งตามลำดับที่ได้รับมาจนกระทั่งรถบรรทุกไม่สามารถบรรทุกของชิ้นต่อไปได้ แล้วจึงส่งรถบรรทุกเดินทางไปสุไหงโกลก ของที่มาหลังจากรถบรรทุกออกก็จะเอาไปใส่รถบรรทุกคันใหม่

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

เมื่อกำหนดลำดับของกล่องที่บริษัทได้รับพร้อมกับน้ำหนักของกล่องแต่ละกล่อง $w_{1},w_{2},\ldots ,w_{n}\,$ จงพิสูจน์ว่าอัลกอริทึมแบบ greedy ที่บริษัืทใช้อยู่นี้ทำให้จำนวนเที่ยวการส่งของน้อยที่สุดเท่าที่จะเป็นไปได้ การพิสูจน์ของคุณควรจะมีลักษณะคล้ายๆ กับการพิสูจน์ความถูกต้องของ greedy algorithm สำหรับแก้ปัญหา interval scheduling ซึ่งใช้เทคนิคการพิสูจน์แบบ "greedy algorithm นำหน้าเสมอ"

เฉลย

ข้อ 2

[Kleinberg & Tardos 4.4] กำหนด string $S\,$ และ $S'\,$ มาให้ เรากล่าวว่า $S'\,$ เป็น subsequence ของ $S\,$ ถ้าหากเราสามารถลบตัวอักษรบางตัวใน $S\,$ ออกแล้วได้ผลลัพธ์เท่ากับ $S'\,$ ยกตัวอย่างเช่น abc เป็น substring ของ daabaefcaf ( da ab aef c af )

จงออกแบบอัลกอริทึมที่รับสตริง $S\,$ ความยาว $m\,$ และ $S'\,$ ความยาว $n\,$ มา แล้วตอบว่า $S'\,$ เป็น subsequence ของ $S\,$ หรือไม่ ในเวลา $O(m+n)\,$

เฉลย

ข้อ 3

[Kleinberg & Tardos 4.5] ถนนชนบทแห่งหนึ่งมีบ้านเรือนตั้งอยู่ริ่มถนนอยู่ $n\,$ โดยบ้านหลังที่ $i\,$ อยู่ห่างจากต้นถนนเป็นระยะทาง $x_{i}\,$ กิโลเมตร เพื่อความสะดวก คุณสามารถสมมติได้ว่า $x_{1}<x_{2}<\ldots <x_{n-1}<x_{n}\,$

คุณต้องการตั้งสถานีส่งสัญญาณโทรศัพท์มือถือบนถนนนี้ โดยที่ทำให้บ้านทุกหลังอยู่ในรัศมี 4 กิโลเมตรของสถานีส่งสัญญาณอย่างน้อยหนึ่งสถานี

จงออกแบบอัลกอริทึมเพื่อเลือกตำแหน่งการตั้งสถานีส่งสัญญาณโทรศัพท์มือถือเพื่อให้บรรลุวัตถุประสงค์ข้างบน โดยมีจำนวนสถานีน้อยที่สุดเท่าที่จะเป็นไปได้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา $O(n)\,$

เฉลย

ข้อ 4

[Kleinberg & Tardos 4.6] ในการแข่งขันไตรกีฬาครั้งหนึ่งมีผู้เข้าแข่งขัน $n\,$ คน ผู้เข้าแข่งขันแต่ละคนจะต้องว่ายน้ำ 20 รอบในสระว่ายน้ำ ปั่นจักรยาน 10 ไมล์ แล้ววิ่ง 3 ไมล์ คุณทราบว่าผู้เข้าแข่งขันคนที่ $i\,$ จะใช้เวลาว่ายน้ำประมาณ $s(i)\,$ นาที ปั่นจักรยานประมาณ $b(i)\,$ นาที และวิ่งอีกประมาณ $r(i)\,$ นาที

สระว่ายน้ำมีอยู่เพียงแค่สระเดียว และมีกฎว่าในเวลาหนึ่งๆ จะมีผู้เข้าแข่งขันใช้สระได้เพียงคนเดียวเท่านั้น ฉะนั้นผู้จัดการแข่งขันจึงจัดการแ่ข่งขันในรูปแบบนี้ ตอนเริ่มต้นแข่งขันผู้เข้าแข่งขันที่ได้เริ่มคนแรกจะว่ายน้ำไป 20 รอบ แล้วออกจากสระไปปั่นจักรยานและวิ่งต่อ ทันใดที่ผู้เข้าแข่งขันที่ได้เริ่มคนแรกออกจากสระไป ผู้เข้าแข่งขันที่ได้เริ่มเป็นคนที่สองก็จะว่ายน้ำ และทันใดที่ผู้เข้าแข่งขันคนนั้นว่ายน้ำเสร็จ ผู้เข้าแข่งขันคนที่สามก็จะเริ่มว่ายต่อ เช่นนี้ไปเรื่อยๆ จนครบ $n\,$ คน

ดังนั้น สมมติว่าผู้จัดการแข่งขันจัดให้ผู้เข้าแข่งขันเริ่มทำการแข่งขันตามลำดับโดยให้ผู้เข้าแข่งขันคนที่ $i_{1}\,$ เริ่มเป็นคนแรก ผู้เข้าแข่งขันคนที่ $i_{2}\,$ เริ่มเป็นคนที่สอง ... และผู้เข้าแข่งขันคนที่ $i_{n}\,$ เริ่มเป็นคนสุดท้ายแล้ว เราจะได้ว่าผู้เข้าแข่งขันคนที่ $i_{k}\,$ จะทำการแข่งขันเสร็จ ณ เวลา $b(i_{k})+r(i_{k})+\sum _{j=1}^{k}s(i_{j})\,$ (กล่าวคือจะต้องรอให้ผู้เข้าแข่งขันคนที่ได้เริ่มก่อนว่ายน้ำให้เสร็จหมดก่อน แล้วจึงได้ว่ายน้ำเอง หลังจากนั้นจึงวิ่งและว่ายน้ำ)

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

เฉลย

ข้อ 5

[Kleinberg & Tardos 4.13] ร้านถ่ายเอกสารแห่งหนึ่งมีเครื่องถ่ายเอกสารเครื่องใหญ่หนึ่งเครื่อง ทุกเช้าร้านถ่ายเอกสารจะได้รับงานจากลูกค้ามาจำนวน $n\,$ งาน

งานของลูกค้าคนที่ $i\,$ จะต้องใช้เวลาทำ $t_{i}\,$ นาที โดยงานนี้จะต้องทำต่อเนื่องกันด้วยเครื่องถ่ายเอกสารตั้งแต่ต้นจนจบโดยไม่มีพัก สมมติว่าเจ้่าของร้านได้ลำดับการทำงานเสร็จแล้ว ให้ $C_{i}\,$ เป็นเวลานับตั้งแต่เริ่มต้นทำงานแรกจนถึงเวลาที่ทำงานของลูกค้าคนที่ $i\,$ เสร็จ (กล่าวคือ ถ้างานของลูกค้าคนที่ $j\,$ เป็นงานแรกที่เจ้าของร้านเลือกทำก่อน เราจะได้ว่า $C_{j}=t_{j}\,$ และถ้างานของลูกค้าคนที่ $i\,$ เป็นงานที่ถูกทำถัดมา เราจะได้ว่า $C_{i}=C_{j}+t_{i}=t_{j}+t_{i}\,$) ลูกค้าแต่ละคนจะให้ "น้ำหนัก" $w_{i}\,$ กับเวลาทำงานเสร็จ โดยความ "ไม่พึงพอใจ" ของลูกค้่าคนที่ $i\,$ สามารถวัดเป็นตัวเลขออกมาได้เท่ากับ $C_{i}w_{i}\,$

เจ้าของร้านต้องการจัดลำดับการทำงานเหล่านี้เพื่อให้ลูกค้าได้รับความพึงพอใจมากที่สุด จึงต้องการทำให้ค่า $C_{1}w_{1}+C_{2}w_{2}+\dotsb +C_{n}w_{n}\,$ มีค่าน้อยที่สุด

ยกตัวอย่างเช่น สมมติว่ามีงานสองงาน งานแรกใช้เวลา $t_{1}=1\,$ และมีน้ำหนัก $w_{1}=10\,$ ส่วนงานที่สองใช้เวลา $t_{2}=3\,$ และมีน้ำหนัก $w_{2}=2\,$ ถ้าเจ้าของร้านเลือกทำงานแรกก่อนทำงานที่สองแล้ว ความไม่พึงพอใจของลูกค้าทั้งหมดมีค่ารวมเท่ากับ $10(1)+2(4)=18\,$ แต่หากเลือกทำงานที่สองก่อนจะส่งผลให้ความไม่พึงพอใจของลูกค้าทั้งหมดมีค่าเท่ากับ $10(4)+2(3)=46\,$ ดังนั้นเจ้าของร้านควรเลือกทำงานแรกให้เสร็จก่อน

จงออกแบบอัลกอริทึัมเพื่อคำนวณลำดับการทำงานที่ทำให้ความไม่พึงพอใจรวมต่ำที่สดเท่าที่จะทำได้

เฉลย

ข้อ 6

[Kleinberg & Tardos 4.12] สมมติว่าคุณมีวิดิโอที่จะต้องส่งให้เพื่อนทั้งหมด $n\,$ ไฟล์ ทีละไฟล์ผ่าน network link เส้นหนึ่ง โดยที่ไฟล์ที่ $i\,$ มีขนาด $b_{i}\,$ บิต และคุณจะต้องส่งมันในเวลา $t_{i}\,$ วินาทีด้วยอัตราคงที่ คุณไม่สามารถส่งวิดีโอสองไฟล์ในเวลาเดียวกันได้ ดังนั้นคุณจะต้องวางแผนว่าจะส่งไฟล์ในก่อนไฟล์ไหนหลัง หลังจากคุณตัดสินใจว่าจะส่งไฟล์ไหนก่อนไฟล์ไหนหลังแล้ว คุณจะต้องส่งไฟล์ตามลำดับที่วางไว้โดยไม่ปล่อยให้ network link ว่างเลยแม้สักช่วงเวลาเดียว อนึ่ง คุณจะเริ่มส่งวิดีโอที่เวลา 0 (ดังนั้นการส่งวิดีโอทั้งหมดจะสิ้นสุดที่เวลา $\sum _{i=1}^{n}t_{i}\,$

network link ที่คุณใช้นั้นมีกฎควบคุม bandwidth ดังต่อไปนี้:

(*) สำหรับจำนวนเต็มบวก $t\,$ จำนวนบิตที่คุณส่งตั้งแต่เวลา 0 ถึงเวลา $t\,$ จะต้องไม่เกิน $rt\,$ เมื่อ $r\,$ เป็นค่าคงที่ของ network link

สังเกตว่ากฎนี้เป็นกฎที่วางไว้กับจำนวนบิตที่ส่งตั้งแต่เริ่มต้นเท่านั้น มันไม่ได้สร้างข้อจำกัดเกี่ยวกับจำนวนบิตที่คุณส่งได้หากคุณเริ่มส่ง ณ เวลาอื่น

เรากล่าวว่าการจัดลำดับการส่งวิดีโอเป็นการจัดลำดับที่ ใช้ได้ (valid) ถ้าหาว่ามันสอดคล้องกับกฎ (*)

ปัญหา: กำหนดไฟล์วิดิโอมาให้ $n\,$ ไฟล์ แต่ละไฟล์ถูกกำหนดด้วยเลข $b_{i}\,$ และ $t_{i}\,$ นอกจากนี้ยังกำหนดค่า $r\,$ ของ network link เราต้องการทราบว่ามีการจัดลำัดับการส่งที่ใช้ได้หรือไม่

ตัวอย่าง: สมมติว่าเรามีไฟล์วิดีโออยู่สามไฟล์ ได้แก่ $(b_{1},t_{1})=(2000,1),(b_{2},t_{2})=(6000,2),(b_{3},t_{3})=(2000,1)\,$ และสมมติืให้ $r=5000\,$ แล้วเราจะได้ว่าการส่งที่ส่งไฟล์ 1, 2, และ 3 ตามลำดับนั้นเป็นลำดับการส่งที่ใช้ได้ เนื่องจากมันสอดคล้องกับกฎ (*):

• เมื่อ $t=1\,$ วิดิโอที่ 1 ถูกส่งไปทั้งหมด และ $2000<5000\cdot 1\,$
• เมื่อ $t=2\,$ วิดิโอที่ 2 ถูกส่งไปครึ่งหนึ่ง และ $2000+3000<5000\cdot 2\,$

หลังจากนั้นคุณสามารถเช็คกรณีที่ $t=3\,$ และ $t=4\,$ ได้ในทำนองเดียวกัน

จงออกแบบอัลกอริทึัมสำหรับแก้ปัญหาดังกล่าว เวลากาำรทำงานของอัลกอริทึมของคุณควรจะเป็น polynomial ในตัวแปร $n\,$

เฉลย

ข้อ 7

[Kleinberg & Tardos 4.15] มีคนงานอยู่ $n\,$ ซึ่งในหนึ่งสัปดาห์จะทำงานหนึ่งกะ โดยงานหนึ่งกะจะเป็นช่วงเวลาที่ต่อเนื่องกัน (กล่าวคือกะงานของคนงานคนที่ $i\,$ สามารถแทนได้ด้วยเวลาเริ่มต้น $s_{i}\,$ และเวลาจบ ​$f_{i}\,$

หัวหน้าของคนงานเหล่านี้ต้องการเลือกคนงานจำนวนหนึ่งใน $n\,$ คนนี้มาเป็นผู้ตรวจงาน (supervisor) ซึ่งจะมาประชุมกับเขาพร้อมกันอาทิตย์ละหนึ่งครั้ง หัวหน้างานต้องการให้กลุ่มของคนงานที่เป็นผู้ตรวจงานมีคุณสมบัติดังต่อไปนี้: สำหรับคนงานที่ไม่ใช้ผู้ตรวจงานทุกคน จะต้องมีผู้ตรวจงานอย่างน้อยหนึ่งคนที่กะของผู้ตรวจงานเหลื่อมกับกะของคนงานคนนั้น เพื่อทให้กลุ่มของผู้ตรวจงานจะสามารถสังเกตการทำงานของคนงานได้ทุกคน

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

ตัวอย่าง: สมมติว่า $n=3\,$ และกะของคนงานทั้งสามคนคือ:

• วันจันทร์ 16.00 น. - 20.00 น.
• วันจันทร์ 18.00 น. - 22.00 น.
• วันจันทร์ 21.00 น. - 23.00 น.

แล้วเราจะได้ว่าเราสามารถเลือกคนงานที่ทำงานกะตั้งแต่เวลา 18.00 น. - 22.00 น. เป็นผู้ตรวจงานได้ สังเกตว่ากะของคนงานคนนี้เหลื่อมกับกะของคนงานอื่นอีกทั้งสองคน

เฉลย

ข้อ 8

[Dasgupta, Papadimitriou, Vazirani 5.32] เครื่องจักรเครื่องหนึ่งมีผู้ใช้งาน $n\,$ คน โดยผู้ใช้งานคนที่ $i\,$ จะส่งงานมาให้เครื่องจักรทำหนึ่งชื้น ซึ่งจะต้องใช้เวลาทำนาน $t(i)\,$ เครื่องจักรไม่สามารถทำงานสองชิ้นพร้อมกันได้ และเมื่อเครื่องจักรเริ่มทำงานชิ้นใดแล้วมันจะต้องทำงานชื้นนั้นจนเสร็จถึงจะไปเริ่มทำงานอื่นได้

คุณต้องการจัดลำดับการทำงาน โดยทำให้เวลาคอยรวมของผุ้ใช้ทุกคนมีค่าน้อยที่สุดเท่าที่จะทำได้ กล่าวคือ สมมติว่าคุณจัดให้เครื่องจักรทำงานของผู้ใช้ $i_{1},i_{2},\ldots ,i_{n}\,$ ตามลำดับ โดยที่ $i_{1},i_{2},\ldots ,i_{n}\,$ เป็น permutation ของเซต $\{1,2,\ldots ,n\}\,$ แล้ว ผุ้ใช้งานคนที่ $i_{k}\,$ จะต้องรอเป็นเวลา ​​​$\sum _{j=1}^{k}t(i_{j})\,$ ฉะนั้นในปัญหานี้คุณต้องการทำให้ค่า $T=\sum _{k=1}^{n}\sum _{j=1}^{k}t(i_{j})\,$ มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

จงออกแบบอัลกอริทึมเพื่อจัดลำดับการทำงานเพื่อให้บรรลุวัตถุประสงค์ดังกล่าว

เฉลย