43. ทฤษฎีความโกลาหล
เป็นสาขาหนึ่งของคณิตศาสตร์ที่เกี่ยวข้องกับพฤติกรรมสุ่มหรือคาดเดาไม่ได้ในระบบกำหนด
พฤติกรรมที่วุ่นวายมักพบเห็นได้รอบตัวเราจากของเหลวที่ไหล สภาพอากาศ การจราจรบนถนน ลูกตุ้มที่แกว่งไปมา และอื่นๆ
ผู้ก่อตั้งทฤษฎีความโกลาหลสมัยใหม่ "เอ็ดเวิร์ด ลอเรนซ์" สังเกตว่าความแตกต่างเพียงเล็กน้อยในสภาวะเริ่มต้นสามารถให้ผลลัพธ์ที่แตกต่างกันอย่างกว้างขวางสำหรับระบบที่กำหนดขึ้น (ระบบที่พฤติกรรมในอนาคตถูกกำหนดโดยเงื่อนไขเริ่มต้นอย่างสมบูรณ์)
ทำให้ไม่สามารถคาดเดาได้ในระยะยาว
ลอเรนซ์สังเกตเห็นสิ่งนี้ในระหว่างการคำนวณการพยากรณ์อากาศของเขา หากเงื่อนไขเริ่มต้นถูกป้อนด้วยทศนิยม 6 ตำแหน่ง ผลลัพธ์ที่ได้จะแตกต่างอย่างมากจากเมื่อใช้ทศนิยม 3 ตำแหน่ง
อีกตัวอย่างหนึ่งของระบบที่วุ่นวายแต่ถูกกำหนดไว้คือลูกตุ้มแบบแท่งคู่ดังต่อไปนี้
เอฟเฟกต์ผีเสื้อ
เป็นหลักการสำคัญของทฤษฎีเคออสที่ระบุว่าการเปลี่ยนแปลงเล็กๆ น้อยๆ ในสภาวะเริ่มต้นสามารถนำไปสู่การเปลี่ยนแปลงครั้งใหญ่ในสถานะระยะยาวของระบบได้
ดังที่ลอเรนซ์กล่าวไว้ในเชิงเปรียบเทียบ ผีเสื้อที่กระพือปีกในบราซิลสามารถมีอิทธิพลต่อพายุทอร์นาโดในเท็กซัสได้
ตัวดึงดูด
ตัวดึงดูดกลุ่มของรัฐซึ่งในที่สุดรัฐใกล้เคียงจะเข้าใกล้ในเส้นทางของตน
ในตัวอย่างของลูกตุ้มที่แกว่ง จุดที่ลูกตุ้มหยุดนิ่งในที่สุดคือจุดดึงดูดของระบบไดนามิกนี้
ลอเรนซ์ แอตแทรคเตอร์
ลอเรนซ์บรรยายบรรยากาศของโลกด้วยการหมุนเวียนของของไหลหมุนเวียนโดยใช้สมการไม่เชิงเส้นสามสมการ
ผลลัพธ์ของสมการเหล่านี้ก่อให้เกิดเส้นโค้งลึกลับที่ไม่เคยตัดผ่านตัวเอง ไม่เคยถึงจุดสมดุล และแสดงให้เห็นถึงความสับสนวุ่นวาย
เส้นโค้งนี้เรียกว่า ตัวดึงดูดลอเรนซ์
44. ปัญหากระเป๋าเป้สะพายหลัง
สมมุติว่ามีโจรมีเป้/เป้ที่รับน้ำหนักได้จำกัด
ควรเลือกกล่องใดต่อไปนี้เพื่อเพิ่มมูลค่าทางการเงินของสินค้าที่ถูกขโมยให้สูงสุดโดยรักษาน้ำหนักโดยรวมให้ต่ำกว่าหรือเท่ากับ 15 กิโลกรัม
นี่เป็นปัญหาการปรับให้เหมาะสมที่สุดซึ่งมักพบในระหว่างการจัดสรรทรัพยากรภายใต้ข้อจำกัด
ไม่มีอัลกอริธึมที่รู้จักที่สามารถให้วิธีแก้ปัญหาที่ถูกต้องและเร็วที่สุด (เวลาพหุนาม) ให้กับทุกกรณีของปัญหา (ปัญหาคือ "NP-complete")
หากเราตรวจสอบชุดค่าผสมที่เป็นไปได้ทั้งหมดเพื่อค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุด อัลกอริธึมกำลังเดรัจฉานนี้จะใช้เวลา O(2^n) เช่น เวลาที่ไม่ใช่พหุนาม
45. ปัญหาพนักงานขายที่เดินทาง
ลองนึกภาพว่ามีพนักงานขายพร้อมรายชื่อเมืองสำหรับจัดส่งพัสดุ
ปัญหาเริ่มต้นด้วยคำถาม:
อะไรคือคำสั่งให้พวกเขาเดินทางไปยังเมืองต่าง ๆ เพื่อลดระยะทางทั้งหมด?
นี่เป็นปัญหา "NP-hard" และใช้อัลกอริทึมคอมพิวเตอร์แบบ Brute-force ที่มีความซับซ้อนเวลา Big O ที่ O(n!)เพื่อค้นหาวิธีแก้ปัญหา
วิธีแก้ไขปัญหาได้รับการอธิบายไว้ในบทความที่ยอดเยี่ยมนี้โดย Pedram Ataee ใน "Towards Data Science":
วิธีแก้ปัญหาใหม่สำหรับปัญหานี้ได้รับการเผยแพร่เมื่อเร็ว ๆ นี้ และมีการอธิบายไว้อย่างดีในบทความด้านล่าง:
ปัญหาดังกล่าวยังถูกนำไปใช้ในด้านอื่นด้วย เช่น ดาราศาสตร์และการสังเคราะห์ DNA
ตรวจสอบส่วนอื่นๆ ในชุดนี้ด้านล่าง:
นั่นคือทั้งหมดสำหรับบทความนี้ ขอบคุณสำหรับการอ่าน!
หากคุณเพิ่งเริ่มใช้ Python หรือเขียนโปรแกรมโดยรวม ลองดูหนังสือเล่มใหม่ของฉันชื่อ 'The No Bulls**t Guide To Learning Python'ด้านล่าง:
