05 · เส้นทางแบบอัลกอริทึม
เส้นทางที่สั้นที่สุด — ประวัติศาสตร์ของศิลปะและศาสตร์แห่งการแก้ปัญหา
อัมสเตอร์ดัม ระเบียงร้านกาแฟ ปี 1956
อัลกอริทึมที่ยังเป็นคำตอบตั้งต้นของคอมพิวเตอร์ทุกเครื่องเมื่อต้องหาทางที่ถูกที่สุดจากที่นี่ไปที่นั่น ถูกคิดขึ้นในร้านกาแฟ ในเวลาราวยี่สิบนาที Edsger Dijkstra อายุยี่สิบหก ออกไปเดินซื้อของกับ Ria คู่หมั้นของเขา และเหนื่อย เขาเพิ่งรับงานที่ Mathematisch Centrum ในอัมสเตอร์ดัม หน้าที่คือสาธิตคอมพิวเตอร์เครื่องใหม่ชื่อ ARMAC เขาต้องการโจทย์ที่ง่ายพอจะอธิบายให้คนนอกสายเทคนิคฟังได้ แต่ก็น่าประทับใจพอจะแสดงว่าเครื่องนี้คุ้มค่าที่เลี้ยงไว้ พอนั่งลงดื่มกาแฟ ไม่มีดินสอ ไม่มีกระดาษ ไม่มีห้องสมุดให้ค้น เขาตั้งคำถามกับตัวเองว่าเส้นทางที่สั้นที่สุดระหว่างเมืองดัตช์สองเมืองคือเส้นไหน ตัวเลขยี่สิบนาทีมาจากปากเขาเองในภายหลัง (David Gries, "Edsger Dijkstra and the Shortest-Path Algorithm," Cornell CS) วิธีที่เขาร่างเช้าวันนั้นมีสองก้าว — ขยายกลุ่มเมืองที่รู้ระยะสั้นที่สุดจากจุดตั้งต้นแน่นอนแล้ว และทุกก้าวเพิ่มเมืองที่ยังไม่ได้ไปซึ่งตอนนี้ใกล้ที่สุดเข้าไป — เจ็ดทศวรรษให้หลังยังไม่มีใครแทนมัน เขาไม่ได้ตีพิมพ์จนอีกสามปีต่อมา และตีพิมพ์เป็นโน้ตสามหน้าที่เขียนอย่างประหยัด แก้ปัญหากราฟสองข้อที่ไม่เกี่ยวกันเลย ในเนื้อที่ที่บทความส่วนใหญ่ใช้เขียนแค่บทคัดย่อ (Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik 1 (1959))
หนังสือชื่อ เส้นทางที่สั้นที่สุด เดินมาถึงบทที่ห้าแล้วเจออัลกอริทึมที่ตั้งชื่อตามการหาเส้นทางสั้นที่สุดตรงๆ คิดขึ้นระหว่างจิบกาแฟ ในเวลาน้อยกว่าที่ใช้อ่านย่อหน้านี้สองรอบ ความสมมาตรนี้น่าพอใจ เกือบจะเรียบร้อยเกินไป แต่มันเป็นของจริง ไม่ได้จัดฉาก และมันคือบานพับที่บทนี้หมุนอยู่บน บทที่ 04 แสดงให้เห็นนักวิทยาศาสตร์รุ่นหนึ่งค้นพบว่าปัญหาในโลกจริง — กองเรือคุ้มกัน สูตรอาหาร โรงงาน — จับใส่กรอบเป็นวัตถุทางคณิตศาสตร์แล้วแก้ด้วยขั้นตอนวิธีอเนกประสงค์ได้ บทนี้ว่าด้วยสิ่งที่เกิดขึ้นต่อจากนั้น: ขั้นตอนวิธีเหล่านั้นเองกลายเป็นวัตถุที่ถูกศึกษา คำถามเปลี่ยนจาก "มีวิธีอยู่ไหม" เป็น "วิธีที่ ดีแค่ไหน จึงจะมีอยู่ได้ และเราจะรู้ได้อย่างไร" การค้นหา (search) — งานดิบที่ใช้กำลังล้วนลองเดินเส้นทางต่างๆ ผ่านพื้นที่ของความเป็นไปได้ — กลายเป็นวิชาที่มีทฤษฎีของตัวเอง มีบทพิสูจน์ของตัวเอง และในที่สุดก็มีเครื่องจักรของตัวเอง
ชายผู้มีชื่อกลายเป็นคำศัพท์
สิ่งที่ Dijkstra ทำเช้าวันนั้น — คิดขั้นตอนทีละก้าวที่รับประกันว่าจะไปถึงคำตอบที่ถูกต้อง — มีชื่อเรียกว่า อัลกอริทึม คำนี้เดินทางอ้อมมายาวก่อนจะลงเอยในห้องเรียนวิทยาการคอมพิวเตอร์
คำนี้มาจากชื่อในรูปละตินของนักปราชญ์ศตวรรษที่เก้าผู้ทำงานอยู่ในบ้านแห่งปัญญา (House of Wisdom) ที่แบกแดด: Muhammad ibn Musa al-Khwarizmi ตำราของเขาว่าด้วยเลขฮินดู-อารบิก ถูกแปลเป็นละตินในชื่อ Algoritmi de numero Indorum มันมอบสองอย่างให้ยุโรปยุคกลาง อย่างแรกคือวิธีคำนวณแบบใหม่ — ระบบทศนิยมเชิงตำแหน่งที่มาแทนเลขโรมัน อย่างที่สองมาช้ากว่า คือคำใหม่คำหนึ่ง: algorismus ตอนแรกหมายถึงเลขคณิตที่ทำด้วยวิธีใหม่นี้โดยเฉพาะ คำว่า "algorithm" ต้องรอถึงศตวรรษที่ยี่สิบจึงขยายมาสู่ความหมายสมัยใหม่: ขั้นตอนวิธีใดๆ ที่มีจำนวนก้าวจำกัด ไม่กำกวม และเครื่องจักรทำตามได้ สำหรับแก้ปัญหาทั้งชั้น (findanexpert.unimelb.edu.au, "Why are algorithms called algorithms?"; NPR, "How 'algorithm' got its name from a 9th-century Persian mathematician") หนังสือเล่มใหญ่อีกเล่มของ al-Khwarizmi มอบคำว่า algebra ให้คณิตศาสตร์ มาจาก al-jabr ที่แปลว่า "การเติมให้ครบ" หรือ "การคืนสภาพ" — ศัพท์เรียกการย้ายปริมาณจากข้างหนึ่งของสมการไปอีกข้างหนึ่ง ความต่างจากอาลักษณ์ในบทที่ 01 อยู่ตรงนี้: อาลักษณ์จดโจทย์ที่แก้แล้วทีละข้อไว้เป็นตัวอย่างสอน; al-Khwarizmi จด ตัวขั้นตอนวิธีเอง ถอดตัวเลขเฉพาะออกหมด เพื่อให้เอาไปใช้กับตัวเลขที่ยังไม่มีใครนึกถึงได้ วิธีในฐานะวัตถุที่มีสถานะของตัวเอง ยกไปใช้ได้กับทุกอินสแตนซ์ (instance) ของปัญหา — นามธรรมข้อนี้คือบรรพบุรุษสายตรงของทุกอย่างในบทนี้
ท่าพื้นฐาน: กวาดออกไปรอบตัว กับดำดิ่งลงลึก
ใต้อัลกอริทึมของ Dijkstra มีกลยุทธ์พื้นฐานกว่าอีกสองอย่างสำหรับสำรวจพื้นที่ของความเป็นไปได้ ทั้งสองมาก่อนมัน ควรเรียกชื่อให้ชัด เพราะทุกอย่างที่ซับซ้อนกว่านั้นในบทนี้สร้างขึ้นจากสองอย่างนี้
เริ่มจากเขาวงกต หรือแผนผังตระกูล หรือใยความสัมพันธ์ของเพื่อนฝูง แทนด้วยวิธีเดียวกับที่บทที่ 02 เล่าว่า Euler แทน Königsberg: เป็นกราฟของโหนดกับเส้นเชื่อม ค้นตามความกว้าง (breadth-first search, BFS) เริ่มที่โหนดหนึ่งแล้วสำรวจออกไปเป็นวงที่ขยายกว้างขึ้น — ทุกอย่างที่ห่างหนึ่งก้าวก่อน แล้วทุกอย่างที่ห่างสองก้าว ไล่ไปเรื่อยๆ ผลคือการรับประกันข้อหนึ่ง: ครั้งแรกที่มันไปถึงโหนดใดก็ตาม มันได้พบเส้นทาง*ที่สั้นที่สุด*ไปยังโหนดนั้นแล้ว วัดด้วยจำนวนก้าว Edward F. Moore คิดมันขึ้นใหม่เพื่อจุดประสงค์นี้พอดีในปี 1959 เขาต้องการวิธีเชิงกลไกในการหาทางออกที่สั้นที่สุดจากเขาวงกต ไอเดียคล้ายกันฝังอยู่ก่อนแล้วโดยไม่ได้ตีพิมพ์ ในวิทยานิพนธ์ปริญญาเอกปี 1945 ของ Konrad Zuse ที่ถูกปฏิเสธ (Wikipedia, "Breadth-first search") ค้นตามความลึก (depth-first search, DFS) ทำตรงกันข้าม: เลือกเส้นทางเดียวแล้วเดินตามให้ไกลที่สุดก่อนถอยกลับ — ดำดิ่งลงช่องทางหนึ่งของเขาวงกตจนสุดทาง แล้วจึงลองช่องอื่น มันไม่รับประกันว่าจะพบเส้นทางสั้นที่สุด แต่ใช้หน่วยความจำน้อยกว่ามาก และในมือของ Robert Tarjan กับ John Hopcroft ช่วงต้นทศวรรษ 1970 มันปลดล็อกคำตอบที่มีประสิทธิภาพให้ปัญหากราฟหลายชนิดที่ไม่มีใครคาด ตั้งแต่ทดสอบว่าแผนที่หนึ่งวาดโดยไม่มีเส้นตัดกันได้หรือไม่ ไปจนถึงหาจุดอ่อนเชิงโครงสร้างของเครือข่าย (Wikipedia, "Depth-first search")
ทั้งสองกลยุทธ์ไม่รู้อะไรเลยเกี่ยวกับปัญหาที่กำลังแก้ นอกจากรูปร่างเปล่าๆ ของกราฟ ความไม่รู้นั้นคือจุดแข็ง — ใช้ได้กับกราฟทุกชนิด — และคือจุดอ่อน: มันผลาญแรงไปกับทิศทางที่ใครก็ตามที่เข้าใจปัญหาจริงๆ จะเห็นทันทีว่าไร้ความหวัง อัลกอริทึมของ Dijkstra คือญาติที่มีวินัยกว่าของ BFS มันไม่ขยายทีละวง แต่มุ่งไปยังโหนดที่ยังไม่ได้ไปซึ่งตอนนี้ไปถึงได้ถูกที่สุดเสมอ นั่นคือเหตุผลที่มันไม่ได้แค่หาเส้นทางสั้น*เส้นหนึ่ง* แต่พิสูจน์ได้ว่าเป็นเส้น*ที่สั้นที่สุด* สำหรับกราฟใดก็ตามที่ระยะทางไม่เคยติดลบ
หนูตัวหนึ่งชื่อ Theseus
หกปีก่อนกาแฟถ้วยนั้นของ Dijkstra ที่ Bell Labs ในปี 1950 Claude Shannon สร้างอนุสาวรีย์ของไอเดียเดียวกันที่เล็กกว่าและแปลกกว่า เขามีชื่อเสียงอยู่แล้วจากการก่อตั้งทฤษฎีสารสนเทศ สิ่งที่เขาสร้างคือหนูกลไกแก้เขาวงกต เขาตั้งชื่อมันว่า Theseus ตามวีรบุรุษผู้หาทางในเขาวงกตของมิโนทอร์ด้วยการคลี่เส้นด้ายทิ้งไว้ข้างหลัง
ในเชิงกลไก Theseus คือแม่เหล็กหุ้มเปลือกโลหะ มันถูกลากไปใต้เขาวงกตขนาดห้าคูณห้าที่ปรับผังใหม่ได้ ด้วยแม่เหล็กไฟฟ้าที่ซ่อนอยู่ใต้พื้น แม่เหล็กไฟฟ้านั้นถูกขับด้วยแผงรีเลย์โทรศัพท์ที่ทำหน้าที่เป็นหน่วยความจำ ปล่อยเข้าเขาวงกตที่ไม่คุ้นเคย หนูจะเดินซุ่มซ่ามไปข้างหน้า ชนกำแพง ถอยหลัง ลองใหม่ — DFS พร้อมการย้อนรอย (backtracking) ในรูปธรรม — จนสะดุดเข้ากับ "ชีส" ชิ้นที่ซ่อนอยู่ ซึ่งทำให้หน้าสัมผัสไฟฟ้าปิดวงจร ทุกการเลี้ยวระหว่างทางถูกบันทึกไว้ในหน่วยความจำรีเลย์ ตั้งกลับไปที่จุดเริ่มต้นของเขาวงกต*อันเดิม* Theseus จะแล่นตรงไปยังเป้าหมายโดยไม่เลี้ยวผิดแม้แต่ครั้งเดียว การค้นหาแบบตาบอดรอบก่อนกลายเป็นคำตอบที่เก็บไว้และใช้ซ้ำได้ (cyberneticzoo.com, "1952 – 'Theseus' Maze-Solving Mouse – Claude Shannon") ตรงนี้ควรหยุดดู เพราะมันคือการสาธิตที่เก่าจริงและเป็นรูปธรรมจริงของไอเดียที่ต่อมาจะนิยามปัญญาของเครื่องจักร: การค้นหาที่ตามด้วยความจำ คือการเรียนรู้ รอบแรกจ่ายราคาเต็มของการสำรวจพื้นที่ ทุกรอบหลังจากนั้นใช้ความรู้ที่เก็บไว้แทนการจ่ายซ้ำ นี่คือการหยั่งเห็น (insight) เดียวกัน ในขนาดจิ๋วและในสายทองแดง ที่ทำให้กำหนดการพลวัต (dynamic programming) ของ Bellman (บทที่ 04) ไม่ต้องแก้ปัญหาย่อยที่เหมือนกันซ้ำ และที่ทำให้โปรแกรมหมากรุกในบทที่ 10 จำตำแหน่งที่มันประเมินไปแล้วได้
การมองโลกในแง่ดีที่ไม่เคยโกหก
ความครบถ้วนของอัลกอริทึมของ Dijkstra คือขีดจำกัดของมันด้วย มันไล่ครบทุกโหนดภายในแนวหน้าที่กำลังขยาย ไม่เคยข้ามโหนดที่อาจกลายเป็นเรื่องสำคัญ บนกราฟที่มีโหนดเป็นล้าน การสำรวจ "ทุกอย่างที่ใกล้กว่าค่าดีที่สุดตอนนี้" ก่อนจะพิจารณาอะไรที่ไกลกว่านั้น ผลาญแรงไปในทุกทิศที่ไม่เกี่ยวกับที่ที่ตั้งใจจะไปจริงๆ
ทางแก้มาถึงในปี 1968 จากโครงการหุ่นยนต์ที่ Stanford Research Institute นักวิจัยสามคน Peter Hart, Nils Nilsson และ Bertram Raphael ต้องการให้หุ่นยนต์เคลื่อนที่ชื่อ Shakey — หนึ่งในเครื่องจักรรุ่นแรกที่ให้เหตุผลถึงสิ่งที่ตัวเองทำในห้องจริงได้ — วางแผนเส้นทางอ้อมสิ่งกีดขวางอย่างประหยัด โดยไม่ต้องสำรวจผังพื้นทั้งอาคารทุกครั้ง (Engineering and Technology History Wiki, "Milestones: SHAKEY: The World's First Mobile Intelligent Robot, 1972") อัลกอริทึมของพวกเขาภายหลังได้ชื่อว่า A\ (อ่านว่า "เอ-สตาร์") มันเติมส่วนผสมเพียงหนึ่งอย่างลงในวิธีของ Dijkstra: ในแต่ละก้าว แทนที่จะจัดอันดับโหนดที่ยังไม่สำรวจด้วยระยะทางที่เดินมาถึงมันแล้วล้วนๆ A\ จัดอันดับด้วยระยะทางนั้น บวกกับการเดา — ค่าประมาณจากวิธีเดาอย่างมีหลัก (heuristic) ว่าเป้าหมายน่าจะยังอยู่ไกลออกไปอีกเท่าไร บนแผนที่ถนน ระยะเส้นตรงแบบ "นกบินตรง" ไปยังจุดหมายคือตัวเดาที่เหมาะเอง คำนวณง่าย และไม่มีทางประเมินระยะขับรถที่เหลือจริงเกินความจริง เพราะไม่มีถนนเส้นไหนสั้นกว่าเส้นตรงระหว่างจุดสองจุดเดียวกัน
คุณสมบัติข้อสุดท้ายนั้น — ไม่ประเมินเกิน — คือความลับทั้งหมด และสมควรอธิบายด้วยคำธรรมดา เพราะมันคือหนึ่งในทฤษฎีบทเล็กๆ ที่งามที่สุดในเรื่องราวทั้งหมดของหนังสือเล่มนี้ heuristic ที่มีคุณสมบัตินี้เรียกว่า ไม่ประเมินเกิน (admissible): มันผิดได้ แต่ไม่เคยผิดไปทางมองโลกในแง่ดีเกินความจริง มันประเมินระยะที่เหลือต่ำกว่าจริงได้ แต่ไม่มีวันอ้างว่าเส้นทางหนึ่งสั้นกว่าที่มันเป็นจริง ให้ admissible heuristic กับ A\* ต่อให้หยาบแค่ไหน มันก็ยังรับประกันทางคณิตศาสตร์ว่าจะหาเส้นทางที่สั้นที่สุด*จริงๆ* พบ เหมือนที่อัลกอริทึมของ Dijkstra ทำ แต่โดยทั่วไปแตะพื้นที่เพียงเสี้ยวเดียวของที่อัลกอริทึมของ Dijkstra ต้องแตะ heuristic ไม่จำเป็นต้องถูก มันแค่ต้องไม่โกหกไปทางความหวังลมๆ แล้งๆ การมองโลกในแง่ดีที่ถูกล็อกไว้ไม่ให้เลยความจริง จึงกลายเป็นของฟรี ค้นหาได้เร็วขึ้น และไม่มีวันถูกหลอกไปสู่คำตอบที่ผิด บทความต้นฉบับปี 1968 ของ Hart, Nilsson และ Raphael ชื่อ "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs" หาวารสารที่ยอมตีพิมพ์แทบไม่ได้ ในที่สุด Raphael ที่อึดอัดกับเรื่องนี้ก็มีส่วนก่อตั้งวารสาร AI ฉบับใหม่ขึ้นมา ส่วนหนึ่งก็เพื่อให้บทความมีที่ลง (IEEE Transactions on Systems Science and Cybernetics 4, no. 2 (1968); doi 10.1109/TSSC.1968.300136) ทุกวันนี้ A\* ทำงานอยู่ในรูปแบบใดรูปแบบหนึ่ง ทั้งในการหาเส้นทางของวิดีโอเกม การจัดเส้นทางโลจิสติกส์ และในลูกหลานของ Shakey ที่ยังแล่นอยู่บนพื้นผิวดาวอังคาร
เครื่องจักรที่พิสูจน์ทฤษฎีบท
ขณะที่หนูของ Shannon เรียนรู้เขาวงกตและ Dijkstra จับเวลากาแฟของเขา อีกกลุ่มหนึ่งที่ RAND Corporation กำลังสอนเครื่องจักรให้ทำคณิตศาสตร์ ในปี 1955 เรื่องนี้ฟังดูใกล้นิยายวิทยาศาสตร์มากกว่าวิศวกรรม
Allen Newell, Herbert Simon และโปรแกรมเมอร์ Cliff Shaw ตั้งใจสร้างโปรแกรมที่พิสูจน์ทฤษฎีบทในตรรกศาสตร์รูปนัยได้ เป้าหมายเจาะจงคือทฤษฎีบทจาก Principia Mathematica งานสามเล่มของ Alfred North Whitehead กับ Bertrand Russell ที่พยายามอนุมานคณิตศาสตร์ทั้งหมดจากสัจพจน์ทางตรรกะชุดเล็กๆ โปรแกรมของพวกเขาชื่อ Logic Theorist มันแทนข้อความทางตรรกะแต่ละข้อด้วยโครงสร้างข้อมูลรูปต้นไม้ แล้วค้นหาไปตามโซ่ของการแทนค่า การตัดออก และกฎการอนุมาน เพื่อล่าลำดับก้าวที่ถูกกติกาซึ่งเชื่อมสัจพจน์เข้ากับทฤษฎีบทที่ต้องพิสูจน์ นี่คือไอเดียพื้นที่ปัญหา (problem space) อันเดียวกับที่บทที่ 00 สืบย้อนไปถึงงานทฤษฎีในภายหลังของ Newell กับ Simon พื้นที่ของการอนุมานที่เป็นไปได้ระเบิดออกแบบเชิงการจัดหมู่ทุกครั้งที่เพิ่มก้าวเข้าไปหนึ่งก้าว Newell กับ Simon จึงต้องตัดกิ่งที่เห็นชัดว่าไม่มีอนาคตทิ้ง และหยิบยืมคำมาเรียกกฎสามัญสำนึกที่ใช้ทำเรื่องนั้น: heuristic Newell เคยเจอคำนี้ใน How to Solve It ของ George Pólya คู่มือที่บทที่ 03 ครอบคลุมไว้เต็มๆ (Wikipedia, "Logic Theorist")
Logic Theorist สร้างเสร็จในปี 1956 และพิสูจน์ทฤษฎีบทได้ 38 ข้อจาก 52 ข้อแรกในบทที่ 2 ของ Principia Mathematica ในกรณีหนึ่งมันพบบทพิสูจน์ที่สง่างามกว่าบทพิสูจน์ที่ Whitehead กับ Russell ตรากตรำทำด้วยมือ หมายเลขของทฤษฎีบทข้อนี้ไม่ตรงกันสองแหล่ง เรื่องเล่าที่แพร่หลายอ้างหมายเลข 2.85 แต่หมายเหตุที่มีเอกสารรองรับในบทความของ Wikipedia ชี้ว่าในฉบับ Cambridge ปี 1910 และ 1963 ของ Principia ทฤษฎีบทข้อเดียวกันนี้มีหมายเลข 2.53 เล่มนี้กางความคลาดเคลื่อนนี้ออกให้เห็น เพราะเล่มนี้ขอให้ผู้อ่านไม่ไว้ใจเกร็ดเล่าที่ถูกขัดให้เรียบระหว่างการเล่าต่อ สิ่งที่มีหลักฐานรองรับดีคือปฏิกิริยาของ Russell: Simon เอาบทพิสูจน์ที่สั้นกว่าของเครื่องให้เขาดู และมีรายงานว่า Russell ตอบรับด้วยความยินดี ทั้งสองคนพยายามตีพิมพ์บทพิสูจน์ใหม่นี้ใน The Journal of Symbolic Logic วารสารปฏิเสธ เหตุผลคือบทพิสูจน์ใหม่ของทฤษฎีบทพื้นฐานไม่ใช่ผลงานที่น่าสนใจ ผู้ประเมินดูจะมองข้าม หรือไม่ก็ไม่รู้สึกอะไร กับข้อเท็จจริงที่ว่าหนึ่งใน "ผู้เขียน" ที่ให้เครดิตไว้คือโปรแกรมคอมพิวเตอร์ (Wikipedia, "Logic Theorist")
ระหว่างปี 1957 ถึง 1959 Newell, Simon และ Shaw ต่อยอด Logic Theorist ด้วยทายาทที่ทะเยอทะยานกว่า: General Problem Solver หรือ GPS มันไม่ได้ตั้งใจแค่พิสูจน์ทฤษฎีบทตรรกะ แต่จัดการปัญหาใดก็ตามที่เขียนออกมาเป็นชุดของสถานะ (state) กับตัวดำเนินการ (operator) ที่ถูกกติกาได้ — รูปนัยของพื้นที่ปัญหาแบบทั่วไปที่หนังสือเล่มนี้พิงอยู่ตลอด เทคนิคหลักของ GPS คือการวิเคราะห์วิธี-เป้าหมาย (means–ends analysis) พูดออกมาง่าย และทนทานเกินคาด: เทียบสถานะปัจจุบันกับสถานะเป้าหมาย ระบุความต่างที่ใหญ่ที่สุดข้อเดียว แล้วเลือก operator ที่มีอยู่ตัวที่รู้ว่าลดความต่างชนิดนั้นพอดี แก้ช่องว่างที่ใหญ่ที่สุดก่อน แล้วทำซ้ำกับช่องว่างที่เหลือ มันคือเครื่องยนต์อเนกประสงค์ขนาดจิ๋วสำหรับบีบพื้นที่มหาศาลให้แคบลงทีละก้าวอย่างตั้งใจ แทนที่จะเดินเตร็ดเตร่ในนั้นแบบสุ่ม (Wikipedia, "General Problem Solver"; Wikipedia, "Means–ends analysis") ในที่สุด GPS ก็ชนกำแพงเดียวกับที่วิธีทั่วไปทุกวิธีชน บทหลังจากนี้ โดยเฉพาะบทที่ 06 จะอธิบายว่าทำไมความเป็นทั่วไปกับประสิทธิภาพถึงดึงกันคนละทาง แต่เทคนิคที่มันแนะนำไว้ยังอยู่ แทบไม่เปลี่ยนรูป ในระบบวางแผนอัตโนมัติสมัยใหม่
ห้าเดิมพันว่าด้วยรูปร่างของพื้นที่
กลยุทธ์การค้นหาทุกแบบ ใต้รายละเอียดของมัน คือการเดิมพันว่าพื้นที่ที่มันกำลังค้นหาเป็นพื้นที่ชนิดไหน ถอยออกมาจากอัลกอริทึมตัวใดตัวหนึ่งในบทนี้แล้วตรรกะร่วมข้อนี้จะปรากฏ เรียกชื่อเดิมพันเหล่านี้ให้ชัด แล้วถุงลูกเล่นคละกันจะกลายเป็นชุดเครื่องมือจริง ชุดที่ยกขึ้นเทียบกับปัญหาใหม่แล้วถามได้ว่าเดิมพันไหนเข้ากัน
อัลกอริทึมแบบโลภ (greedy) เดิมพันว่าเลือกสิ่งที่ดีที่สุดเฉพาะถิ่นในทุกก้าว ไม่ย้อนกลับมาทบทวนเลย แล้วผลรวมจะดีในระดับทั้งหมด เดิมพันนี้อันตราย — สร้างปัญหาที่มันล้มเหลวโดยสิ้นเชิงได้ง่ายๆ — แต่เมื่อโครงสร้างของปัญหารับประกันว่าเดิมพันได้ผล (คุณสมบัติที่นักคณิตศาสตร์เรียกว่าเงื่อนไขมาทรอยด์หรือเงื่อนไขแลกเปลี่ยนในกรณีที่สะอาดที่สุด) กลยุทธ์ greedy ไม่มีอะไรสู้ได้ในแง่ความเรียบง่ายและความเร็ว มองแบบนี้ อัลกอริทึมของ Dijkstra คืออัลกอริทึม greedy ที่บังเอิญพิสูจน์ได้ว่าปลอดภัย: ปิดตายโหนดที่ยังไม่ได้ไปซึ่งถูกที่สุดตอนนี้เสมอ และไม่หันกลับไปมองอีก
แบ่งแล้วพิชิต (divide and conquer) เดิมพันว่าปัญหายากข้อหนึ่งแยกออกเป็นสำเนาของตัวมันเองที่เล็กลงและมีโครงสร้างเหมือนกันได้ แก้แยกกัน แล้วเย็บกลับเข้าด้วยกัน มันคือกลยุทธ์เบื้องหลังอัลกอริทึมเรียงลำดับและคูณเลขที่เร็ว เดิมพันของมันคือ การแยกส่วนได้: แก้ชิ้นส่วนแล้วรู้จริงหรือว่าจะแก้ทั้งก้อนอย่างไร
dynamic programming ที่บทที่ 04 แนะนำผ่านหลักความเหมาะที่สุดของ Bellman เดิมพันว่าปัญหาย่อยของปัญหาหนึ่ง ซ้อนทับกัน — คำถามเล็กข้อเดิมจะวนกลับมาหลายครั้งภายในการค้นหาที่ใหญ่กว่า — และเก็บคำตอบแต่ละข้อไว้ตั้งแต่ครั้งแรกที่คำนวณจะประหยัดแรงที่ต้องทำซ้ำในภายหลัง ชิ้นส่วนของแบ่งแล้วพิชิตเป็นอิสระต่อกัน ชิ้นส่วนของ dynamic programming แบ่งงานกันใช้ เทคนิคนี้มีอยู่เพื่อเลี่ยงการทำงานร่วมนั้นซ้ำพอดี เหมือนที่หนูของ Shannon ไม่เคยกลับไปสำรวจช่องทางที่มันทำแผนที่ไว้แล้ว
backtracking เดิมพันว่าพื้นที่หนึ่งค้นหาแบบ DFS ได้ ตราบใดที่การค้นหารู้ตัวเร็วว่าเจอทางตัน แล้วถอยกลับก่อนผลาญแรงลงไปในนั้นอีก มันคือเวอร์ชันมีวินัยของสิ่งที่ Theseus ทำด้วยการลอง ชน และแก้
แตกกิ่งแล้วตีกรอบ (branch and bound) เดิมพันว่าเราคำนวณ ขอบเขต ราคาถูกได้ว่าคำตอบใดก็ตามที่แตกกิ่งออกจากตัวเลือกบางส่วนอันหนึ่งจะดีได้มากที่สุดแค่ไหน ทันทีที่ขอบเขตพิสูจน์ว่ากิ่งนั้นชนะคำตอบที่ถืออยู่ในมือแล้วไม่ได้ ก็ตัดกิ่งทั้งกิ่งของต้นไม้การค้นหาทิ้งโดยไม่ต้องเข้าไปดูเลย Ailsa Land กับ Alison Doig ทำให้มันเป็นรูปนัยในปี 1960 สำหรับปัญหาที่ต้องการคำตอบเป็นจำนวนเต็มแทนที่จะเป็นเศษส่วน (Wikipedia, "Branch and bound") มันคือ admissible heuristic ของ A\* ที่ถูกทำให้ทั่วไปขึ้น จากการหาเส้นทางบนแผนที่ ไปสู่การหาจุดเหมาะที่สุดในพื้นที่เชิงการจัดหมู่ที่หลากหลายกว่ามาก
ห้าเดิมพัน คือห้าการเดาที่ต่างกันเกี่ยวกับรูปร่างที่ซ่อนอยู่ของพื้นที่ปัญหา ไม่มีอันไหนเป็นวิธีค้นหาที่ถูก "อันนั้น"; แต่ละอันถูก เมื่อเดิมพันของมันเกี่ยวกับพื้นที่บังเอิญเป็นจริง อ่านปัญหาใหม่ได้ดีพอจะรู้ว่าเดิมพันไหนใช้ได้ — นั่นคือทักษะเกือบทั้งหมดที่หนังสือเล่มนี้พยายามเรียกชื่อ
อัลกอริทึมคือ heuristic ที่หาบทพิสูจน์มาได้
"อัลกอริทึม" กับ "heuristic" ไม่ใช่ขั้วตรงข้าม มองย้อนจากโลกที่มีตัววางแผนเส้นทางและเครื่องยนต์หมากรุก มีสิ่งล่อใจให้ถือว่าอย่างหนึ่งเข้มงวดและรับประกันได้ อีกอย่างเป็นการเดาหยาบๆ ที่อาจพลาด ประวัติศาสตร์ในบทนี้เถียงให้ภาพอีกแบบ อัลกอริทึมของ Dijkstra เริ่มจาก insight แบบไม่เป็นทางการว่าควรไปเมืองไหนต่อ; สิ่งที่ทำให้มันเป็นอัลกอริทึมแทนที่จะเป็นลางสังหรณ์ คือ Dijkstra พิสูจน์ได้ว่า insight นั้นใช้ได้เสมอ ค่าประมาณแบบ heuristic ของ A\* เป็นการเดาอย่างเปิดเผยตั้งแต่ชื่อ แต่พอจับคู่กับคุณสมบัติที่พิสูจน์ได้ข้อเดียวคือ admissibility การเดานั้นก็กลายเป็นส่วนหนึ่งของอัลกอริทึมที่รับประกันคำตอบเหมาะที่สุดอย่างหักล้างไม่ได้ กฎสามัญสำนึกของ Newell กับ Simon ที่ใช้ตัดกิ่งในการค้นหาบทพิสูจน์ทฤษฎีบท เป็น heuristic ในความหมายเก่าที่หลวมกว่า: มีประโยชน์ ยังไม่พิสูจน์ และบางทีก็ผิด สาขานี้เติบโตตลอดทั้งบทด้วยการค่อยๆ แปลงลางสังหรณ์ให้เป็นการรับประกัน ไม่ใช่ด้วยการทิ้งสัญชาตญาณ แต่ด้วยการค้นให้เจอว่าสัญชาตญาณข้อไหนกันแน่ที่พิสูจน์ได้ว่าจะไม่มีวันทรยศ
ตรงนี้เองที่ธรรมเนียมเชิงอัลกอริทึมเริ่มแยกออกจากธรรมเนียมวิจัยดำเนินงาน (operational research, OR) ของบทที่ 04 กำหนดการเชิงเส้น (linear programming) และ dynamic programming แก้ปัญหาการหาค่าเหมาะที่สุดเชิงตัวเลขที่นิยามไว้ชัดเจน อัลกอริทึมในบทนี้แก้ปัญหา*การค้นหา*บนพื้นที่ไม่ต่อเนื่องซึ่งมักเป็นเชิงการจัดหมู่ — เขาวงกต กราฟ บทพิสูจน์ทางตรรกะ ตำแหน่งบนกระดาน การค้นพบใจกลางของพวกมันคือ โครงสร้างของพื้นที่เองต่างหาก (ระยะทางในนั้น ปัญหาย่อยที่ซ้อนทับกัน ความแยกส่วนได้ของมัน) ที่กำหนดว่ากลยุทธ์การค้นหาแบบไหนจะพิสูจน์ได้ว่าถูกและเร็ว การค้นพบนั้นปูทางไปสู่การค้นพบถัดไปที่มืดกว่า มันรออยู่ในบทที่ 06: พื้นที่บางแบบไม่มีโครงสร้างชนิดนี้ให้ใช้ประโยชน์เลย และไม่ว่าจะฉลาดแค่ไหนก็ผลิตมันขึ้นมาในที่ที่ไม่มีไม่ได้
ท่าประจำบท
Move 05 — จัดลำดับการค้นหา — ใช้โครงสร้างดันเส้นทางที่ดีขึ้นมาก่อน
- เรียกชื่อให้ได้ว่าเดิมพันข้อไหนในห้าข้อเข้ากับพื้นที่ของคุณ ก่อนจะเริ่มค้นหามัน ปัญหาย่อยที่ซ้อนทับกันเรียกหา dynamic programming; ปัญหาที่แยกส่วนได้เรียกหาแบ่งแล้วพิชิต; ตัวเลือกเฉพาะถิ่นที่พิสูจน์ได้ว่าปลอดภัยเรียกหา greedy; นอกนั้นมักเรียกหา backtracking หรือ branch and bound การเดาเดิมพันผิดคือการผลาญการค้นหาทิ้งตั้งแต่ยังไม่เริ่ม
- เมื่อต้องเดา จงเดาในแง่ดี แต่ห้ามเลยความจริง A\* แสดงให้เห็นว่าค่าประมาณไม่จำเป็นต้องแม่นถึงจะมีประโยชน์ — มันแค่ต้อง admissible ขอบล่างที่ซื่อสัตย์ของแรงที่เหลือ มีค่ามากกว่า "การเดาที่ดีที่สุด" ที่เชื่อถือไม่ได้
- จำไว้ว่าค้นอะไรไปแล้วบ้าง หนูของ Shannon กับสมการเชิงฟังก์ชันของ Bellman มีบทเรียนร่วมกันข้อหนึ่ง: การเดินผ่านพื้นที่รอบแรกแพงได้ ตราบใดที่ไม่มีอะไรบังคับให้จ่ายค่าปัญหาย่อยข้อเดียวกันสองครั้ง
- แยกการรับประกันของจริงออกจาก heuristic ที่ฟังดูมีเหตุผล แล้วพูดออกมาดังๆ ว่ากำลังพึ่งอันไหนอยู่ "กฎสามัญสำนึก" ของ Logic Theorist กับแนวหน้าที่พิสูจน์ว่าเหมาะที่สุดของ Dijkstra ต่างก็เป็นกลยุทธ์การค้นหา — แต่มีแค่อันเดียวที่สัญญาว่ามันผิดไม่ได้
ต่อไป — บทที่ 06 · กำแพง: ไม่ใช่ทุกพื้นที่ที่จะยอมโค้งให้ลำดับการค้นหาอันชาญฉลาด อัลกอริทึมทั้งหมดในบทนี้เจอโครงสร้างให้ใช้ประโยชน์ — บทหน้าจะพบปัญหาที่ไม่มีโครงสร้างให้ใช้ประโยชน์เลย และถามว่านักแก้ปัญหาทำอย่างไรเมื่อพื้นที่เองปฏิเสธที่จะสั้นลง
บทถัดไป · 7 / 1206 · กำแพง