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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

อัลกอริทึม

เราจะพิจารณาบ้านไปทีละบ้านตามตำแหน่งจากน้อยไปหามาก (กล่าวคือ พิจารณา , ,

Error

Too many requests (f061ab2)

Wikimedia Status
, จนถึง ตามลำดับ)

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

ยกตัวอย่างเช่น ถ้าสมมติว่ามีบ้านตั้งอยู่ที่ตำแหน่ง 2, 3, 5, 10, 11, 15, 20 แล้วเราจะทำการตั้งเสาหนึ่งต้นที่ตำแหน่ง 6 = 2+4 และ 15 = 11+4 และ 24 = 20+4 เป็นต้น

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

<geshi lang="c"> y = -INFINITY // หรืออาจจะให้ y เป็นค่าใดก็ได้ที่ทำให้ y+4 < x[1] for i = 1 to n do {

   if x[i] > y then
   {
       ตั้งเสาใหม่ที่ x[i]+4
       y = x[i] + 4
   }

} </geshi>

เห็นได้อย่างชัดเจนว่าอัลกอริทึมข้างบนทำงานในเวลา

ความถูกต้องของอัลกอริทึม

สมมติว่า greedy algorithm ข้างบนตั้งเสาที่ตำแหน่ง โดยที่

Error

Too many requests (f061ab2)

Wikimedia Status
และสมมติให้วิธีการตั้งเสาที่ใช้จำนวนเสาน้อยที่สุดตั้งเสาอยู่ที่ตำแหน่ง โดยที่ เช่นกัน สังเกตว่า


lemma: สำหรับจำนวนเต็ม ทุกตัวที่ เราได้ว่า เสมอ

พิสูจน์: เราจะพิสูจน์โดยใช้ induction บนตัวแปร

(Base Case) ในกรณีนี้ และเราจะได้ว่าเสาที่อยู่ด้านซ้ายสุดจะต้องมีบ้าน อยู่ในพื้นที่ ดังนั้นเราจะได้ว่า แต่ greedy algorithm ปักเสาที่ตำแหน่ง พอดี ดังนั้น

(Induction Case) สมมติให้ สำหรับจำนวนเต็ม บางค่าที่ เราต้องการแสดงว่า ด้วย

สมมติเพื่อให้เกิดข้อขัดแย้งว่า ฉะนั้นแสดงว่าจะต้องมีบ้าน ที่อยู่ ณ ตำแหน่ง พอดี

เรารู้ว่าบ้าน ไม่อยู่ในเขตของเสา (มิฉะนั้น greedy algorithm จะไม่ตั้งเสาใหม่) และเนื่องจาก มันจึงไม่อยู่ในขอบเขตของเสา

Error

Too many requests (f061ab2)

Wikimedia Status
ด้วย

นอกจากนี้ เนื่องจาก

Error

Too many requests (f061ab2)

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

ฉะนั้นเราจึงสามารถสรุปได้ว่า สำหรับทุกๆ ที่


ทฤษฎีบท: Greedy algorithm ใช้เสาเป็นจำนวนน้อยที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ

พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่า

จาก lemma เราได้ว่า

Error

Too many requests (f061ab2)

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

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

ดังนั้น และ greedy algorithm ใช้จำนวนเสาน้อยที่สุดเท่าที่จะเป็นไปได้

รายการเลือกการนำทาง