04 · สงครามกับศาสตร์แห่งการค้นหา
เส้นทางที่สั้นที่สุด — ประวัติศาสตร์ของศิลปะและศาสตร์แห่งการแก้ปัญหา
Portsmouth 1941
ฤดูใบไม้ผลิปี 1941 Patrick Blackett นั่งอยู่ในห้องบัญชาการปฏิบัติการของ Royal Air Force เฝ้าดูเรืออูจมเรือสินค้าเร็วกว่าที่อังกฤษจะต่อขึ้นมาใหม่ได้ และพยายามคำนวณหาทางออกจากมัน ไม่เคยมีนักฟิสิกส์คนไหนถูกมอบหมายให้ทำงานแบบนี้มาก่อน เขาสร้างชื่อเสียงระดับโนเบลไว้ในวงการฟิสิกส์แล้ว — และได้รับรางวัลโนเบลจริงในปี 1948 จากงานเรื่องรังสีคอสมิก
ทีมของเขาไม่มีชื่อทางการ คนจึงเรียกว่า Blackett's circus: นักสรีรวิทยาหนึ่งคน นักฟิสิกส์หนึ่งคน นักฟิสิกส์ดาราศาสตร์หนึ่งคน และในที่สุดผู้ที่จะได้รางวัลโนเบลในอนาคตอีกสองคน ทุกคนถูกยืมตัวจากห้องทดลองมาประจำ Operational Research Section ที่เพิ่งตั้งขึ้นของ Coastal Command (INFORMS biographical profile of Blackett) ไม่มีใครในทีมเคยรบในสงครามมาก่อน สิ่งที่พวกเขามีคือนิสัยที่นักฟิสิกส์ทุกคนถูกปลูกฝังมา: ไม่เชื่อสัญชาตญาณที่ยังไม่ได้เทียบกับตัวเลข
สัญชาตญาณข้อแรกที่พวกเขาตรวจสอบเกือบทำให้อาชีพใครคนหนึ่งจบลง กองเรือคุ้มกันของอังกฤษ — เรือสินค้าที่แล่นเป็นกลุ่มข้ามแอตแลนติกโดยมีเรือคุ้มกัน — ยึดกฎที่ไม่มีใครพูดออกมาดังๆ มาหลายปี: ให้กองเล็กไว้ กลุ่มเรือที่เล็กกว่าคือเป้าที่เล็กกว่า และถ้าตะกร้าหล่น ไข่ก็เสียน้อยกว่า นายทหารเรือระดับสูงถึงขั้นพลเรือเอก Ernest King ของอเมริกาเชื่อเรื่องนี้แน่นจนแทบไม่คิดว่าคุ้มจะทดสอบ กลุ่มของ Blackett ทดสอบอยู่ดี และพบสิ่งตรงข้าม เรืออูต้อง*หา*กองเรือให้เจอก่อนจึงโจมตีได้ และมหาสมุทรกว้าง พื้นที่ที่เรือดำน้ำต้องค้นไม่ขึ้นกับว่ามีเรือกี่ลำอยู่ในวงของกองเรือ พอเรือล่าเจอกองเรือแล้ว ตอร์ปิโดที่มันมีก็จำกัด กองเรือ 80 ลำจึงเสียระวางบรรทุกให้ผู้โจมตีรายเดียวมากกว่ากองเรือ 40 ลำเพียงเล็กน้อย — ในขณะที่จำนวนกองเรือที่ต้องข้ามมหาสมุทรและเปิดตัวเองให้เสี่ยงต่อการถูกพบตั้งแต่แรกนั้นลดลงครึ่งหนึ่ง แก่นของเหตุผลเป็นเรขาคณิตล้วน: อัดเรือสินค้าเข้าไปในวงกลม จำนวนที่ใส่ได้โตตาม*พื้นที่* คือกำลังสองของรัศมี ส่วนเรือคุ้มกันที่ลาดตระเวนตาม*เส้นรอบวง* เพิ่มตามรัศมีเท่านั้น เพิ่มขนาดกองเรือเป็นสองเท่า เรือคุ้มกันไม่ต้องเพิ่มเป็นสองเท่า — เรือคุ้มกันอีกไม่กี่ลำคุ้มสินค้าได้มากกว่าเดิมมากตามสัดส่วน (Pacific War Encyclopedia, "Convoys") กองทัพเรืออังกฤษยึดขนาดกองเรือ "ในอุดมคติ" ไว้ที่ราว 40 ลำ โดยไม่มีใครอธิบายเหตุผลได้ เมื่อถูกโน้มน้าวในที่สุดให้เดินกองเรือใหญ่เท่าที่การขนส่งเอื้อ ยอดเรือถูกจมก็ลดลง นักวิเคราะห์คำนวณว่าเรือคุ้มกันที่ต่อขึ้นแต่ละลำช่วยเรือสินค้าไว้ได้ราวสองลำตลอดช่วงสงคราม
ชนวนตั้งผิดความลึก นั่นคือสิ่งที่คณะละครสัตว์คณะเดิมพบ เมื่อหันเครื่องคิดเลขไปที่ระเบิดลึกของ RAF — ระเบิดใต้น้ำที่ทิ้งใส่เรืออูที่ดำอยู่ ลูกเรือตั้งชนวนให้ระเบิดที่ราว 100 ฟุต ความลึกที่ผู้บังคับการเรือดำน้ำน่าจะดำหนีลงไป แต่ข้อมูลการโจมตีจริงบอกว่าเรืออูส่วนใหญ่ยังอยู่ใกล้ผิวน้ำตอนถูกจับได้ กำลังดำลงอย่างตื่นตระหนก ตั้งชนวนใหม่ให้ระเบิดที่ราว 35 ฟุตแทน ระเบิดลึกที่เคยพลาดเป้าเพราะจุดระเบิดลึกเกินไป ก็จับเรือได้ตรงที่มันอยู่จริง การเปลี่ยนแค่นี้อย่างเดียวได้เครดิตว่าเพิ่มอัตราการจมของการโจมตีที่ยิงเข้าเป้าขึ้นราวเท่าตัว (INFORMS, Blackett profile) ไม่มีใครสร้างอาวุธใหม่ ไม่มีใครคิดยุทธวิธีใหม่ มีคนมองตัวเลขที่อยู่ในตู้เอกสารอยู่แล้ว และถามคำถามที่คมกว่าเดิมกับมัน
บทนี้ว่าด้วยการค้นพบข้อเดียว และควรพูดตรงๆ ก่อนเรื่องเล่าจะกองสุมกัน: ในเบ้าหลอมของสงครามโลกครั้งที่สอง นักฟิสิกส์ นักสถิติ และนักเศรษฐศาสตร์กลุ่มเล็กๆ ที่กระจัดกระจายตระหนักว่าสงคราม — และไม่นานหลังจากนั้น ธุรกิจ เกษตรกรรม และวิศวกรรม — เต็มไปด้วยการตัดสินใจที่*ดูเหมือน*เป็นเรื่องของประสบการณ์และความกล้า แต่แท้จริงคือโจทย์การหาค่าเหมาะที่สุด (optimisation) ที่สวมเครื่องแบบมา มองเห็นแบบนั้นแล้ว ก็แก้ด้วยเลขคณิตแทนสัญชาตญาณได้ โจทย์กองเรือกับโจทย์ระเบิดลึกดูไม่เหมือนกันเลยที่ผิวหน้า ข้างใต้คือท่าเดียวกัน: วัดสิ่งที่เกิดขึ้นจริง ไม่ใช่สิ่งที่สมมติว่าเกิด แล้วให้การวัด — ไม่ใช่สัญชาตญาณของทหารผ่านศึก — เป็นผู้เลือกตัวเลข
เครื่องบินทิ้งระเบิดที่ไม่ได้กลับบ้าน
อีกฟากมหาสมุทร Abraham Wald นักคณิตศาสตร์ กำลังแก้โจทย์รูปทรงเดียวกันแต่รสชาติต่างกันมาก ชื่อของเขาติดอยู่กับเกร็ดที่ถูกเล่าซ้ำมากที่สุดเรื่องหนึ่งในสถิติประยุกต์ตั้งแต่นั้นมา — เรื่องที่คุ้มจะเล่า*และ*คุ้มจะแก้ให้ถูก เพราะตัวการแก้เองคือบทเรียนของแก่นความคิดในหนังสือเล่มนี้
เวอร์ชันที่ทุกคนเคยได้ยินเป็นแบบนี้: กองทัพบกสหรัฐฯ อยากติดเกราะเครื่องบินทิ้งระเบิดโดยไม่ให้หนักจนบินไม่ขึ้น จึงนำข้อมูลมาให้ Wald ว่าเครื่องที่บินกลับมาเสียหายตรงไหน — ส่วนใหญ่ที่ลำตัวและปีก น้อยครั้งที่ใกล้เครื่องยนต์ — และเตรียมเสริมเกราะที่ลำตัว เรื่องเล่าว่า Wald บอกพวกเขาว่าคิดกลับหัวกลับหาง: ให้ติดเกราะที่เครื่องยนต์ เพราะเครื่องที่ถูกยิงโดน*ตรงนั้น*คือลำที่ไม่ได้กลับมาให้นับ นี่คือเรื่อง "อคติจากผู้รอด (survivorship bias)" และในฐานะภาพประกอบของแนวคิดนี้ มันเกือบสมบูรณ์แบบ
ในฐานะประวัติศาสตร์ เรื่องนี้ถูกแต่งขึ้นเสียเป็นส่วนใหญ่ ปี 2016 Bill Casselman นักคณิตศาสตร์ ไปตามหาแหล่งข้อมูลปฐมภูมิ และพบน้อยมาก: ไม่มีบันทึกคำต่อคำที่ Wald ให้คำแนะนำต่อหน้าห้องที่เต็มไปด้วยนายพล ไม่มีแผนภาพเครื่องบินทิ้งระเบิดพรุนกระสุนที่มีลายมือของ Wald เองอยู่บนนั้น ไม่มีอะไรใกล้เคียงกับฉากมีสีสันที่เล่าซ้ำบนเว็บไซต์นับพัน สิ่งที่รอดมาคือบันทึกช่วยจำจริงของ Wald สำหรับ Statistical Research Group ที่ Columbia เปิดเผยหลายทศวรรษต่อมา ในนั้นมีบางอย่างที่ทั้งดูหนังน้อยกว่าและน่าประทับใจกว่า: กลไกทางเทคนิคสำหรับประมาณ จากรูปแบบรอยกระสุนบนเครื่องที่*รอด*กลับมาเท่านั้น ว่าเครื่องที่ถูกยิงโดน n ครั้งมีความน่าจะเป็นที่จะตกเท่าไร — โดยไม่เคยเห็นเครื่องที่หายไปเลยสักลำ (Bill Casselman, "The Legend of Abraham Wald," AMS Feature Column, 2016; บันทึกช่วยจำต้นฉบับและคำอธิบายมาตรฐานยุคปัจจุบันรวมอยู่ใน Mangel & Samaniego, "Abraham Wald's Work on Aircraft Survivability," Journal of the American Statistical Association 79 (1984)) Wald สมมติว่ากระสุนข้าศึกกระทบเครื่องบินอย่างสุ่มโดยประมาณ แล้วสร้างสมการเรียกซ้ำเชื่อมการแจกแจงรอยกระสุนที่*สังเกตได้*บนผู้รอด เข้ากับประชากรเครื่องบินที่ไม่เคยกลับมาซึ่ง*สังเกตไม่ได้* — เท่ากับแก้หาผีจากการที่มันไม่อยู่ในห้อง เขาไม่เคยบันทึกวรรคทองสั้นๆ เรื่องจะขันเกราะตรงไหนไว้เลย นโยบายที่ SRG ประกาศไว้คือตอบคำถามทางเทคนิคที่ถูกถาม ไม่ออกคำแนะนำทางยุทธวิธี บันทึกปฐมภูมิที่ใกล้ที่สุด จาก W. Allen Wallis ผู้อำนวยการ SRG ระบุเพียงว่า Wald "สมมติบนหลักฐานที่ดีว่ารอยกระสุนในการรบกระจายอย่างสม่ำเสมอทั่วตัวเครื่องบิน" แล้วอนุมานค่าประมาณความเปราะบางจากสมมติฐานนั้น — น่าจะเป็นเมล็ดที่งอกเป็นการเล่าใหม่อันมีสีสันในยุคปัจจุบัน
ทั้งหมดนี้ไม่ได้ทำให้การหยั่งเห็น (insight) ที่อยู่ข้างใต้จริงน้อยลง หรือสำคัญกับหนังสือเล่มนี้น้อยลง การเปลี่ยนกรอบ (reframe) ที่เป็นหัวใจของเรื่อง Wald — เลิกถือว่า "ข้อมูลที่มีอยู่ในมือ" คือ "ข้อมูลทั้งหมดที่มี" แล้วถามว่ากระบวนการอะไรกรองข้อมูลก่อนถึงมือ — คือการเปลี่ยนรูปแบบการแทนปัญหา (representation) ชนิดที่หนังสือเล่มนี้ไล่ล่าอยู่พอดี แต่เวอร์ชันยอดนิยมลูบการให้เหตุผลทางสถิติที่ละเอียดและระมัดระวังชิ้นหนึ่งจนเรียบ เหลือเกร็ดสั้นกระชับที่มีตัวร้าย (นายพลหัวทึบ) และพระเอกที่ปล่อยวรรคทองปิดไมค์ Wald ตัวจริงน่าสนใจกว่า: นักคณิตศาสตร์ที่มองตารางนับรอยกระสุนบนเครื่องบินที่รอด ใช้เพียงสมมติฐานว่ากระสุนไม่เลือกที่ตก แล้วสร้างประชากรที่เขาไม่มีวันได้เห็นขึ้นมาใหม่ นั่นคือเส้นทางที่ยาวกว่าสู่ insight ที่สั้นกว่า และเป็นเรื่องที่สอนได้มากกว่าในสองเรื่องนี้
ไม้อัดของประเทศหนึ่ง เมนูอาหารของอีกประเทศ
ปี 1938 Plywood Trust ในท้องถิ่น สหกรณ์อุตสาหกรรมโซเวียตแห่งหนึ่ง เอาปัญหาจัดตารางที่ฟังดูธรรมดามาให้ Leonid Kantorovich นักคณิตศาสตร์หนุ่มจากเลนินกราด: เครื่องกลึงแปดเครื่อง ไม้วีเนียร์ห้าชนิด และข้อเรียกร้องให้คง*อัตราส่วน*ของไม้อัดทั้งห้าชนิดไว้คงที่ พร้อมทำผลผลิตรวมให้มากที่สุด โจทย์นี้ไม่มีความเกี่ยวข้องกับสงครามให้เห็นเลย ขณะที่คณะละครสัตว์ของ Blackett จูนระเบิดลึกอยู่ วิศวกรของทรัสต์เองลองและปรับแล้วก็หาคำตอบที่น่าพอใจไม่ได้
Kantorovich เห็นว่าโจทย์นี้ไม่ได้เกี่ยวกับเครื่องกลึงจริงๆ และข้อสังเกตนี้สำคัญไกลเกินไม้อัด สถานการณ์ใดก็ตามที่ต้องจัดสรรทรัพยากรกองหนึ่งที่มีจำกัดให้การใช้งานที่แข่งกันอยู่ ภายใต้ความสัมพันธ์แบบเส้นตรง (linear) ระหว่างปัจจัยเข้ากับผลผลิต มีโครงกระดูกเดียวกันหมด ไม่ว่าทรัพยากรจะเป็นชั่วโมงแรงงาน ตันของเหล็ก เฮกตาร์ของที่นา หรือเวลาเครื่องจักร ปี 1939 เขาตีพิมพ์ The Mathematical Method of Production Planning and Organization แสดงว่าโจทย์การจัดสรรกลุ่มใหญ่มากเขียนเป็นสมการเดียวได้: หาค่าสูงสุด (หรือต่ำสุด) ของฟังก์ชันเชิงเส้นของตัวแปรจำนวนมาก ภายใต้ข้อจำกัดเชิงเส้น (MacTutor History of Mathematics, biography of Kantorovich) เขาเรียกเทคนิคนี้ว่ากำหนดการเชิงเส้น (linear programming) ก่อนที่ชื่อนี้จะมีในโลกตะวันตก เขาไม่มีแผนที่ว่าจะ*แก้*เวอร์ชันทั่วไปอย่างมีประสิทธิภาพได้อย่างไร — มีเพียงการมองเห็นว่าเวอร์ชันทั่วไปนั้นมีอยู่ และอุตสาหกรรมโซเวียตเต็มไปด้วยสำเนาปลอมตัวของมัน หลายทศวรรษต่อมา ปี 1975 เขาร่วมรับรางวัลโนเบลสาขาเศรษฐศาสตร์จากการหยั่งเห็นข้อนี้พอดี (Britannica, "Leonid Vitalyevich Kantorovich") — นักคณิตศาสตร์โซเวียตที่รางวัลเศรษฐศาสตร์ของตะวันตกยอมรับ เพราะมองเห็นในโรงงานไม้อัดรูปทรงของโจทย์ที่สุดท้ายจะเดินห่วงโซ่อุปทานทั้งสองฝั่งม่านเหล็ก
George Stigler นักเศรษฐศาสตร์อเมริกัน เดินชนโจทย์รูปทรงเดียวกันจากประตูคนละบาน อีกฟากมหาสมุทรและไม่รู้เรื่องงานของ Kantorovich ปี 1945 เขาถามว่าชายที่กระฉับกระเฉงพอประมาณคนหนึ่งจะกินให้ถูกที่สุดได้อย่างไร โดยยังได้สารอาหารเก้าชนิดตามที่ U.S. National Research Council แนะนำ และเลือกได้อิสระจากอาหาร 77 รายการ ไม่มีวิธีที่รู้จักกันตอนนั้นหาชุดอาหารที่ถูกที่สุดจริงได้ตรงๆ Stigler จึงค้นด้วยมือในชุดผสมที่ดูมีแววจำนวนจำกัด แล้วรายงานอาหารชุดหนึ่ง — แป้งสาลี นมข้นระเหย กะหล่ำปลี ผักโขม ถั่วขาวแห้ง — ราคา 39.93 ดอลลาร์ต่อปีตามราคาปี 1939 (Wikipedia, "Stigler diet") เขารู้ว่าเจอคำตอบที่ดีชุดหนึ่ง ไม่จำเป็นต้องเป็นชุดที่ดีที่สุด และเขาพูดออกมาตรงๆ
วิธีที่กลืนโจทย์ทั้งหมด
สองปีต่อมา George Dantzig นักคณิตศาสตร์อเมริกัน ให้คำตอบทั่วไปแก่โจทย์อาหารของ Stigler และทุกโจทย์ที่มีรูปทรงเดียวกัน เส้นทางที่เขาไปถึงจุดนั้นมีเรื่องต้นกำเนิดที่มีหลักฐานดีของตัวเอง แยกจากเรื่องที่ภายหลังจะมาติดกับชื่อเขา
วิธีซิมเพล็กซ์ของ Dantzig เกิดจากระบบราชการยามสงคราม เขาเป็นนักสถิติหนุ่มของกองทัพอากาศบกสหรัฐฯ และชำนาญกลไกของการวางแผนโลจิสติกส์ที่ทำด้วยมือบนเครื่องคิดเลขตั้งโต๊ะ ทีละแผน มิถุนายน 1947 เขาสร้างแบบจำลองทั่วไปสำหรับโจทย์วางแผนพวกนี้เป็นระบบอสมการเชิงเส้น สิงหาคมปีนั้นเขาคิดอัลกอริทึมซิมเพล็กซ์ขึ้นมาแก้มัน — เดินอย่างเป็นระบบและมีประสิทธิภาพไปตามขอบของรูปทรงเรขาคณิตที่ข้อจำกัดของโจทย์ก่อขึ้น จนถึงมุมที่เหมาะที่สุด (George Dantzig, "Origins of the Simplex Method," ACM, 1990; MacTutor biography of Dantzig) ภายในไม่กี่เดือน เพื่อนร่วมงานที่ RAND เปลี่ยนชื่อสาขาของเขาเป็น "กำหนดการเชิงเส้น" ("linear programming") และปี 1951 วิธีนี้ก็เผยแพร่สู่สาธารณะ
ชุดอาหารต้นทุนต่ำสุดจริงถูกกว่าค่าประมาณที่ Stigler ค้นด้วยมือเพียงราว 24 เซนต์ต่อปี ฤดูใบไม้ร่วงปีเดียวกันนั้น Jack Laderman นักวิจัยที่ National Bureau of Standards ตัดสินใจทดสอบความทนของอัลกอริทึมใหม่เอี่ยมนี้กับอินสแตนซ์จริงที่ยากที่สุดเท่าที่หาได้: โจทย์อาหารของ Stigler ข้อจำกัดทางโภชนาการเก้าข้อบนอาหารเจ็ดสิบเจ็ดรายการ ทีมหนึ่งใช้เวลาราว 120 คน-วันบดเลขคณิตของวิธีซิมเพล็กซ์ด้วยเครื่องคิดเลขตั้งโต๊ะแบบหมุนมือ — ตอนนั้นยังอีกหลายปีกว่าคอมพิวเตอร์อิเล็กทรอนิกส์อเนกประสงค์จะเป็นของธรรมดา — และได้ตัวเลขนั้นออกมา (Wikipedia, "Stigler diet"; George Dantzig, INFORMS oral history) สัญชาตญาณของ Stigler ที่ลับด้วยวิจารณญาณของนักเศรษฐศาสตร์ เข้าใกล้ค่าเหมาะที่สุดจนต่างกันแค่เศษปัดเศษ แต่วิธีซิมเพล็กซ์ไปถึงตรงนั้น*ด้วยขั้นตอนวิธี* ขั้นตอนที่ใช้ได้ไม่ว่าโจทย์ถัดไปจะเป็นอาหาร โรงไม้อัด หรือปฏิบัติการทิ้งระเบิด และยังใช้ได้เมื่อจำนวนตัวแปรไต่ขึ้นถึงหลักพัน แล้วหลักล้าน
ชื่อของ Dantzig ยังติดอยู่กับเกร็ดอีกเรื่องที่เก่ากว่าและไม่เกี่ยวข้องกัน เรื่องนี้สมควรเล่าพร้อมวันที่ที่ถูกต้อง ไม่ใช่พับรวมเข้ากับเรื่องซิมเพล็กซ์ ปี 1939 Dantzig เป็นนักศึกษาปริญญาเอกปีหนึ่งสาขาสถิติที่ Berkeley เขามาสายในคาบบรรยายของ Jerzy Neyman ลอกโจทย์สองข้อที่เขียนด้วยชอล์กไว้บนกระดานดำลงมา และเข้าใจว่าเป็นการบ้านประจำสัปดาห์ เขาพบว่ามันยากกว่าปกติ แต่ก็ส่งคำตอบไม่กี่วันถัดมา จริงแล้วมันคือโจทย์สองข้อในสถิติเชิงคณิตศาสตร์ที่ไม่มีใครแก้ได้มานาน Dantzig ไม่รู้เรื่องนี้ จึงไม่เคยถูกทำให้ท้อที่จะลอง และแก้ได้ทั้งสองข้อ แก่นของเรื่องตรวจสอบแล้วเป็นจริง ส่วนรายละเอียดประดับที่แพร่หลายกันมาก (ข้อสอบไล่สิบข้อ คำอ้างว่า "แม้แต่ Einstein" ก็ทำโจทย์พวกนี้ไม่ได้) ไม่จริง และตามรอยไปพบว่ามาจากการเล่าใหม่แบบเสริมดราม่าในภายหลังของนักเทศน์ทางโทรทัศน์คนหนึ่ง ไม่ใช่จากตัว Dantzig เอง (Snopes, "The Legend of the 'Unsolvable Math Problem'") บทเรียนที่ Dantzig ดึงออกมาเอง — การไม่รู้ว่าโจทย์หนึ่งควรจะเป็นไปไม่ได้ บางครั้งคือเหตุผลเดียวที่แก้มันได้ — เป็นของแก่นความคิดในหนังสือเล่มนี้ในสิทธิ์ของมันเอง: กรอบที่ล้อมโจทย์อยู่ รวมถึงกรอบว่า*คนเชื่อกันว่ามันยากแค่ไหน* เป็นส่วนหนึ่งของสิ่งที่ทำให้พื้นที่ใหญ่หรือเล็ก
ชื่อที่ตั้งไว้ซ่อนคณิตศาสตร์
ไอเดียที่สุดโต่งที่สุดอย่างเงียบๆ จาก RAND Corporation ในทศวรรษนี้เป็นของ Richard Bellman และตามคำบอกเล่าของ Bellman เอง มันเริ่มต้นในฐานะการพรางตัว
แผนโดยรวมที่เหมาะที่สุดต้องเหมาะที่สุดสำหรับแผนย่อยทุกแผนที่มันบรรจุอยู่ด้วย เริ่มนับจากตรงไหนก็ตามที่บังเอิญยืนอยู่กลางทาง — นี่คือการหยั่งเห็นทางคณิตศาสตร์ข้อสำคัญของ Bellman ภายหลังถูกทำให้เป็นรูปนัยในชื่อ หลักการเหมาะที่สุด (principle of optimality) และพูดออกมาง่ายเมื่อเห็นแล้ว Bellman มาถึง RAND ในปี 1949 กระสับกระส่ายกับเส้นทางวิชาการแบบเดิมอยู่แล้ว และพอถึงปี 1950 ก็ทำงานกับสิ่งที่เขาเรียกว่ากระบวนการตัดสินใจหลายขั้น: โจทย์ที่ลำดับของทางเลือกซึ่งเลือกทีละอย่างต้องรวมกันเป็นผลลัพธ์โดยรวมที่ดี — จัดสรรการลงทุนข้ามปีอย่างไร เดินกระบวนการผ่านขั้นตอนที่ต่อกันอย่างไร วางลำดับของท่าไปสู่เป้าหมายอย่างไร ถ้าช่วงสุดท้ายของทริปถนนที่ดีที่สุดเท่าที่เป็นไปได้จากกรุงเทพฯ ไปเชียงใหม่ผ่านลำปาง เส้นทางที่ดีที่สุดจากลำปางต่อไปเชียงใหม่ก็ต้องเหมาะที่สุดในตัวมันเอง — ถ้ามีเส้นทางที่ดีกว่าจากลำปางอยู่ ก็เอามาแทนแล้วทั้งทริปดีขึ้น สิ่งนี้ทำให้นักแก้ปัญหาแตกโจทย์หลายขั้นขนาดใหญ่เป็นโซ่ของโจทย์เล็กๆ แก้ย้อนกลับจากเป้าหมาย แต่ละข้อง่ายเมื่อรู้คำตอบของข้อที่ตามมันมาแล้ว Bellman เรียกเทคนิคนี้ว่ากำหนดการพลวัต (dynamic programming) และสมการเชิงฟังก์ชันที่สร้างบนหลักการเหมาะที่สุดยังคงเป็นหนึ่งในเครื่องยนต์อเนกประสงค์ไม่กี่ตัวสำหรับแก้โจทย์การตัดสินใจแบบลำดับในเศรษฐศาสตร์ วิศวกรรม และ — บทที่ 10 จะแสดงให้เห็น — การเรียนรู้แบบเสริมกำลัง มาจนถึงทุกวันนี้
เส้นเวลาไม่ลงรอยกับคำบอกเล่าของ Bellman เรื่องตัวชื่อ ในอัตชีวประวัติปี 1984 ที่ Stuart Dreyfus คัดมาบางส่วน Bellman อธิบายว่าเขาต้องการป้ายชื่อที่ไม่ฟังดูเหมือน "การวิจัยทางคณิตศาสตร์" เจ้านายสูงสุดของ RAND ที่กระทรวงกลาโหม — "รัฐมนตรี Wilson" คนหนึ่ง ซึ่งในคำของ Bellman "กลัวและเกลียดคำว่า research อย่างเป็นโรค" — ต้องไม่ถูกปล่อยให้สงสัยว่าเขากำลังจ่ายเงินสนับสนุนคณิตศาสตร์บริสุทธิ์ Bellman จึงเลือกคำว่า programming คำที่ให้เสียงปฏิบัติจริงและไม่คุกคาม กับ dynamic คำคุณศัพท์ที่เขาตัดสินว่าใช้ในแง่ลบไม่ได้ แล้วรวมเป็นร่มคำที่ "แม้แต่สมาชิกสภาคองเกรสก็ค้านไม่ได้" (Stuart Dreyfus, "Richard Bellman on the Birth of Dynamic Programming," Operations Research 50, no. 1 (2002) อ้าง Eye of the Hurricane ของ Bellman ปี 1984) เป็นเรื่องที่วิเศษมากเกี่ยวกับข้าราชการที่ตีความตรงตัวเกินกว่าจะทนคำว่า "research" ได้ ปัญหาอยู่ที่ปฏิทิน: บทความตีพิมพ์ชิ้นแรกของ Bellman เองที่ใช้คำว่า "dynamic programming" ปรากฏใน Proceedings of the National Academy of Sciences เดือนสิงหาคม 1952 (Bellman, "On the Theory of Dynamic Programming," PNAS 38, no. 8 (1952)) — ขณะที่ Charles Wilson รัฐมนตรีกลาโหมที่ Bellman เอ่ยชื่อ ยังไม่เข้ารับตำแหน่งจนกระทั่งมกราคม 1953 บล็อกเกอร์และนักประวัติศาสตร์ที่ตามความไม่ลงรอยนี้ตั้งข้อสังเกตว่าเรื่องตามที่เล่ากันมาคลาดเคลื่อนไปอย่างน้อยหนึ่งปี (see the discussion at Arcane Sentiment, "Why 'dynamic programming'?") Bellman อาจแค่จำผิดว่าเจ้าหน้าที่คนไหนทำให้เขาระวังตัว หลังเหตุการณ์ผ่านไปหลายทศวรรษ หรืออาจพับความทรงจำสองชิ้นเป็นชิ้นเดียว — อัตชีวประวัติไม่ใช่คำให้การใต้คำสาบาน และบันทึกความทรงจำของเขาเองก็เตือนไว้ที่อื่นด้วยความรู้ตัวอย่างน่าเอ็นดูว่า "ทั้งหมดนี้มีส่วนทำให้ประวัติศาสตร์แบบที่เล่ากันมามีลักษณะชวนเข้าใจผิด" สิ่งที่ไม่มีข้อสงสัยคือคณิตศาสตร์: หลักการเหมาะที่สุดนั้นจริง ทรงพลัง และทั่วไปเท่าที่ Bellman อ้างไว้พอดี
เมื่อการค้นหาสิ้นหวัง ก็เล่นพนัน
ไม่ใช่ทุกโจทย์ยามสงครามจะยอมแพ้ให้สมการ บางโจทย์พันกับความบังเอิญแน่นเกินไป — นิวตรอนพุ่งผ่านก้อนวัสดุฟิสไซล์ ชน กระเจิง และบางครั้งจุดชนวนการชนอีกครั้ง — จนไม่มีสูตรไหนจับพฤติกรรมของมันในรูปปิดได้ และค้นหาให้ครบถ้วนก็เป็นไปไม่ได้เลย แม้กับเครื่องคำนวณขนาดเท่าห้อง
ทางออกมาจากเกมไพ่ ตามคำบอกเล่าของ Stanislaw Ulam เอง ปี 1946 เขาพักฟื้นจากการเจ็บป่วยและเล่นไพ่คนเดียวแบบ Canfield ไม่รู้จบ Ulam สงสัยว่าสำรับที่สับแล้วมีสัดส่วนเท่าไรที่ชนะได้จริง อนุมานด้วยการวิเคราะห์เชิงการจัดหมู่ไม่สำเร็จ เขาจึงเห็นว่าเส้นทางเร็วที่สุดสู่ค่าประมาณที่ดีคือวางไพ่หลายๆ ตาแล้วนับเอา ถ้าคำนวณความน่าจะเป็นของเหตุการณ์จากหลักการพื้นฐานไม่ได้ ก็มักจะ*จำลอง*เหตุการณ์นั้นหลายๆ ครั้ง แล้วให้ความถี่ยืนแทนความน่าจะเป็นได้ Ulam เอาไอเดียนี้ไปหา John von Neumann ผู้เห็นทันทีว่าลูกไม้เดียวกัน — แทนการคำนวณที่จัดการไม่ไหวด้วยการทดลองสุ่มจำนวนมาก — จำลองการแพร่ของนิวตรอนผ่านแกนระเบิดได้ โจทย์นี้เป็นหัวใจของโครงการระเบิดไฮโดรเจนที่ Los Alamos Nicholas Metropolis ที่ทำงานอยู่ข้างๆ พวกเขา ตั้งชื่อที่อยู่ยืนยงให้เทคนิคตระกูลนี้ตามย่านคาสิโนของโมนาโก เพื่อพยักถึงลุงของ Ulam ที่ว่ากันว่าอดใจไม่ไปที่นั่นไม่เคยได้ (Los Alamos National Laboratory, "Hitting the Jackpot: The Birth of the Monte Carlo Method")
วิธีมอนติคาร์โล (Monte Carlo) คือคำสารภาพและทางเลี่ยงในเวลาเดียวกัน ในคำศัพท์ของหนังสือเล่มนี้ สารภาพว่าพื้นที่ใหญ่เกินไปหรือพันกันเกินกว่าจะค้นหรือคำนวณอย่างแม่นยำได้ และเลี่ยงด้วยการแลกคำตอบแม่นยำที่รับประกันได้ กับคำตอบที่น่าจะดีและได้มาเร็ว มันคือการเดิมพันแบบเดียวกับที่นักสำรวจความคิดเห็นทำเมื่อสอบถามผู้มีสิทธิ์เลือกตั้งหนึ่งพันคนแทนที่จะเป็นสี่สิบล้านคน เพียงแต่ใช้กับฟิสิกส์แทนการเมือง — และมันจะกลายเป็นเครื่องมือมาตรฐานชิ้นหนึ่งของการคำนวณสมัยใหม่ ถูกเรียกใช้ทุกครั้งที่โครงสร้างที่แน่นอนของโจทย์ต้านการวิเคราะห์ แต่*ผลลัพธ์*ของมันสุ่มตัวอย่างได้ในราคาถูก
โจทย์เดียว หลายเครื่องแต่งกาย
รูปแบบเดียวปรากฏขึ้นเมื่อถอยออกจากเรื่องเล่าแต่ละเรื่อง และมันเกือบจะน่าขนลุก ทีมนักฟิสิกส์คำนวณชนวนระเบิดลึก นักสถิติสร้างความสูญเสียของเครื่องบินที่มองไม่เห็นขึ้นมาใหม่ นักคณิตศาสตร์โซเวียตจัดตารางเครื่องกลึงไม้อัด นักเศรษฐศาสตร์อเมริกันตั้งราคาอาหารประทังชีวิต นักศึกษาบัณฑิตศึกษาหนุ่มที่ Berkeley แก้โจทย์ที่เขาไม่รู้ว่าโด่งดัง ที่ปรึกษาของ RAND ซ่อนแคลคูลัสไว้ในชื่อที่ปลอดภัยทางการเมือง คนไข้พักฟื้นเล่นไพ่คนเดียว ไม่มีใครในนี้ทำงานกับ "โจทย์เดียวกัน" ในความหมายที่คนทั่วไปจะรับรู้ได้เลย กระนั้น เครื่องกลึงของ Kantorovich ของชำของ Stigler และโลจิสติกส์กองทัพบกของ Dantzig กลับเป็นวัตถุทางคณิตศาสตร์ชิ้นเดียว — กำหนดการเชิงเส้น — ในสามชุดปลอมตัว Bellman แสดงว่าการตัดสินใจแบบลำดับตระกูลใหญ่ ตั้งแต่ตารางการลงทุนถึงเส้นทางที่สั้นที่สุด ใช้โครงกระดูกเรียกซ้ำเดียวกัน และสิ่งที่ Wald กับ Ulam ให้ไว้ล้วนเท่ากับสกัดสัญญาณออกจากกระบวนการที่ใหญ่หรือถูกบังเกินกว่าจะสังเกตตรงๆ ได้
representation พกพาได้ — นี่คือการค้นพบของทศวรรษในบทนี้ และเป็นสิ่งที่เปลี่ยนการแก้ปัญหาจากงานฝีมือให้เป็นสาขาวิศวกรรม พิสูจน์แล้วว่าการจัดสรรทรัพยากร การวางแผนอาหาร และการจัดตารางโรงงานคือสมการเดียวกัน ก็ไม่ต้องมีทฤษฎีใหม่สำหรับแต่ละอย่าง — ต้องการตัวแก้ตัวเดียว ใช้สามครั้ง นี่ยังเป็นเหตุผลที่หน่วยของการปรับให้เหมาะที่สุดเลิกเป็นอาวุธชิ้นเดียว กองเรือชุดเดียว หรือสายการผลิตสายเดียว และกลายเป็น*ระบบ*: กองเรือทั้งกองเรือ หลักนิยมระเบิดลึกทั้งหลักนิยม ห่วงโซ่อุปทานทั้งห่วงโซ่ ปรับความเร็วของเรือลำเดียวให้เหมาะที่สุดคือลูกไม้เฉพาะถิ่น ปรับเรขาคณิตของกองเรือให้เหมาะที่สุดคือ insight ระดับระบบที่ช่วยระวางบรรทุกไว้ได้ทั้งมหาสมุทร นักวิจัยดำเนินงาน (operational research) แห่งทศวรรษ 1940 คือคนกลุ่มแรกที่ได้เงินเดือนเต็มเวลาเพื่อถามว่า "รูปทรงจริงของโจทย์นี้คืออะไร" ก่อนจะแตะคันโยกสักคัน — และคำตอบ ครั้งแล้วครั้งเล่า คือรูปทรงนั้นเล็กกว่าและทั่วไปกว่าที่ใครก็ตามที่ทำงานด้วยความรู้สึกเคยสงสัย
ท่าประจำบท
Move 04 — ปรับทั้งระบบ และวัดก่อนปรับ
- ลากขอบเขตให้กว้างก่อนจะลากข้อสรุปสักข้อ ทีมของ Blackett ไม่ได้ถามว่า "จะปกป้องเรือลำนี้อย่างไร" — พวกเขาถามว่า "จะปกป้องกองเรือนี้อย่างไร" และคำตอบที่ถูกของคำถามที่กว้างกว่า (กองเรือใหญ่ขึ้น) คือตรงข้ามกับคำตอบที่ถูกของคำถามที่แคบกว่า ไม่ว่าจะถูกล่อให้ปรับหน่วยไหนให้เหมาะที่สุด — งานหนึ่งชิ้น เรือหนึ่งลำ เครื่องบินหนึ่งเครื่อง — ให้ถามว่าหน่วยจริงอยู่สูงขึ้นไปอีกชั้นหรือเปล่า
- อย่าเชื่อสัญชาตญาณจนกว่าจะวัดกระบวนการที่ผลิตข้อมูลของคุณแล้ว insight จริงของ Wald ไม่ใช่วรรคทองเรื่องตำแหน่งติดเกราะ มันคือการปฏิเสธที่จะถือว่า "เครื่องบินที่มองเห็นได้" คือ "เครื่องบินทั้งหมดที่มี" ก่อนจะปรับอะไรให้เหมาะที่สุด ให้ถามว่าอะไรกรองตัวอย่างมา
- มองหากำหนดการเชิงเส้น หรือสมการเรียกซ้ำ ที่ซ่อนอยู่ในโจทย์ เครื่องกลึงของ Kantorovich ของชำของ Stigler และโลจิสติกส์ของ Dantzig คือสมการเดียวที่สวมเสื้อสามตัว เมื่อโจทย์รู้สึกเหมือนถูกตัดเย็บมาเฉพาะ ให้ตรวจว่ามีตัวแก้ทั่วไปที่รู้จักกันอยู่แล้วสวมพอดีกับมันหรือไม่
- เมื่อการค้นหาแบบแม่นยำสิ้นหวัง ให้สุ่มตัวอย่างแทนการเดา ไพ่คนเดียวของ Ulam และการจำลองนิวตรอนของ Metropolis เปลี่ยนการคำนวณที่ตอบไม่ได้ให้เป็นการทดลองที่นับได้ การทดลองอย่างซื่อสัตย์จำนวนมากชนะการเดาอย่างมั่นใจครั้งเดียว
ต่อไป — บทที่ 05 · เส้นทางแบบอัลกอริทึม: การค้นหาที่วิจัยดำเนินงานทำด้วยไม้บรรทัดเลื่อน คนอีกรุ่นจะทำด้วยเครื่องจักร — และเครื่องจักรกลุ่มแรกที่ค้นหาได้ก็จะต้องการทฤษฎีของตัวเอง
บทถัดไป · 6 / 1205 · เส้นทางแบบอัลกอริทึม