อัลกอริทึม

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

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

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

เวลาเขียนโปรแกรม เราจะเขียน for loop วนโดยให้ตัวแปร $i\,$ มีค่าตั้งแต่ 1 ถึง และเราจะจำตำแหน่ง $y\,$ ของเสาต้นสุดท้ายที่เราตั้งเอาไว้ สำหรับบ้าน $x_{i}\,$ แต่ละหลัง เราสามารถเช็คได้ว่ามันได้รับสัญญาณโทรศัพท์หรือไม่โดยการเช็คว่า $x_{i}>y+4\,$ หรือไม่ ถ้าใช่เราก็ตั้งเสาใหม่ที่ตำแหน่ง $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

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}<\dotsb <y_{k}\,$ และสมมติให้วิธีการตั้งเสาที่ใช้จำนวนเสาน้อยที่สุดตั้งเสาอยู่ที่ตำแหน่ง $y'_{1},y'_{2},\ldots ,y'_{\ell }\,$ โดยที่ $y'_{1}<y'_{2}<\dotsb <y'_{\ell }\,$ เช่นกัน สังเกตว่า

lemma: สำหรับจำนวนเต็ม $i\,$ ทุกตัวที่ เราได้ว่า $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

y_{i}\geq y'_{i}\,

เสมอ

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

(Base Case) ในกรณีนี้ และเราจะได้ว่าเสาที่อยู่ด้านซ้ายสุดจะต้องมีบ้าน $x_{1}\,$ อยู่ในพื้นที่ ดังนั้นเราจะได้ว่า แต่ greedy algorithm ปักเสาที่ตำแหน่ง $x_{1}+4\,$ พอดี ดังนั้น $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

y_{1}\geq y'_{1}\,

(Induction Case) สมมติให้ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

y_{i}\geq y'_{i}\,

สำหรับจำนวนเต็ม บางค่าที่ เราต้องการแสดงว่า

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 241175049 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Wed, 08 Jul 2026 21:43:55 GMT Sensitive client information IP address: 158.108.32.49

ด้วย

สมมติเพื่อให้เกิดข้อขัดแย้งว่า $y_{i+1}<y'_{i+1}\,$ ฉะนั้นแสดงว่าจะต้องมีบ้าน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

x_{j}\,

ที่อยู่ ณ ตำแหน่ง พอดี

เรารู้ว่าบ้าน ไม่อยู่ในเขตของเสา $y_{i}\,$ (มิฉะนั้น greedy algorithm จะไม่ตั้งเสาใหม่) และเนื่องจาก $y_{i}\geq y'_{i}\,$ มันจึงไม่อยู่ในขอบเขตของเสา $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

y'_{i}\,

ด้วย

นอกจากนี้ เนื่องจาก $y'_{i+1}>y_{i+1}\,$ เราจะได้ว่าบ้าน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

x_{j}\,

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

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 147177171 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Wed, 08 Jul 2026 21:43:57 GMT Sensitive client information IP address: 158.108.32.49

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

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

ทฤษฎีบท: Greedy algorithm ใช้เสาเป็นจำนวนน้อยที่สุดเท่าที่จะเป็นไปได้ กล่าวคือ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

\ell =k\,

พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่า $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

\ell <k\,

จาก lemma เราได้ว่า $y_{\ell }\geq y'_{\ell }\,$ เนื่องจากการปักเสาที่ $y'_{1},y'_{2},\ldots ,y'_{\ell }\,$ ครอบคลุมบ้านทุกบ้าน ดังนั้นจะไม่มีบ้านใดอยู่ ณ ตำแหน่งเกิน $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

y'_{\ell }+4\,

ด้วยเหตุนี้จึงไม่มีบ้านใดอยู่เกินตำแหน่ง ด้วย

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

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

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

อัลกอริทึม

Error

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

Error

Error

Error

Error

Error

Error

Error

Error

Error

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

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ