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

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 13:11, 21 กันยายน 2552 โดย Aoy (คุย | มีส่วนร่วม) (→‎ข้อ 1)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

ข้อ 1

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

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

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

เฉลย

ข้อ 2

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

จงออกแบบอัลกอริทึมที่รับสตริง ความยาว และ ความยาว มา แล้วตอบว่า เป็น subsequence ของ หรือไม่ ในเวลา

เฉลย

ข้อ 3

[Kleinberg & Tardos 4.5] ถนนชนบทแห่งหนึ่งมีบ้านเรือนตั้งอยู่ริ่มถนนอยู่ โดยบ้านหลังที่ อยู่ห่างจากต้นถนนเป็นระยะทาง กิโลเมตร เพื่อความสะดวก คุณสามารถสมมติได้ว่า

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

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

เฉลย

ข้อ 4

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

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

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

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

เฉลย

ข้อ 5

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

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

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

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

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

เฉลย

ข้อ 6

[Kleinberg & Tardos 4.12] สมมติว่าคุณมีวิดิโอที่จะต้องส่งให้เพื่อนทั้งหมด ไฟล์ ทีละไฟล์ผ่าน network link เส้นหนึ่ง โดยที่ไฟล์ที่ มีขนาด บิต และคุณจะต้องส่งมันในเวลา วินาทีด้วยอัตราคงที่ คุณไม่สามารถส่งวิดีโอสองไฟล์ในเวลาเดียวกันได้ ดังนั้นคุณจะต้องวางแผนว่าจะส่งไฟล์ในก่อนไฟล์ไหนหลัง หลังจากคุณตัดสินใจว่าจะส่งไฟล์ไหนก่อนไฟล์ไหนหลังแล้ว คุณจะต้องส่งไฟล์ตามลำดับที่วางไว้โดยไม่ปล่อยให้ network link ว่างเลยแม้สักช่วงเวลาเดียว อนึ่ง คุณจะเริ่มส่งวิดีโอที่เวลา 0 (ดังนั้นการส่งวิดีโอทั้งหมดจะสิ้นสุดที่เวลา

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

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

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

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

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

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

  • เมื่อ วิดิโอที่ 1 ถูกส่งไปทั้งหมด และ
  • เมื่อ วิดิโอที่ 2 ถูกส่งไปครึ่งหนึ่ง และ

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

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

เฉลย

ข้อ 7

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

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

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

ตัวอย่าง: สมมติว่า และกะของคนงานทั้งสามคนคือ:

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

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

เฉลย

ข้อ 8

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

คุณต้องการจัดลำดับการทำงาน โดยทำให้เวลาคอยรวมของผุ้ใช้ทุกคนมีค่าน้อยที่สุดเท่าที่จะทำได้ กล่าวคือ สมมติว่าคุณจัดให้เครื่องจักรทำงานของผู้ใช้ ตามลำดับ โดยที่ เป็น permutation ของเซต แล้ว ผุ้ใช้งานคนที่ จะต้องรอเป็นเวลา ​​​ ฉะนั้นในปัญหานี้คุณต้องการทำให้ค่า มีค่าน้อยที่สุดเท่าที่จะเป็นไปได้

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

เฉลย