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

อัลกอริทึม

เราจะพิจารณาบ้านไปทีละบ้านตามตำแหน่งจากน้อยไปหามาก (กล่าวคือ พิจารณา $x_{1}\,$, $x_{2}\,$, $\ldots \,$, จนถึง $x_{n}\,$ ตามลำดับ)

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

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

เวลาเขียนโปรแกรม เราจะเขียน for loop วนโดยให้ตัวแปร $i\,$ มีค่าตั้งแต่ 1 ถึง $n\,$ และเราจะจำตำแหน่ง $y\,$ ของเสาต้นสุดท้ายที่เราตั้งเอาไว้ สำหรับบ้าน $x_{i}\,$ แต่ละหลัง เราสามารถเช็คได้ว่ามันได้รับสัญญาณโทรศัพท์หรือไม่โดยการเช็คว่า $x_{i}>y+4\,$ หรือไม่ ถ้าใช่เราก็ตั้งเสาใหม่ที่ตำแหน่ง $x_{i}+4\,$ และเปลี่ยนค่า $y\,$ เป็นค่าใหม่นี้ ตาม 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>

เห็นได้อย่างชัดเจนว่าอัลกอริทึมข้างบนทำงานในเวลา $O(n)\,$

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

สมมติว่า greedy algorithm ข้างบนตั้งเสาที่ตำแหน่ง $y_{1},y_{2},\ldots ,y_{k}\,$ โดยที่ $y_{1}<y_{2}<\dotsb <y_{k}\,$ และสมมติให้วิธีการตั้งเสาที่ใช้จำนวนเสาน้อยที่สุดตั้งเสาอยู่ที่ตำแหน่ง $y'_{1},y'_{2},\ldots ,y'_{\ell }\,$ โดยที่ $y'_{1}<y'_{2}<\dotsb <y'_{\ell }\,$ เช่นกัน สังเกตว่า $\ell \leq k\,$

lemma: สำหรับจำนวนเต็ม $i\,$ ทุกตัวที่ $1\leq i\leq \ell \,$ เราได้ว่า $y_{i}\geq y'_{i}\,$ เสมอ

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

(Base Case) ในกรณีนี้ $i=1\,$ และเราจะได้ว่าเสาที่อยู่ด้านซ้ายสุดจะต้องมีบ้าน $x_{1}\,$ อยู่ในพื้นที่ ดังนั้นเราจะได้ว่า $x_{1}+4\geq y'_{1}\,$ แต่ greedy algorithm ปักเสาที่ตำแหน่ง $x_{1}+4\,$ พอดี ดังนั้น $y_{1}\geq y'_{1}\,$

(Induction Case) สมมติให้ $y_{i}\geq y'_{i}\,$ สำหรับจำนวนเต็ม $i\,$ บางค่าที่ $i\geq 1\,$ เราต้องการแสดงว่า $y_{i+1}\geq y'_{i+1}\,$ ด้วย

สมมติเพื่อให้เกิดข้อขัดแย้งว่า $y_{i+1}<y'_{i+1}\,$ ฉะนั้นแสดงว่าจะต้องมีบ้าน $x_{j}\,$ ที่อยู่ ณ ตำแหน่ง $y_{i+1}-4\,$ พอดี

เรารู้ว่าบ้าน $x_{j}\,$ ไม่อยู่ในเขตของเสา $y_{i}\,$ (มิฉะนั้น greedy algorithm จะไม่ตั้งเสาใหม่) และเนื่องจาก $y_{i}\geq y'_{i}\,$ มันจึงไม่อยู่ในขอบเขตของเสา $y'_{i}\,$ ด้วย

นอกจากนี้ เนื่องจาก $y'_{i+1}>y_{i+1}\,$ เราจะได้ว่าบ้าน $x_{j}\,$ ไม่อยู่ในขอบเขตของเสา $y'_{i+1}\,$ ด้วย กล่าวคือหากเราวางเสาโทรศัพท์ตามวิธีที่ใช้จำนวนเสาน้อยที่สุดเท่าที่จะทำได้แล้ว บ้าน $x_{j}\,$ จะไม่อยู่ในขอบเขตของเสาต้นใดเลย เกิดข้อขัดแย้งกับข้อกำหนดที่ว่าวิธีการวางเสาที่ใช้เสาน้อยที่สุดจะต้องครอบคลุมบ้านทุกบ้าน

ฉะนั้นเราจึงสามารถสรุปได้ว่า $y_{i}\geq y'_{i}\,$ สำหรับทุกๆ $i\,$ ที่ $1\leq i\leq \ell \,$

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

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

จาก lemma เราได้ว่า $y_{\ell }\geq y'_{\ell }\,$ เนื่องจากการปักเสาที่ $y'_{1},y'_{2},\ldots ,y'_{\ell }\,$ ครอบคลุมบ้านทุกบ้าน ดังนั้นจะไม่มีบ้านใดอยู่ ณ ตำแหน่งเกิน $y'_{\ell }+4\,$ ด้วยเหตุนี้จึงไม่มีบ้านใดอยู่เกินตำแหน่ง $y_{\ell }+4\,$ ด้วย

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

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