418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 9

อัลกอริทึม

เราออกแบบอัลกอริทึมที่ใช้แก้ปัญหาโจทย์ข้อนี้ด้วยเทคนิค divide and conquer ในขั้นแรก เราจะสมมติว่าเรามีอัลกอริทึมที่สามารถแก้ปัญหานี้ได้อยู่แล้ว และเราจะเรียกชื่อมันว่า $\mathrm {Majority} \,$ โดยมันจะรับบัตร ATM $c_{1},c_{2},\ldots ,c_{n}\,$ เป็นอินพุต และจะส่งข้อมูลออกตามเงื่อนไขดังต่อไปนี้

• ถ้าหากในกลุ่มของบัตร ATM ที่ให้ไม่มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})=\mathrm {NONE} \,$ โดยที่ $\mathrm {NONE} \,$ เป็นค่าพิเศษค่าหนึ่งที่ไม่ตรงกับบัตร ATM ใดๆ เลย
• ถ้าหากในกลุ่มของบัตร ATM ที่ให้มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})=x\,$ เมื่อ $x\,$ เป็นบัตร ATM บัตรหนึ่งในกลุ่มของบัตรนั้น

เมื่อได้สมมติเช่นนั้นแล้ว รายละเอียดของ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะเป็นดังต่อไปนี้

• DIVIDE: แบ่งบัตร ATM ที่ได้รับมาออกเป็นสองกลุ่ม ได้แก่ $c_{1},c_{2},\ldots ,c_{h}\,$ และ $c_{h+1},c_{h+2},\ldots ,c_{n}\,$ เมื่อ $h=\lfloor n/2\rfloor \,$

  พึงระลึกว่า เราจะไม่สามารถแบ่งปัญหาออกเป็นปัญหาย่อยเช่นนี้ได้ถ้า $n=1\,$ ในกรณีนี้เราจะืคืนค่า $c_{1}\,$ กลับไป กล่าวคืือ $\mathrm {Majority} (c_{1})=c_{1}\,$

• CONQUER: เรียก $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{h})\,$ และสมมติให้ผลลัพธ์ของมันเป็น $x_{1}\,$ หลังจากนั้นเรียก $\mathrm {Majority} (c_{h+1},c_{h+2},\ldots ,c_{n})\,$ และสมมติให้ผลลัพธ์เป็น $x_{2}\,$

• COMBINE: ตรวจสอบว่าระหว่าง $x_{1}\,$ กับ $x_{2}\,$ ตัวใดกันแน่ที่เป็นมีกลุ่มบัตร ATM ที่สมมูลกับมันมากกว่า $n/2\,$ ใบ ซึ่งการตรวจสอบสามารถทำได้โดยการนำเอา $x_{1}\,$ ไปตรวจเช็คความสมมูลกับบัตร ATM อื่นๆ ทุกบัตร แล้วนับว่ามีบัตรที่สมมูลกับมันกี่บัตร แล้วจึงทำเช่นเดียวกันกับ $x_{2}\,$ หลังจากนั้นเราจึงคืนบัตรที่มีจำนวนบัตรที่สมมูลกับมันมากกว่า $n/2\,$ กลับไป (จะมีบัตรนี้ได้เพียงบัตรเดียวเท่านั้น)

อัลกอริืทึมที่อธิบายมาข้างบนสามารถเขียนเป็น pseudocode ได้ดังต่อไปนี้ <geshi lang="c"> Majority(c[1], c[2], ..., c[n]) {

   if n = 1 then
       return c[1]
   else
   {
       h = n/2
       x1 = Majority(c[1], c[2], ..., c[h])
       x2 = Majority(c[h+1], c[h+2], ..., c[n])
       
       x1count = 0
       if x1 != NONE then
       {            
           for i = 1 to n do
                if TEST_EQUIVALENCE(x1, c[i]) = true then
                    x1count = x1count + 1
       }

       x2count = 0
       if x2 != NONE then
       {
           for i = 1 to n do
                if TEST_EQUIVALANCE(x2, c[i]) = true then
                    x2count = x2count + 1
       }

       if x1count > n/2 then
           return x1
       else if x2count > n/2 then
           return x2
       else
           return NONE
   }

} </geshi> ใน pseudocode ข้างบนนี้ TEST_EQUIVALANCE คือการเช็คว่าบัตร ATM สองบัตรสมมูลกันหรือไม่

ความถูกต้อง

การพิูสูจน์ว่าอัลกอริทึมข้างบนทำงานได้ถูกต้อง เราจะต้องพิสูจน์ข้อความสองข้อความต่อไปนี้

1. ถ้าใน $c_{1},c_{2},\ldots ,c_{n}\,$ มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา
2. ถ้าใน $c_{1},c_{2},\ldots ,c_{n}\,$ ไม่มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนั้นมีขนาดมากกว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนค่า NONE

ข้อความที่ 1

ให้ $P(n)\,$ เป็นประพจน์เปิด "$c_{1},c_{2},\ldots ,c_{n}\,$ มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา"

เราจะพิสูจน์ $P(n)\,$ ด้วย induction บน $n\,$ แต่ก่อนที่เราจะพิสูจน์เราจะพิสูจน์ lemma ต่อไปนี้

lemma: ให้บัตร $x\,$ เป็นบัตร ATM บัตรหนึ่งใน $c_{1},c_{2},\ldots ,c_{n}\,$ ที่มีบัตรสมมูลกับมันมากกว่า $n/2\,$ ใบ และให้ $h=n/2\,$ แล้วอย่างน้อยข้อความใดข้อความหนึ่งต่อไปนี้จะเป็นจริิง

1. มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $h/2\,$ ใบ
2. มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $(n-h)/2\,$ ใบ

พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่าข้อความทั้งสองเป็นเท็จ ดังนั้นเราจะได้ว่ามีบัตรที่สมมูลกับ $x\,$ ไม่เกิืน $h/2+(n-h)/2=n/2\,$ ใบ เกิดข้อขัดแย้งกับความจริงที่ว่ามีบัตรสมมูลกับ $x\,$ มากกว่า $n/2\,$ ฉะนั้นจะต้องมีอย่างน้อยข้อความหนึ่งที่เป็นจริง

พิสูจน์ $P(n)\,$: (Base Case) ในกรณีนี้ $n=1\,$ ซึ่งเราทราบว่า $\mathrm {Majority} (c_{1})=c_{1}\,$ และ $c_{1}\,$ เป็นบัตรที่มีบัตรสมมูลกับมัน 1 ใบ (ตัวมันเอง) ซึ่งจำนวนบัตรนี้มากกว่า $1/2=0.5\,$

(Induction Case) สมมติให้ $P(1),P(2),\ldots ,P(n-1)\,$ เป็นจริงสำหรับจำนวนเต็ม $n>1$ บางตัว พิจารณาเซตของบัตร ATM $c_{1},c_{2},\ldots ,c_{n}\,$ และสมมติให้ $x\,$ เป็นบัตร ATM ที่มีบัตรสมมูลกับมัน (รวมตัวมันเองด้วย) มากกว่า $n/2\,$ ใบ จาก lemma เราจะได้ว่า

• มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $h/2\,$ ใบ หรือไม่ก็
• มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $(n-h)/2\,$ ใบ

ฉะนั้นจะมีบัตรอย่างน้อยหนึ่งใบใน $x_{1}=\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{h})\,$ และ $x_{2}=\mathrm {Majority} (c_{h+1},c_{h+1},\ldots ,c_{n})\,$ ที่สมมูลกับ $x\,$

ดังนั้นเมื่อเรานำ $x_{1}\,$ และ $x_{2}\,$ ไปตรวจว่ามีบัตร ATM ที่สมมูลกับมันกี่ตัว จะมีบัตรหนึ่งทีมีบัตรสมมูลกับมันมากกว่า $n/2\,$ ใบ และ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนบ้ัตรนั้นออกมา ฉะนั้นเราสรุปได้ว่า $P(n)\,$ เป็นจริง

ดังนั้นเราสามารถสรุปว่า $P(n)\,$ เป็นจริงสำหรับจำนวนเต็มบวก $n\,$ ทุกตัวด้วย (strong) induction

ข้อความที่ 2

พิสูจน์: พิจารณาการทำงานของ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ เราจะได้ว่าไม่ว่า $x_{1}\,$ และ $x_{2}\,$ จะมีค่าเป็นอะไรก็ตาม จะมีบัตร ATM ที่สมมูลกับมันไม่เกิน $n/2\,$ เสมอ ฉะนั้น $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะตอบค่า NONE เท่านั้น

ประสิทธิภาพ

ให้ $T(n)\,$ เป็นเวลาการทำงานของ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ แล้วเราจะได้ว่า

$T(n)={\begin{cases}O(1)&n=1\\2T(n/2)+O(n)&n>1\end{cases}}\,$

ฉะนั้นด้วย Master Theorem เราจะได้ว่า $T(n)=O(n\log n)\,$