กรรมวิธีในการแก้ปัญหา และ รูปแบบของปัญหา

ดร.บุญญฤทธิ์ อุยยานนวาระ
ภาควิชาคอมพิวเตอร์และเทคโนโลยีสารสนเทศ
สถาบันเทคโนโลยีนานาชาติสิรินธร
มหาวิทยาลัยธรรมศาสตร์

 

เอาหล่ะ เริ่มเรื่องกันด้วยคำจำกัดความนีสนึง คำว่า Algorithm มันคืออะไรกัน แล้วทำไมเราต้องเรียนเรื่องนี้กันให้ยุ่งยาก

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

นั่นแปลว่า ความชัดเจนของกรรมวิธีต้องชัดเจนจริงๆ ถ้าใครมาเอาไปทำตามต้องทำได้เหมือนกันทุกคน ไม่ต้องตีความ และ ถ้ากรรมวิธีของคุณใช้ในการแก้ปัญหาถูกบ้างไม่ถูกบ้าง บาง input ก็คำนวณถูก บาง input คำนวณผิด แบบนี้ก็ไม่เรียกว่า algorithm นะครับ (น่าจะเรียกว่า เดา มากกว่า 555) หรือว่าวิธีในการแก้ปัญหาของคุณเขียนโปรแกรมเสร็จ อาจจะต้อง run บน Super Computer แล้วก็ใช้เวลาในการแก้ปัญหานั้นซัก 350 ปี แบบนี้ก็ไม่ไหวเหมือนกัน เพราะฉนั้น Algorithm ที่ดี ต้องมีความชัดเจนของกรรมวิธี แก้ปัญหาได้ถูกต้อง และจบในเวลาและทรัพยากรที่จำกัด

ต้องเรียนเรื่องนี้กันด้วยละครับ?
อืมมมม เป็นคำถามที่ดี

เราต้องการเรียนวิชานี้เพราะว่า โดยปกติแล้วมีคนคิดการแก้ปัญหาในเรื่องต่างๆไว้มากมายแล้ว และบางปัญหาก็คิดกันมาเป็น 100 ปีแล้ว ได้ algorithm วิธีแก้ปัญหาที่เนี๊ยบและฉลาด แล้ว ถามว่าถ้าเราต้องแก้ปัญหาเหล่านั้นอีกทำไมเราต้องหาวิธีใหม่ หรือแม้แต่ปัญหาของเราถ้าไม่ได้ตรงเป๊ะกับปัญหาที่เคยโดน solve ไปแล้ว เราก็ยังสามารถหา algorithm ที่ใกล้เคียง แล้วประยุกต์เพื่อแก้ปัญหาของเราได้ (อีกอย่างก็คือเราเรียนเพื่อเอาเกรดไงครับ 555 อันนี้ขำๆ)


ขั้นตอนในการคิดเพื่อแก้ปัญหา

โอเค ในส่วนนี้เราก็มาดูกรรมวิธีในการแก้ปัญหากันดีกว่านะครับ อันนี้เป็นกระบวนการโดยทั่วๆไปในการแก้ปัญหาใดๆ หมายความว่าไม่ว่าคุณจะเจอปัญหาอะไรที่ต้องการจะให้คอมพิวเตอร์ช่วยในการ solve ก็ให้ลองพยายามไล่ตามกระบวนการนี้ไปนะครับ

1. understand the problem เริ่มขั้นแรกคือการ ทำความเข้าใจกับปัญหาให้ชัดเจน มองปัญหาอย่างละเอียดและพยายามดึงเอาข้อมูลที่มีอยู่ในปัญหาออกมาให้หมดเท่าที่จะมีได้ มี input ของปัญหาเป็นอะไร ปัญหาต้องการอะไร ต้องให้อะไรเป็น output ของปัญหา ในปัญหานี้มีสิ่งที่เกี่ยวข้องกับการคำนวณ(หรือตัวแปร)อยู่กี่ตัว ขั้นตอนนี้รวมถึงการพยายามแปลงปัญหาไปเป็นสิ่งที่คอมพิวเตอร์เข้าใจได้ (จะพูดอีกครั้งโดยละเอียดในเรื่องState Space)

prove its correctness เพื่อพิสูจน์ว่า Algorithm ของเราทำงานได้อย่างถูกต้อง (มีศักยภาพในการประมวลผลดีแค่ไหน อยู่ใน class อะไร(ต้องการการขยายความเพิ่ม)

Analyze for its efficiency เพื่อวิเคราะห์ดูว่า Algorithm ของเรามีศักยภาพในการประมวลผลดีแค่ไหน อยู่ใน class อะไร (ต้องการการขยายความเพิ่ม)

coding ลงมือเขียนโปรแกรม ซึ่งเป็นขั้นตอนสุดท้ายในการแก้ปัญหา ขั้นตอนนี้หากว่าเราเป็นผู้คิดแก้ปัญหาที่ดี แต่อาจจะไม่มี skill ในการเขียนโปรแกรม หรืออาจจะไม่ถนัดในภาษาที่จำเป็นต้องใช้เขียน (อาจถนัดภาษาอื่น) ก็อาจมอบงานส่วนนี้ให้กับ programmer ได้ (แต่ในวิชานี้เราคิดว่าเราต้องทำตัวเป็นทั้งผู้ออกแบบ algorithm และ programmer)


Common Problem types

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

Sorting Problem คือปัญหาประเภทที่ต้องการเรียงลำดับค่าของข้อมูล เช่น จากน้อยไปหามาก จากสูงไปต่ำเป็นต้น ปัญหานี้เป็นปัญหาที่พื้นฐานของหลายปัญหาอย่างอื่น เนื่องจากการเรียงลำดับข้อมูลเป็นปัญหาที่มีประโยชน์มากและมักจะใช้ควบคู่กับการค้นหาข้อมูล หรือจัดการข้อมูลได้ ทำให้มีคนคิดค้น algorithm ในการแก้ปัญหา Sorting ไว้แล้วมากมาย มีทั้งที่ดีและไม่ดี ซึ่งจะได้เห็นในหน้าถัดๆไป

Searching Problem ปัญหาประเภทการค้นหาข้อมูล คือปัญหาที่เราต้องการมองหาข้อมูลจำเพาะจากกลุ่มของข้อมูล เช่น ต้องการหานักศึกษาจากหมายเลข ID เป็นต้น หรือ Search Engine ที่มองหาข้อมูลที่เป็น keyword

Combinatorial Problem คือปัญหาที่มองหาผลหรือเงื่อนไขเฉพาะจากโอกาสที่จะเกิดได้ทั้งหมด และปัญหาประเภทนี้จัดเป็นปัญหาที่ยากที่สุด เพราะการที่จะหา combination ที่ดีที่สุดของ input อาจจะหมายถึงการต้องหา combination ทุกๆ combination แล้วก็ทำการเปรียบเทียบกัน ซึ่งการหา combination ของปัญหาจะเป็นเรื่องใหญ่หากข้อมูลที่เข้ามามีขนาดใหญ่ เช่น ถ้าเรามีข้อมูลอยู่ 10 ตัว และต้องการเรียงสับเปลี่ยนเพื่อให้ได้ combination ทั้งหมดของข้อมูลชุดนี้แล้วหล่ะก็ ต้องสร้าง combination ถึง 10! (สิบแฟคทอเรี่ยล) ทีเดียซ ซึ่งนั่นก็หมายถึงหลายล้าน combination เข้าไปแล้ว และถ้าต้องการหาทุกๆ combination ของข้อมูลที่มีขนาดซัก 100 ข้อมูล ซึ่งหมายถึง 100! นี่อันนี้เลิกคิดถึงได้เลย

Numerical Problem คือปัญหาที่ต้องการหาค่าทางตัวเลขเพื่อเป็นคำตอบของสมการ ซึ่งอาจจะหาได้จากการประมาณ เพราะหากต้องแก้สมการด้วยมือหรือกรรมวิธีอื่นอาจใช้เวลานาน