ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 7"
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 7: | แถว 7: | ||
ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น <math> O(n \log n) \,</math> นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ <math>T(n)=2T(n/2)+O(n) \,</math> จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน <math> O(n) \, </math> เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ | ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น <math> O(n \log n) \,</math> นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ <math>T(n)=2T(n/2)+O(n) \,</math> จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน <math> O(n) \, </math> เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ | ||
| + | |||
| + | จากการที่เราใช้เทคนิค divide and conquer จะสามารถแสดงขั้นตอนต่าง ๆ ได้ดังนี้ | ||
| + | |||
*'''DIVIDE:''' แบ่งอะเรย์ออกเป็นสองครึ่งที่มีขนาดเท่ากัน สมมติให้ k เป็นตำแหน่งที่แบ่ง จะได้กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>) | *'''DIVIDE:''' แบ่งอะเรย์ออกเป็นสองครึ่งที่มีขนาดเท่ากัน สมมติให้ k เป็นตำแหน่งที่แบ่ง จะได้กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>) | ||
| แถว 13: | แถว 16: | ||
*'''COMBINE:''' ทำการหาช่วงที่มีผลบวกมากที่สุดข้ามฝั่งซ้ายขวา นั่นคือมีตำแหน่งเริ่มต้นของช่วง <math> i \, </math> โดยที่ <math> 1 \leq i \leq k \,</math> และตำแหน่งสิ้นสุดของช่วง <math> j \, </math> โดยที่ <math> k+1 \leq j \leq n \,</math> | *'''COMBINE:''' ทำการหาช่วงที่มีผลบวกมากที่สุดข้ามฝั่งซ้ายขวา นั่นคือมีตำแหน่งเริ่มต้นของช่วง <math> i \, </math> โดยที่ <math> 1 \leq i \leq k \,</math> และตำแหน่งสิ้นสุดของช่วง <math> j \, </math> โดยที่ <math> k+1 \leq j \leq n \,</math> | ||
| + | |||
คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ <math> A[k] \, </math> กับ <math> A[k+1] \, </math> อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า <math> A[k] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ <math> A[k+1] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง | คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ <math> A[k] \, </math> กับ <math> A[k+1] \, </math> อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ <math>A[1],A[2],...,A[k] \,</math> ส่วนกลุ่มขวาเป็นอะเรย์ <math>A[k+1],A[k+2],...,A[n] \,</math>) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า <math> A[k] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ <math> A[k+1] \,</math> ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง | ||
| แถว 57: | แถว 61: | ||
al <--- (a[1],a[2],...,a[k]) // แบ่งปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k | al <--- (a[1],a[2],...,a[k]) // แบ่งปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k | ||
ar <--- (a[k+1],a[k+2],...,a[n]) | ar <--- (a[k+1],a[k+2],...,a[n]) | ||
| − | |||
(iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย | (iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย | ||
(iR,jR,mR) <--- Maxinterval(ar,n-k) | (iR,jR,mR) <--- Maxinterval(ar,n-k) | ||
| − | |||
(maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย | (maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย | ||
(maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา | (maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา | ||
รุ่นแก้ไขปัจจุบันเมื่อ 07:23, 8 กันยายน 2552
อินพุต:อะเรย์ขนาด ช่อง แต่ละช่องมีจำนวนเต็มบรรจุอยู่หนึ่งตัว
เอาพุต: คู่ลำดับ ที่ ที่ทำให้ มีค่ามากที่สุด
แนวคิด วัตถุที่ต้องการตรวจสอบคือ คู่ลำดับ ดังนั้นคู่ลำดับที่เป็นไปได้ คือ ส่วนเงื่อนไขคือ คู่ลำดับ ดังกล่าวข้างต้นที่ ที่ทำให้ มีค่ามากที่สุด
ในแบบฝึกหัดก่อนหน้านี้เราได้ใช้วิธี Brute Force ไปแล้ว ในโจทย์ข้อนี้เราจะใช้เทคนิค Divide and Conquer กัน ซึ่งถ้าต้องการให้ได้เวลาการทำงานของอัลกอริทึมเป็น นั้นต้องให้ได้สมการที่แสดงเวลาการทำงาน แบบนี้ จากสมการเวลาการทำงานข้างต้น เราจะทำการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยสองปัญหาที่มีขนาดเท่ากัน จากนั้น ถ้าเราสามารถทำการหาช่วงที่มีผลบวกมากที่สุดระหว่างกลุ่มแรกกับกลุ่มหลังที่เราทำการแบ่งได้ในเวลาการทำงาน เราก็จะได้เวลาการทำงานของอัลกอริทึม ตามที่เราต้องการ
จากการที่เราใช้เทคนิค divide and conquer จะสามารถแสดงขั้นตอนต่าง ๆ ได้ดังนี้
- DIVIDE: แบ่งอะเรย์ออกเป็นสองครึ่งที่มีขนาดเท่ากัน สมมติให้ k เป็นตำแหน่งที่แบ่ง จะได้กลุ่มซ้ายเป็นอะเรย์ ส่วนกลุ่มขวาเป็นอะเรย์ )
- CONQUER: ทำการหาช่วงที่มีผลบวกมากที่สุดในอะเรย์ครึ่งซ้ายและครึ่งขวา
- COMBINE: ทำการหาช่วงที่มีผลบวกมากที่สุดข้ามฝั่งซ้ายขวา นั่นคือมีตำแหน่งเริ่มต้นของช่วง โดยที่ และตำแหน่งสิ้นสุดของช่วง โดยที่
คำตอบที่จะได้คือช่วงที่มีผลบวกมากที่สุด ระหว่างช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย (กลุ่มแรก) ช่วงที่มีผลบวกมากที่สุดในกลุ่มขวา (หลัง) และช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา การหาช่วงที่มีผลบวกมากที่สุดในกลุ่มซ้าย และ ขวาจะทำการหาเหมือนกับการหาช่วงที่มีผลบวกมากที่สุดของปัญหาใหญ่ ส่วนการหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานั้น พิจารณาได้ดังนี้ ช่วงดังกล่าว จะต้องมีอะเรย์ตัวที่ กับ อยู่ด้วย (ถ้าสมมติให้การแบ่งปัญหาเป็นปัญหาย่อย แบ่งที่ตำแหน่ง k คือ กลุ่มซ้ายเป็นอะเรย์ ส่วนกลุ่มขวาเป็นอะเรย์ ) นอกจากนี้การหาช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวานี้ ยังสามารถคิดได้อีกว่า เป็นการหาว่า ต้องบวกกับอะเรย์ที่อยู่ทางซ้ายไปกี่ตัว ถึงจะมีผลบวกมากที่สุด และ ต้องบวกกับอะเรย์ที่อยู่ทางขวาไปกี่ตัว ถึงจะมีผลบวกมากที่สุด นั่นเอง
![{\displaystyle A[k+1],A[k+2],...,A[n]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/486739d6dc6a7b91e06d03aba2b0a6913e578d05)
จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
ฟังก์ชั่น IntervalL มีไว้เพื่อหาค่าผลบวกที่มากที่สุดในอะเรย์ด้านซ้าย จากแนวคิดข้างต้น ที่บอกไว้ว่า ผลบวกที่มากที่สุดข้ามซ้ายขวา จะต้องมีอะเรย์ตำแหน่งที่ k อยู่ด้วยเสมอ จากนั้นเราต้องหาต่อไปว่า นี้ต้องบวกไปกับสมาชิกในอะเรย์ด้านซ้ายอีกกี่ตัวจึงจะมีค่าผลบวกมากที่สุด นั่นคือหาว่าค่าเริ่มต้นของช่วง จะอยู่ตำแหน่งไหน ระหว่าง 1 ถึง k นั่นเอง
![{\displaystyle A[k]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99daa240115659575df3bbc1a5404db6fc016fb9)
<geshi lang="c"> IntervalL(x,y,k)
maxL <--- -infinity
sum <--- 0
for i=k down to 1 // เวลาการทำงาน for loop นี้จะเป็น n/2
sum <--- sum + a[k] // หาผลบวกของอะเรย์ตำแหน่งที่ i ถึง k
if sum > maxL // เก็บช่วงที่มีผลบวกมากสุดไว้
maxL = v
maxiL=i
maxjL=k
</geshi>
ฟังก์ชั่น IntervalR มีไว้เพื่อหาค่าผลบวกที่มากที่สุดในอะเรย์ด้านขวา จากแนวคิดข้างต้น ที่บอกไว้ว่า ผลบวกที่มากที่สุดข้ามซ้ายขวา จะต้องมีอะเรย์ตำแหน่งที่ k+1 อยู่ด้วยเสมอ จากนั้นเราต้องหาต่อไปว่า นี้ต้องบวกไปกับสมาชิกในอะเรย์ด้านขวาอีกกี่ตัวจึงจะมีค่าผลบวกมากที่สุด นั่นคือหาว่าค่าสิ้นสุดของช่วง จะอยู่ตำแหน่งไหน ระหว่าง k+1 ถึง n นั่นเอง
![{\displaystyle A[k+1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a626e7f06bc68365aed07a3558862cd88b04de0)
<geshi lang="c"> IntervalR(x,y,k)
maxR <--- -infinity
sum <--- 0
for j=k+1 to n // for loop นี้อีก n/2
sum <--- sum + a[j]
if sum > maxR
maxR = v
maxiR=k
maxjR=j
</geshi>
เมื่อได้ฟังก์ชั่นในการหาค่าผลบวกมากที่สุดในด้านซ้ายและขวาแล้ว ก็สามารถเขียนอัลกอริทึมที่ใช้ในการหาช่วงที่มีผลบวกมากที่สุด โดยวิธี divide and conquer ได้ดังนี้
<geshi lang="c"> Maxinterval(a,n)
if n= 1
return a
else
k=n/2
al <--- (a[1],a[2],...,a[k]) // แบ่งปัญหาออกเป็นปัญหาย่อยสองปัญหาที่แต่ละปัญหามีขนาดเป็น k
ar <--- (a[k+1],a[k+2],...,a[n])
(iL,jL,mL) <--- Maxinterval(al,k) // ทำการหาช่วงที่มีผลบวกมากที่สุดของแต่ละปัญหาย่อย โดยให้ iL,iR เก็บช่วงด้านซ้าย และ mL เก็บค่าผลบวกมากสุดด้านซ้าย
(iR,jR,mR) <--- Maxinterval(ar,n-k)
(maxiL,maxjL,maxL) <--- IntervalL(x,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งซ้าย
(maxjR,maxjR,maxR) <--- IntervalL(y,k) // หาช่วงที่มีผลบวกมากที่สุดระหว่างปัญหาย่อยฝั่งขวา
maxi <--- maxiL // maxi เป็นตัวแปรที่เก็บตำแหน่งเริ่มต้นของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งเริ่มต้นของฝั่งซ้าย
maxj <--- maxjR // maxj เป็นตัวแปรที่เก็บตำแหน่งเริ่มสุดท้ายของช่วงที่มีผลบวกมากที่สุดข้ามซ้ายขวา ดังนั้นจึงเท่ากับ ตำแหน่งสุดท้ายของฝั่งขวา
max <--- maxL + maxR // max เก็บค่าผลบวกที่มากที่สุดระหว่างสองฝั่ง จึงเท่ากับผลบวกที่มากที่สุดฝั่งซ้ายบวกกับผลบวกที่มากที่สุดฝั่งขวา
if mL >= mR then // ถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดด้านขวา
{
if mL >= max then // และถ้าผลบวกมากสุดด้านซ้ายมากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
{
i <--- iL // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านซ้าย
j <--- jL
m <--- mL
}else{ // ผลบวกมากสุดด้านซ้ายมากกว่าด้านขวา แต่น้อยกว่าผลบวกข้ามซ้ายขวา
i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
j <--- maxj
m <--- max
}
}else // ถ้าผลบวกมากสุดด้านขวามากกว่าผลบวกมากสุดด้านซ้าย
{
if mR >= max then // และถ้าผลบวกมากสุดด้านขวามากกว่าหรือเท่ากับผลบวกมากสุดข้ามซ้ายขวาด้วย
{
i <--- iR // คำตอบจะเป็นช่วงและผลบวกมากสุดด้านขวา
j <--- jR
m <--- mR
}else{ // ผลบวกมากสุดด้านขวามากกว่าด้านซ้าย แต่น้อยกว่าผลบวกข้ามซ้ายขวา
i <--- maxi // คำตอบจะเป็นช่วงและผลบวกมากสุดข้ามซ้ายขวา
j <--- maxj
m <--- max
}
}
return (i,j,m)
</geshi>
