“Design & Analysis Algorithms” ของ อ.สมชาย ประสิทธิ์จูตระกูล #1

เคยฟังคำกล่าวว่า อันจอมยุทธ หยิบกิ่งไผ่ ก็เสมือนหนึ่ง กระบี่ .. และสำหรับบางประโยค ชาวบ้านร้านตลาดอย่างเรา ก็ไม่อาจเข้าใจได้ในบัดดล

จนเมื่อกลับมาอ่านใหม่อีกครั้ง หลังจากทิ้งมีด, ทิ้งจอบ ออกท่องเที่ยว Research มาสักพัก จึงได้รู้สึกว่า .. อืม .. อย่างนี้ นี่เอง .. ภาพรวมของยุทธภพ

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

ถ้าง่ายมักใช้กลวิธีการแบ่งแยกและเอาชนะ (Divide and Conquer), กำหนดการพลวัต (Dynamic Programming), หรืออัลกอริทึมเชิงละโมบ (Greedy Algorithm) แต่ถ้าต้องการง่ายๆเร็วๆ ก็อาจใช้อัลกอริทึมเชิงสุ่ม (Randomized Algorithm)

ถ้ายากมักใช้การค้นเชิงการจัด (Combinatorial Search) เช่น การย้อนรอย (Back Tracking), หรือการขยายและจำกัดเขต (Branch and Bound)
ถ้าลดความทะเยอทะยานของคำตอบลง เช่น ต้องการคำตอบที่ดีดี ก็พอ ไม่จำเป็นต้องดีที่สุด ก็อาจใช้การค้นเฉพาะที่ (Local Search) หรืออัลกอริทึมเชิงประมาณ (Approximation Algorithm)

แต่ไม่ว่าปัญหาจะง่ายหรือยาก ถ้าเป็นปัญหาที่มีขนาดเล็กจริงๆ บางทีลุยเอา (แบบที่เขาเรียกกันว่า Brute Force) ก็เพียงพอ

กว่าจะรู้ .. ง่ายหรือยากให้ดูที่ Time Complexity ในการประมวลผลเป็นหลัก (Big O)

ส่วนขนาดเล็กหมายถึง ความเป็นไปได้ของ Input เช่นการคำนวณ ที่มี Input เป็น n = 1 ถึง 10 อาจใช้เวลา 1-2ชม. แต่ถ้า n = 1000 อาจใช้เวลาเป็น 10 ปี .. แต่ถ้าเราแน่ใจว่า n จะไม่มีทางเกินกว่า 10 ไปได้ เราก็อาจเลือกใช้ Algorithm ที่ทำงานแบบ Time Complexity สูงๆได้

ขอขอบคุณ อาจารย์ สมชาย ประสิทธิ์จูตระกูล ครับ

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s