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

  ติดต่อ

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

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

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

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

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

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

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

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

 

บันทึกนี้เขียนที่ GotoKnow โดย  ใน This blog never has a title

หมายเลขบันทึก: 280152, เขียน: , แก้ไข, 2012-06-21 19:28:54+07:00 +07 Asia/Bangkok, สัญญาอนุญาต: ครีเอทีฟคอมมอนส์แบบ แสดงที่มา-ไม่ใช้เพื่อการค้า-อนุญาตแบบเดียวกัน, ความเห็น: 1, อ่าน: คลิก

คำสำคัญ (Tags) #ระบายสี#algorithms

บันทึกล่าสุด 

ความเห็น (1)

วิชา
IP: xxx.206.3.105
เขียนเมื่อ 

คำถาม

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

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

[email protected]