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}\,$ กิโลเมตร เพื่อความสะดวก คุณสามารถสมมติได้ว่า $w_{1}<w_{2}<\ldots <w_{n-1}<w_{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})\,$ (กล่าวคือจะต้องรอให้ผู้เข้าแข่งขันคนที่ได้เริ่มก่อนว่ายน้ำให้เสร็จหมดก่อน แล้วจึงได้ว่ายน้ำเอง หลังจากนั้นจึงวิ่งและว่ายน้ำ)

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