ผมต้องส่งการบ้านในหัวข้อ “งานวิจัย NP ในปัจจุบัน” พอค้น ๆ ไปในอินเทอร์เน็ตถึงได้พบว่า อย่าว่าแต่ของคนไทยเลย ขนาดของพวกฝรั่งก็ยังเขียนลำดับให้เข้าใจไม่ค่อยได้ คือ เขาจะเขียนข้าม ๆ เป็นห้วง ๆ ไม่ลำดัีบเป็นขั้น ๆ เขาจะถือว่ารู้แล้ว (ซึ่งจริง ๆ เราไม่รู้) ดังนั้น ผมก็เลยต้องอ่านจากหลาย ๆ ที่ แล้วเอามาประมวลเป็นลำดับขั้นตอนเพื่อส่งการบ้าน ทีนี้เห็นว่ามันน่าจะเอามาเผยแพร่ได้ ให้คนทั่วไปเข้าใจได้ง่าย ๆ (เอ๊ะ หรือจะไม่ง่าย?) ก็เลยคิดว่าเอามาลงในบล็อกของตัวเองดีกว่า
งั้นเริ่มเลยล่ะกัน …
1. บทคัดย่อ
ในวงการวิทยาการคอมพิวเตอร์ หากเรากล่าวถึง “ปัญหา” จะมีสิ่งให้ขบคิดอยู่สองประเด็น นั่นคือ เราจะหาคำตอบของปัญหานั้น ๆ อย่างมีประสิทธิภาพได้อย่างไร และ หากมีการเฉลยคำตอบของปัญหานั้น ๆ แล้ว เราจะหาวิธียืนยันคำตอบนั้น ๆ อย่างมีประสิทธิภาพได้อย่างไร ว่ามันเป็นคำตอบที่ “ใช่” หรือ “ไม่ใช่” ซึ่งกลุ่มของปัญหาที่ต้องการ ๆ ยืนยันคำตอบอย่างมีประสิทธิภาพหากคำตอบคือ “ใช่” จะถูกเรียกในทางทฤษฎีว่าเป็นกลุ่มปัญหา NP หรือ Non-deterministic polynomial time ซึ่งในบทความนี้จะนำเสนอถึงการวิจัย NP ในปัจจุบัน ว่ามีความก้าวหน้าไปอย่างไรบ้าง
2. บทนำ
วิทยาการคอมพิวเตอร์เป็นศาสตร์ที่ใช้คณิตศาสตร์หลายแขนง เพื่อช่วยในการแก้ปัญหาให้กับศาสตร์ของตนเอง โดยเฉพาะการใช้ศาสตร์ที่เรียกว่า Combinatorics ในการแก้ปัญหา โดยเนื้อหาหลักของ Combinatorics ก็คือ “การจัดหมู่” ในสิ่งที่มีขอบเขต “จำกัด” จากนั้นจึงทำการ “นับ” มัน
ปัจจัยสำคัญใน “การนับ” ในทางวิทยาการคอมพิวเตอร์ก็คือการวนรอบ เพราะคุณลักษณะเด่นของคอมพิวเตอร์ก็คือ การที่สามารถวนรอบทำงานซ้ำ ๆ ได้ โดยไม่เหน็ดเหนื่อยและผิดพลาด ดังนั้น เมื่อมีการวนรอบก็จะหมายถึงการต้องเสียเวลา การวนรอบ 1 ชั้นก็หมายถึงการเสียเวลาน้อยกว่าหรือเท่ากับ n รอบ และการวนรอบ 2 ชั้นก็อาจหมายถึงการเสียเวลาน้อยกว่าหรือเท่ากับ n^2 รอบ เป็นต้น
ด้วยรูปแบบของการวนรอบเพื่อนับ จึงทำให้สามารถมองได้ว่าปัญหาส่วนใหญ่ในทางวิทยาการคอมพิวเตอร์ สามารถแก้ได้ในเวลา Polynomial Time แต่การแก้ปัญหาจะไม่ถือว่ามีประสิทธิภาพ หากใช้เวลาในการแก้ปัญหาเกินกว่าจะยอมรับได้ เช่นในการแก้ปัญหา Travelling Salesman Problem ที่กำหนดให้พนักงานขายเลือกเส้นทางที่สั้นที่สุด เพื่อเดินทางไปทีล่ะเมืองให้ครบทุกเมืองโดยไม่ซ้ำ แล้วย้อนกลับมายังเมืองที่ตั้งต้น ซึ่งการหาผลเฉลยที่ถูกต้องที่สุดก็คือการตรวจในทุก ๆ เส้นทางที่เป็นไปได้ แล้วเลือกเส้นทางที่สั้นที่สุดจากการตรวจสอบทั้งหมด โดยต้องใช้จำนวนรอบเพื่อหาผลเฉลยเท่ากับ n! ซึ่งหากมีจำนวนของเมือง 100 เมืองให้เดินทาง ก็หมายถึงการที่ต้องค้นหาผลเฉลยด้วยจำนวนรอบเท่ากับ 100! ซึ่งใช้เวลาที่มากเกินกว่าจะยอมรับได้
ดังนั้น ในทางทฤษฎีจึงเกิดแนวความคิดว่า ถ้ายังคงต้องการแก้ปัญหาที่ใช้เวลามาก ๆ ใน Polynomial Time ได้อย่างมีประสิทธิภาพ (และเราก็เชื่อว่ายังไงก็ต้องแก้แบบ Polynomial Time จนกว่ามันจะมีวิธีอื่นมาแทนที่ เช่น Quantum อะไรประมาณนั้น) จำเป็นอย่างยิ่งที่จะต้องเปลี่ยนแนวคิดของเครื่องจักรทางทฤษฎีที่ใช้ขับเคลื่อนการแก้ปัญหา จากเดิมที่ใช้เครื่องจักรทางทฤษฎีในการแก้ปัญหาที่มีกลไกเคลื่อนที่ 1 State เกิด 1 Action หรือที่เรียกว่า Deterministic Turing Machine ให้กลายเป็นเครื่องจักรทางทฤษฎีในการแก้ปัญหา ที่มีกลไกเคลื่อนที่ 1 State เกิดได้หลาย Action หรือที่เรียกว่า Non-deterministic Turing Machine
ซึ่งการแก้ปัญหาใน Polynomial Time บนเครื่องจักรทางทฤษฎีแบบ Non-deterministic Turing Machine จึงเรียกว่าเป็นการแก้ปัญหาแบบ Non-deterministic Polynomial Time หรือ NP และปัจจุบันก็มีงานวิจัยในหลากหลายแขนงวิชา ที่กำลังค้นคว้าวิจัยกลุ่มปัญหา NP อยู่ในขณะนี้ ดังจะกล่าวในหัวข้อถัดไป
3. งานวิจัยในปัจจุบัน
งานวิจัยที่เกี่ยวข้องกับ NP ในช่วงแรกนั้น มุ่งเน้นไปที่การแสวงหาเทคนิคและอัลกอริทึม ในการค้นหาผลเฉลยที่แม่นยำถูกต้องที่สุดเพียงคำตอบเดียวอย่างมีประสิทธิภาพ เพื่อให้สามารถหาคำตอบได้ในเวลาน้อยกว่า O(n!) เช่น งานวิจัยของ Held & Karp[1] และ Bellman[2] ได้นำเสนอการแก้ปัญหา Travelling Salesman Problem โดยใช้ Dynamic Programming เข้ามาช่วยเก็บผลการคำนวณก่อนหน้า เพื่อจะไม่ต้องมาวนซ้ำคำนวณใหม่อีกครั้งในทุก ๆ รอบซึ่งถูกพิสูจน์แล้วว่าสามารถลดการคำนวณจาก O(n!) เหลือ O(n^2*2^(n-1) )[2] เป็นต้น
เทคนิคการค้นหาผลเฉลยในรูปแบบข้างต้น ช่วยลดเวลาในการแก้ปัญหาจาก Factorial Time ให้อยู่ในรูปของ Exponential Time ได้ก็จริง แต่หากต้องเผชิญกับการแก้ปัญหาขนาดใหญ่ที่มีจำนวนข้อมูลมาก ๆ การแก้ปัญหาใน Exponential Time ก็ยังไม่สามารถถือว่าเป็นการแก้ปัญหาที่มีประสิทธิภาพได้ ดังนั้น งานวิจัยในปัจจุบัน จึงเน้นไปที่การค้นหาผลเฉลยที่เหมาะสมพอยอมรับได้ โดยใช้เวลาในการค้นหาที่จำกัดบนทรัพยากรที่จำกัด ด้วยเทคนิคและอัลกอริทึมต่าง ๆ ไม่ว่าจะเป็นการจำลองความฉลาดแบบกลุ่มด้วย Swarm Intelligence, การเลียนแบบขั้นตอนวิธีเชิงพันธุกรรมด้วย Genetic Algorithm หรือวิธีอื่น ๆ เป็นต้น
3.1 Swarm Intelligence
คำว่า Swarm Intelligence ถูกอ้างขึ้นครั้งแรกโดย Gerardo Beni & Jing Wang[3] ในบันทึกการประชุมเกี่ยวกับ Cellular Robotic Systems โดยมีเนื้อหาที่กล่าวถึงระบบซึ่งมีกลุ่มของหุ่นยนต์ที่ไม่ฉลาดจำนวนมากอยู่รวมกันเพื่อบรรลุภารกิจใหญ่ภารกิจหนึ่ง ซึ่งหุ่นยนต์ดังกล่าวจะบริหารจัดการตนเองโดยไม่มีศูนย์กลางควบคุม จะสามารถสื่อสารข้อมูลได้เฉพาะกับหุ่นยนต์ที่อยู่ในรัศมีใกล้ ๆ กัน จะแสดงพฤติกรรมที่ไม่สุ่มแต่ก็ไม่สามารถคาดเดาได้ จะแสดงพฤติกรรมหลายอย่างเกินกว่าความเข้าใจ และไม่สามารถใช้สถิติเพื่ออธิบายพฤติกรรมได้เลย
แนวความคิด Swarm Intelligence ได้ถูกนำไปต่อยอดเพื่อสร้างอัลกอริทึมในการค้นหาผลเฉลยที่เหมาะสมในหลาย ๆ รูปแบบ ซึ่งหนึ่งในนั้นก็คืองานวิจัยของ Marco Dorigo[4][5] ซึ่งเป็นผู้บุกเบิกหลักในการคิดค้น Ant Colony Optimization Algorithms ขึ้นมา โดยแนวคิดของ Ant Colony Optimization Algorithms หรือ ACO ก็คือ การจำลอง Set ของตัวแทนซึ่งมีความร่วมมือกัน โดยสิ่งที่ใช้เป็นตัวแทนก็คือ “มด” ในการร่วมมือร่วมใจกันเพื่อค้นหาผลเฉลยที่ดีที่สุด เปรียบได้กับการร่วมมือร่วมใจของมด ในการเดินทางออกจากรังเพื่อค้นหาแหล่งอาหารด้วยระยะทางเดินที่ใกล้ที่สุด โดยระหว่างการเดินทางค้นหา มดแต่ล่ะตัวจะใช้วิธีทางอ้อมเพื่อทิ้งร่องรอยของเส้นทางเดินให้มดตัวอื่นตามมา ด้วยการปล่อยฟีโรโมนตามเส้นทางเป็นระยะและยิ่งเส้นทางเดินใดมีฟีโรโมนมาก มดตัวใหม่ ๆ ที่เดินตามมาก็จะยิ่งเลือกเส้นทางดังกล่าวมากขึ้น และปล่อยฟีโรโมนซ้ำลงไปเรื่อย ๆ จนกระทั่งสุดท้ายเส้นทางอื่นก็จะไม่ถูกเลือกอีกต่อไป โดยเทคนิคของ ACO จะใช้ทฤษฎีกราฟเป็นโมเดล โดยจะแทนที่ทางเดินระหว่างรังมดกับแหล่งอาหารด้วย Connected Graph, แทนที่การเลือกเส้นทางในช่วงแรกของมดด้วยการสุ่มและ แทนที่การปล่อยฟีโรโมนของมดด้วยการให้ค่าน้ำหนักบน Edges ในระหว่างการเดินบน Path ดังนั้น เมื่อคำนวณจนถึงระดับหนึ่งแล้ว ก็จะได้ผลเฉลยที่เหมาะสมในรูปของ Path ที่มีผลรวมของ Edges มากที่สุดนั่นเอง
ปัจจุบัน มีงานวิจัยซึ่งนำแนวคิด Ant Colony Optimization หรือ ACO ไปเพิ่มขีดความสามารถอย่างกว้างขวาง เช่น งานวิจัยของ Lijie Li, Shangyou Ju และ Ying Zhang[6] ซึ่งได้สร้างโมเดลความน่าจะเป็นแบบใหม่ โดยใช้ Held-Karp Lower Bound ในการพิจารณาตัดสินใจว่าจะให้ระบบเลือกผลเฉลยอย่างใดอย่างหนึ่ง ระหว่างผลเฉลยที่ได้จากค่าน้ำหนักบน Edges หรือผลเฉลยที่ได้จาก Heuristic Information เป็นต้น
หรือการนำ ACO ไปประยุกต์ใช้ เช่น งานวิจัยของ Guangyu Li & Lila Boukhatem[7] ที่ทำให้ยานพาหนะทุกคันซึ่งวิ่งอยู่บนท้องถนน ทำตัวเป็น Wireless Router เพื่อสร้างระบบ Mobile Network โดยการประยุกต์ใช้ ACO เพื่อค้นหาเส้นทางที่สั้นที่สุดระหว่างยานพาหนะที่ต้องการจะสื่อสารกัน โดยการกำหนดให้ยานพาหนะเป็น Vertex ซึ่งเคลื่อนที่ได้, กำหนดให้การเชื่อมโยง Wireless ระหว่างรถแต่ล่ะคันที่มีระยะทำการใกล้ ๆ กัน (100-300 เมตร) เป็น Edge และกำหนดให้ Path คือเส้นทาง Mobile Network ระหว่างรถที่ต้องการสื่อสารกัน ซึ่งจุดที่น่าสนใจจะอยู่ที่ Vertex และ Edge จะสามารถเปลี่ยนแปลงไปมาได้ เพราะยานพาหนะที่วิ่งอยู่บนท้องถนนไม่อยู่นิ่งอยู่กับที่ เป็นต้น
4. เอกสารอ้างอิง
[1] Michael Held & Richard M. Karp. A dynamic programming approach to sequencing problems. ACM ’61 Proceedings of the 1961 16th ACM national meeting Pages 71.201-71.204.
[2] Richard Bellman. Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM (JACM) JACM Homepage archive. Volume 9 Issue 1, Jan. 1962. Pages 61-63.
[3] Gerardo Beni & Jing Wang. Swarm Intelligence in Cellular Robotic Systems. Proceedings of NATO Advanced Workshop on Robots and Biological Systems Vol 102.
[4] Alberto Colomi, Marco Dorigo, Vittorio Mamiezzo. Distributed Optimization by Ant Colonies. Proceedings of ECAL91 European Conference on Artificial Intelligence Life, Paris, France, Elsevier Publishing, 134-142.
[5] Marco Dorigo. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, Vol.1, No. 1, 1997.
[6] Lijie Li, Shangyou Ju and Ying Zhang. Improved Ant Colony Optimization for the Traveling Salesman Problem. Proceeding of ICICTA ’08 Proceedings of the 2008 International Conference on Intelligent Computation Technology and Automation – Volume 01, Pages 76-80
[7] Guangyu Li & Lila Boukhatem. Adaptive vehicular routing protocol based on ant colony optimization. Proceeding of VANET ’13 Proceeding of the tenth ACM international workshop on Vehicular inter-networking, systems, and applications, Pages 95-98, June 25 2013, Taipei, Taiwan
…ก็จบประมาณนี้
จริง ๆ แล้วการบ้านชิ้นนี้เป็นงานกลุ่ม ดังนั้น ผมจึงต้องให้เกียรติผู้ร่วมกลุ่ม โดยการไม่เอาส่วนที่พวกเขาเขียนมาลงในบล็อกของผม แต่ผมก็คิดว่าเฉพาะส่วนที่ผมเขียน ก็น่าจะครอบคลุมให้ผู้อ่านเกิดความเข้าใจได้ในระดับหนึ่งครับ
