แก้ปัญหา ที่แก้ไม่ได้ (solve the unsolvables)

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


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

คราวนี้ คำว่า algorithm ที่มีประสิทธิภาพ มันจะวัดกันอย่างไร ปัจจุบันคำว่ามีประสิทธิภาพ ถูกกำหนดด้วยเวลาที่ alogorihtm มันใช้ในการแก้ปัญหานั้น ซึ่งถ้าหากว่า algorithm นั้นสามารถแก้ปัญหา ได้ด้วย บิ๊กโอ อยู่ในระดับ O(nk) หรือมี บิ๊กโออยู่ในรูปของ polynomial เราก็จะบอกว่า algorithm นั้นมีประสิทธิภาพ ซึ่งหมายถึงว่าปัญหาดังกล่าวแก้ได้ด้วย algorithm ที่มีประสิทธิภาพ ก็แปลว่าปัญหานั้นแก้ได้นั่นเอง และเราก็มีคำเฉพาะในการเรียกกลุ่มปัญหาพวกนี้ว่า ปัญหา P (ซึ่งย่อมาจาก polynomial) นั่นแปลว่าปัญหาที่แก้ไม่ได้ด้วย algorithm ที่มีประสิทธิภาพ (วงเล็บนะคร้าบ มันอาจจะแก้ได้ด้วย algorithm ที่ไม่มีประสิทธิภาพครับ) เราก็เรียกมันว่าปัญหาที่แก้ไม่ได้ หรือปัญหาประเภท NP (Nondeterministic Polynomial Time Problem) นั่นเอง

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

ก่อนอื่นเราจะพูดคุยกันถึงการแยกแยะประเภทของปัญหาเสียก่อน
P (Polynomial Time Problem)
กลุ่มของปัญหาที่สามารถแก้ปัญหาได้ด้วย algotihm ที่มี บิ๊กโอ อยู่ในระดับ O(nk) เมื่อ n คือจำนวนของ input และ k คือค่าคงที่

NP (Nondeterministic Polynomial Time Problem)
กลุ่มของปัญหาที่สามารถแก้ปัญหาได้ด้วย nondeterministic algotihm (ซึ่งหมายถึง algorithm ที่ให้ผลไม่ชัดเจน - เอ๊ะยังไง ชักจะงงๆ)

nondeterministic algotihm ก็คือ ...... 

NP-Complete
ปัญหาที่อยู่ในกลุ่มนี้จัดเป็นปัญหาที่ยากมาก แปลว่าเราไม่สามารถหา algorithm ที่มีประสิทธิภาพมาแก้ปัญหานี้ได้ (ซึ่งรวมไปถึงนักวิทยาศาสตร์คอมพิวเตอร์ที่มีชีวิตก่อนหน้าเราด้วย)

ตอนนี้

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

การแก้ปัญหาเพื่อให้ได้ผลที่แน่นอน (Exact solution)
- Backtracking
เป็นการหา solution ของปัญหาโดยการเพิ่มองค์ประกอบของคำตอบทีละส่วน ทีละส่วน จนได้คำตอบที่สมบูรณ์ ซึ่งลักษณะจะคล้ายๆกับการแตกต้นไม้ของ state space นั่นเอง 
ข้อดีคือจะไม่ต้องหา combination ทุกๆอย่างของปัญหาเหมือนกับวิธีใช้แรงถึก (brute force) แต่ใน กรณี worse case ก็จะเป็น brute force 

- Branch and Bound
การแตกต้นไม้แบบ Branch and Bound จริงๆแล้วก็ขยายต่อออกมาจากการแตกแบบ backtracking เพียงแต่เพิ่ม ตัววัดขึ้นมาอีก 2 ตัว คือ bound และ ค่าของผลลัพธ์ที่ดีที่สุดจนถึงปัจจุบัน

การแก้ปัญหาเพื่อให้ได้ผลแบบประมาณ (Approximate Algorithm)
การแก้ปัญหาที่ยากที่จะแก้ เช่น พวก NP การที่จะให้ได้มาซึ่งคำตอบที่ถูกต้องเป๊ะๆ อาจจะทำได้ยากมาก หรือไม่ก็ทำไม่ได้เลย ซึ่งในกรณีนี้หากเราจำเป็นที่ต้องการคำตอบจากปัญหาเหล่านั้นจริงๆหล่ะจะทำอย่างไร คำตอบของคำถามนี้ก็คือว่า เราอาจจะใช้วิธีการประมาณการเอา โดยที่คำตอบที่ได้จากการประมาณ อาจจะไม่ใช่คำตอบที่ดีที่สุด แต่อย่างน้อย ในเวลาที่เรามี คำตอบนั้น ก็น่าจะใกล้เคียงกับคำตอบที่ดีที่สุดและอยู่ในเกณฑ์ที่รับได้ ในเวลาที่จำกัด 

ลองมาดูตัวอย่าง a lgorithm ที่เป็นการประมาณการกันดูนะครับ

Traveling Salesman Problem

Nearest Neighbor
twice-around-the-tree
หา minimum spaning tree แล้วเดินรอบ