การระบายสี กับ ขีดจำกัดของการคำนวณด้วยคอมพิวเตอร์

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

"ปัญหาการระบายสี" (coloring) :โจทย์มีอยู่ว่า มีแผนที่มาให้แผนที่หนึ่งที่แบ่งออกเป็น อาณาเขตย่อยๆหลายแห่ง เราต้องการระบายสีอาณาเขตทุกอาณาเขต โดยใช้สีให้น้อยที่สุด และมีกฏอยู่ว่า อาณาเขตที่อยู่ติดกันห้ามใช้สีเดียวกัน ภาพหนึ่งรูปแทนคำบรรยายล้านคำ ... ขอผมยกตัวอย่างด้วยภาพแล้วกันนะครับ

ให้สังเกตุว่าเราสามารถระบายสีแผนที่อเมริกาได้ด้วยสีเพียงสี่สีเท่านั้น ... ให้ลองทดสอบดูนะครับว่าแผนที่อเมริกาไม่สามารถระบายด้วยสามสีได้ แต่สี่สีสามารถทำได้ .... สิ่งที่น่าตกใจไปกว่านั้นก็คือ... ผมอยากจะบอกว่า ไม่ว่าเราจะระบายสีแผนที่ใดๆก็ตาม เราสามารถระบายได้โดยใช้เพียงสี่สีโดยที่อาณาเขตที่ิติดกันใช้ต่างสีกัน  นี่เป็นทฤษฎีที่สำคัญอย่างหนึ่งของคณิตศาสตร์ ชื่อว่า Four color theorem

(หากใครไม่เชื่อลองเอาแผนที่ประเทศไทยมาระบายสีเล่นดูนะครับ จะเห็นได้ว่าไม่จำเป็นต้องใช้เกินสี่สี)

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

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

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

(หมายเหตุ: ปัญหานี้เป็นปัญหาเดียวกันกับ  P vs NP นะครับ)

 

บันทึกนี้เขียนที่ GotoKnow โดย 

 คำสำคัญ: ระบายสี algorithms 
 หมายเลขบันทึก: 280152
 เขียน:  
 ความเห็น:  อ่าน: คลิก 
 สัญญาอนุญาต: ครีเอทีฟคอมมอนส์แบบ แสดงที่มา-ไม่ใช้เพื่อการค้า-อนุญาตแบบเดียวกัน
 แจ้งลบ
 
 แจ้งลบ

ความเห็น

วิชา
IP: xxx.206.3.105
เขียนเมื่อ Mon Jan 31 2011 14:36:04 GMT+0700 (ICT)

คำถาม

มีโปรแกรมทำแผนที่ประเทศไทยหรือเปล่า

ที่ใช้ค่าตัวเลขแทนสีต่างๆ เมื่อเปลี่ยนค่าตัวเลขที่กำหนดสีก็เปลี่ยนไปด้วย มีไหมครับ

wicha30@gmail.com

 อนุญาตให้แสดงความเห็นได้เฉพาะสมาชิก
 ไม่อนุญาตให้แสดงความเห็น
{{ kv.current_user.preferred_name }} - เพิ่มความเห็นเพิ่มความเห็น
 ใส่รูปหรือไฟล์
 
บันทึกก่อนนี้
บันทึกใหม่กว่า