การระบายสี กับ ขีดจำกัดของการคำนวณด้วยคอมพิวเตอร์
วันนี้ผมอยากพูดถึงปัญหาสำคัญที่สุดอย่างหนึี่งของวิทยาการคอมพิวเตอร์ ปัญหานี้เกี่ยวข้องกับปัญหาการคำนวณด้วยคอมพิวเตอร์ปัญหาอื่นๆนับพันปัญหาในปัจจุบัน ทั้งทางตรงและทางอ้อม (แน่นอนว่าไม่เกี่ยวกับปัญหาการเมืองเรื้อรังของประเทศเรานะครับ)
"ปัญหาการระบายสี" (coloring) :โจทย์มีอยู่ว่า มีแผนที่มาให้แผนที่หนึ่งที่แบ่งออกเป็น อาณาเขตย่อยๆหลายแห่ง เราต้องการระบายสีอาณาเขตทุกอาณาเขต โดยใช้สีให้น้อยที่สุด และมีกฏอยู่ว่า อาณาเขตที่อยู่ติดกันห้ามใช้สีเดียวกัน ภาพหนึ่งรูปแทนคำบรรยายล้านคำ ... ขอผมยกตัวอย่างด้วยภาพแล้วกันนะครับ
ให้สังเกตุว่าเราสามารถระบายสีแผนที่อเมริกาได้ด้วยสีเพียงสี่สีเท่านั้น ... ให้ลองทดสอบดูนะครับว่าแผนที่อเมริกาไม่สามารถระบายด้วยสามสีได้ แต่สี่สีสามารถทำได้ .... สิ่งที่น่าตกใจไปกว่านั้นก็คือ... ผมอยากจะบอกว่า ไม่ว่าเราจะระบายสีแผนที่ใดๆก็ตาม เราสามารถระบายได้โดยใช้เพียงสี่สีโดยที่อาณาเขตที่ิติดกันใช้ต่างสีกัน นี่เป็นทฤษฎีที่สำคัญอย่างหนึ่งของคณิตศาสตร์ ชื่อว่า Four color theorem
(หากใครไม่เชื่อลองเอาแผนที่ประเทศไทยมาระบายสีเล่นดูนะครับ จะเห็นได้ว่าไม่จำเป็นต้องใช้เกินสี่สี)
ทีนี้ การระบายสีโดยใช้คนระบายสามารถทำได้ไม่ยากนัก ผมจำได้สมัยผมสามขวบผมนั่งระบายสีรูปสัตว์ประหลาดเล่น แล้วโดยธรรมชาติของผม ผมมักจะระบายให้อาณาเขตที่ติดกันเป็นสีต่างกันไปเอง ไม่ทราบว่าท่านอื่นเป็นแบบผมหรือเปล่า?
ปัญหานี้ คอมพิวเตอร์ปวดหัวเป็นอย่างมากครับ ในปัจจุบัน เราไม่สามารถเขียนโปรแกรมให้คอมพิวเตอร์ระบายสีอัตโนมัติแบบมีประสิทธิภาพโดยใช้สีน้อยที่สุดได้ แย่ไปยิ่งกว่านั้น สมมติว่าเรามีแผนที่สองแผนที่ A กับ B โดยที่ แผนที่ A สามารถระบายสีได้โดยใช้ 3 สี ส่วนแผนที่ B จำเป็์นต้องใช้ 4 สีในการระบาย ในปัจจุบัน ยังไม่มีโปรแกรมคอมพิวเตอร์ที่สามารถบอกความแตกต่างระหว่างแผนที่ที่ใช้สี 3 สี กับ 4 สีได้ นี่ถือเป็นความล้มเหลวอย่างหนึ่งของนักคอมพิวเตอร์หรือเปล่า?
ปัญหานี้ไม่ใช่ปัญหาธรรมดา หากคุณสามารถเขียนโปรแกรมที่ระบายสีแผนที่โดยใช้สีน้อยที่สุดได้อย่างมีประสิทธิภาพ (โปรแกรมต้องระบายสีแผนที่ใดๆก็ได้ไม่ใช่แผนที่ใดแผนที่หนึ่งนะครับ) คุณจะได้รับรางวัล 1 ล้านเหรียญสหรัฐทันที!!! หรือ หากคุณสามารถพิสูจน์ได้ว่า ไม่มีโปรแกรมใดสามารถทำงานดังกล่าวได้ รางวัล 1 ล้านเหรียญเป็นของคุณเช่นกัน
(หมายเหตุ: ปัญหานี้เป็นปัญหาเดียวกันกับ P vs NP นะครับ)
ความเห็น (1)
คำถาม
มีโปรแกรมทำแผนที่ประเทศไทยหรือเปล่า
ที่ใช้ค่าตัวเลขแทนสีต่างๆ เมื่อเปลี่ยนค่าตัวเลขที่กำหนดสีก็เปลี่ยนไปด้วย มีไหมครับ