05 · The Algorithmic Path
05 · เส้นทางแบบอัลกอริทึม
THE SHORTEST PATH — A History of the Art and Science of Problem-Solving
เส้นทางที่สั้นที่สุด — ประวัติศาสตร์ของศิลปะและศาสตร์แห่งการแก้ปัญหา
Amsterdam, a café terrace, 1956
อัมสเตอร์ดัม ระเบียงร้านกาแฟ ปี 1956
Edsger Dijkstra was twenty-six, shopping with his fiancée Ria, and tired. He had recently taken a job at the Mathematisch Centrum in Amsterdam demonstrating a new computer called the ARMAC, and he wanted a problem simple enough to explain to a nontechnical audience yet impressive enough to show the machine earning its keep. Sitting down for coffee, without pencil, paper, or access to a library, he set himself the question of the shortest route between two Dutch cities and, in his own later telling, worked out the solution in about twenty minutes (David Gries, "Edsger Dijkstra and the Shortest-Path Algorithm," Cornell CS). The algorithm he sketched that morning — grow a set of cities whose shortest distance from the start is already known for certain, and at each step add whichever unvisited city is now closest — is still, seven decades later, the default answer whenever a computer needs to find the cheapest way from here to there. He did not publish it until three years afterward, as a spare three-page note that solved two unrelated graph problems in the space most papers need for an abstract (Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik 1 (1959)).
อัลกอริทึมที่ยังเป็นคำตอบตั้งต้นของคอมพิวเตอร์ทุกเครื่องเมื่อต้องหาทางที่ถูกที่สุดจากที่นี่ไปที่นั่น ถูกคิดขึ้นในร้านกาแฟ ในเวลาราวยี่สิบนาที 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))
There is a pleasing, almost too-neat symmetry in the fact that a book called The Shortest Path arrives, in its fifth chapter, at an algorithm literally named for finding shortest paths, invented over coffee in less time than it takes to read this paragraph twice. But the neatness is real, not manufactured, and it marks the hinge this chapter turns on. Chapter 04 showed a generation of scientists discovering that real-world problems — convoys, diets, factories — could be captured as mathematical objects and solved by general-purpose procedures. This chapter is about what happened next: those procedures themselves became objects of study. People began asking not just "does a method exist?" but "how good a method can exist, and how would we know?" Search — the raw, brute business of trying paths through a space of possibilities — became a subject with its own theory, its own proofs, and eventually its own machines.
หนังสือชื่อ เส้นทางที่สั้นที่สุด เดินมาถึงบทที่ห้าแล้วเจออัลกอริทึมที่ตั้งชื่อตามการหาเส้นทางสั้นที่สุดตรงๆ คิดขึ้นระหว่างจิบกาแฟ ในเวลาน้อยกว่าที่ใช้อ่านย่อหน้านี้สองรอบ ความสมมาตรนี้น่าพอใจ เกือบจะเรียบร้อยเกินไป แต่มันเป็นของจริง ไม่ได้จัดฉาก และมันคือบานพับที่บทนี้หมุนอยู่บน บทที่ 04 แสดงให้เห็นนักวิทยาศาสตร์รุ่นหนึ่งค้นพบว่าปัญหาในโลกจริง — กองเรือคุ้มกัน สูตรอาหาร โรงงาน — จับใส่กรอบเป็นวัตถุทางคณิตศาสตร์แล้วแก้ด้วยขั้นตอนวิธีอเนกประสงค์ได้ บทนี้ว่าด้วยสิ่งที่เกิดขึ้นต่อจากนั้น: ขั้นตอนวิธีเหล่านั้นเองกลายเป็นวัตถุที่ถูกศึกษา คำถามเปลี่ยนจาก "มีวิธีอยู่ไหม" เป็น "วิธีที่ ดีแค่ไหน จึงจะมีอยู่ได้ และเราจะรู้ได้อย่างไร" การค้นหา (search) — งานดิบที่ใช้กำลังล้วนลองเดินเส้นทางต่างๆ ผ่านพื้นที่ของความเป็นไปได้ — กลายเป็นวิชาที่มีทฤษฎีของตัวเอง มีบทพิสูจน์ของตัวเอง และในที่สุดก็มีเครื่องจักรของตัวเอง
The Man Whose Name Became a Word
ชายผู้มีชื่อกลายเป็นคำศัพท์
The word for what Dijkstra did that morning — devise a step-by-step procedure guaranteed to reach a correct answer — is algorithm, and the word has its own long detour before it lands in a computer science course.
สิ่งที่ Dijkstra ทำเช้าวันนั้น — คิดขั้นตอนทีละก้าวที่รับประกันว่าจะไปถึงคำตอบที่ถูกต้อง — มีชื่อเรียกว่า อัลกอริทึม คำนี้เดินทางอ้อมมายาวก่อนจะลงเอยในห้องเรียนวิทยาการคอมพิวเตอร์
It comes from the Latinized name of a ninth-century scholar working in the House of Wisdom in Baghdad: Muhammad ibn Musa al-Khwarizmi. His treatise on Hindu-Arabic numerals, translated into Latin as Algoritmi de numero Indorum, gave medieval Europe both a new way to calculate — the positional decimal system, replacing Roman numerals — and, eventually, a new word: algorismus, referring at first specifically to arithmetic done this new way. Only much later, in the twentieth century, did "algorithm" widen into its modern sense: any finite, unambiguous, mechanically executable procedure for solving a class of problems (findanexpert.unimelb.edu.au, "Why are algorithms called algorithms?"; NPR, "How 'algorithm' got its name from a 9th-century Persian mathematician"). Al-Khwarizmi's other great book gave mathematics the word algebra, from al-jabr, "completion" or "restoration" — a term for the operation of moving a quantity from one side of an equation to the other. The scribes of chapter 01 wrote down individual solved problems as teaching examples; al-Khwarizmi wrote down the procedure itself, stripped of any particular numbers, so that it could be applied to numbers no one had thought of yet. That abstraction — the method as an object in its own right, portable across every instance of a problem — is the direct ancestor of everything in this chapter.
คำนี้มาจากชื่อในรูปละตินของนักปราชญ์ศตวรรษที่เก้าผู้ทำงานอยู่ในบ้านแห่งปัญญา (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) ของปัญหา — นามธรรมข้อนี้คือบรรพบุรุษสายตรงของทุกอย่างในบทนี้
The Primitive Moves: Sweeping Outward, Plunging Deep
ท่าพื้นฐาน: กวาดออกไปรอบตัว กับดำดิ่งลงลึก
Before Dijkstra's algorithm, and underneath it, sit two even more basic strategies for exploring a space of possibilities, and it is worth naming them plainly because everything more sophisticated in this chapter is built from them.
ใต้อัลกอริทึมของ Dijkstra มีกลยุทธ์พื้นฐานกว่าอีกสองอย่างสำหรับสำรวจพื้นที่ของความเป็นไปได้ ทั้งสองมาก่อนมัน ควรเรียกชื่อให้ชัด เพราะทุกอย่างที่ซับซ้อนกว่านั้นในบทนี้สร้างขึ้นจากสองอย่างนี้
Imagine a maze, or a family tree, or a web of friendships, represented the way chapter 02 taught Euler to represent Königsberg: as a graph of nodes and connecting edges. Breadth-first search starts at one node and explores outward in expanding rings — first everything one step away, then everything two steps away, and so on — guaranteeing that the first time it reaches any given node, it has found the shortest possible route to it, measured in number of steps. It was reinvented for exactly this purpose in 1959 by Edward F. Moore, who wanted a mechanical way to find the shortest way out of a maze, though a similar idea had been buried, unpublished, in Konrad Zuse's rejected 1945 doctoral thesis (Wikipedia, "Breadth-first search"). Depth-first search, by contrast, commits to a single path and follows it as far as it can go before backing up — plunging down one corridor of the maze to its very end before trying another. It has no built-in guarantee of finding the shortest route, but it uses far less memory to run and, in the hands of Robert Tarjan and John Hopcroft in the early 1970s, turned out to unlock efficient solutions to a surprising range of graph problems, from testing whether a map can be drawn without crossing lines to finding a network's structural weak points (Wikipedia, "Depth-first search").
เริ่มจากเขาวงกต หรือแผนผังตระกูล หรือใยความสัมพันธ์ของเพื่อนฝูง แทนด้วยวิธีเดียวกับที่บทที่ 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")
Neither strategy knows anything about the problem it is solving beyond the bare shape of the graph. That ignorance is their strength — they work on any graph whatsoever — and their weakness: they waste enormous effort exploring directions that, to anyone who actually understood the problem, would look obviously hopeless. Dijkstra's algorithm is breadth-first search's more disciplined cousin, expanding outward not ring by ring but always toward whichever unvisited node is currently cheapest to reach — which is why it finds not just a short path but provably the shortest one, for any graph where distances are never negative.
ทั้งสองกลยุทธ์ไม่รู้อะไรเลยเกี่ยวกับปัญหาที่กำลังแก้ นอกจากรูปร่างเปล่าๆ ของกราฟ ความไม่รู้นั้นคือจุดแข็ง — ใช้ได้กับกราฟทุกชนิด — และคือจุดอ่อน: มันผลาญแรงไปกับทิศทางที่ใครก็ตามที่เข้าใจปัญหาจริงๆ จะเห็นทันทีว่าไร้ความหวัง อัลกอริทึมของ Dijkstra คือญาติที่มีวินัยกว่าของ BFS มันไม่ขยายทีละวง แต่มุ่งไปยังโหนดที่ยังไม่ได้ไปซึ่งตอนนี้ไปถึงได้ถูกที่สุดเสมอ นั่นคือเหตุผลที่มันไม่ได้แค่หาเส้นทางสั้น*เส้นหนึ่ง* แต่พิสูจน์ได้ว่าเป็นเส้น*ที่สั้นที่สุด* สำหรับกราฟใดก็ตามที่ระยะทางไม่เคยติดลบ
A Mouse Named Theseus
หนูตัวหนึ่งชื่อ Theseus
Six years before Dijkstra's coffee, at Bell Labs in 1950, Claude Shannon — already famous for founding information theory — built a smaller, stranger monument to the same idea: a maze-solving mechanical mouse he named Theseus, after the hero who navigated the Minotaur's labyrinth by unspooling a thread behind him.
หกปีก่อนกาแฟถ้วยนั้นของ Dijkstra ที่ Bell Labs ในปี 1950 Claude Shannon สร้างอนุสาวรีย์ของไอเดียเดียวกันที่เล็กกว่าและแปลกกว่า เขามีชื่อเสียงอยู่แล้วจากการก่อตั้งทฤษฎีสารสนเทศ สิ่งที่เขาสร้างคือหนูกลไกแก้เขาวงกต เขาตั้งชื่อมันว่า Theseus ตามวีรบุรุษผู้หาทางในเขาวงกตของมิโนทอร์ด้วยการคลี่เส้นด้ายทิ้งไว้ข้างหลัง
Theseus was, mechanically, a magnet wrapped in a metal shell, dragged along underneath a re-configurable five-by-five maze by an electromagnet hidden beneath the floor, itself driven by a bank of telephone relays functioning as memory. Released into an unfamiliar maze, the mouse would blunder forward, bumping walls, backing up, trying again — a physical enactment of depth-first search with backtracking — until it stumbled onto a hidden slice of "cheese" that closed an electrical contact. But every turn it made was recorded in the relay memory as it went. Reset to the start of the same maze, Theseus would now glide directly to the goal without a single wrong turn, having converted its earlier blind search into a stored, reusable solution (cyberneticzoo.com, "1952 – 'Theseus' Maze-Solving Mouse – Claude Shannon"). This is worth pausing on, because it is a genuinely early and genuinely physical demonstration of the idea that would come to define machine intelligence: search followed by memory is learning. The first pass through a space costs the full price of exploring it. Every later pass can spend that stored knowledge instead of paying again — the same insight, in miniature and in copper wire, that would let Bellman's dynamic programming (chapter 04) avoid resolving identical sub-problems, and that lets a chess program in chapter 10 remember a position it has already evaluated.
ในเชิงกลไก Theseus คือแม่เหล็กหุ้มเปลือกโลหะ มันถูกลากไปใต้เขาวงกตขนาดห้าคูณห้าที่ปรับผังใหม่ได้ ด้วยแม่เหล็กไฟฟ้าที่ซ่อนอยู่ใต้พื้น แม่เหล็กไฟฟ้านั้นถูกขับด้วยแผงรีเลย์โทรศัพท์ที่ทำหน้าที่เป็นหน่วยความจำ ปล่อยเข้าเขาวงกตที่ไม่คุ้นเคย หนูจะเดินซุ่มซ่ามไปข้างหน้า ชนกำแพง ถอยหลัง ลองใหม่ — DFS พร้อมการย้อนรอย (backtracking) ในรูปธรรม — จนสะดุดเข้ากับ "ชีส" ชิ้นที่ซ่อนอยู่ ซึ่งทำให้หน้าสัมผัสไฟฟ้าปิดวงจร ทุกการเลี้ยวระหว่างทางถูกบันทึกไว้ในหน่วยความจำรีเลย์ ตั้งกลับไปที่จุดเริ่มต้นของเขาวงกต*อันเดิม* Theseus จะแล่นตรงไปยังเป้าหมายโดยไม่เลี้ยวผิดแม้แต่ครั้งเดียว การค้นหาแบบตาบอดรอบก่อนกลายเป็นคำตอบที่เก็บไว้และใช้ซ้ำได้ (cyberneticzoo.com, "1952 – 'Theseus' Maze-Solving Mouse – Claude Shannon") ตรงนี้ควรหยุดดู เพราะมันคือการสาธิตที่เก่าจริงและเป็นรูปธรรมจริงของไอเดียที่ต่อมาจะนิยามปัญญาของเครื่องจักร: การค้นหาที่ตามด้วยความจำ คือการเรียนรู้ รอบแรกจ่ายราคาเต็มของการสำรวจพื้นที่ ทุกรอบหลังจากนั้นใช้ความรู้ที่เก็บไว้แทนการจ่ายซ้ำ นี่คือการหยั่งเห็น (insight) เดียวกัน ในขนาดจิ๋วและในสายทองแดง ที่ทำให้กำหนดการพลวัต (dynamic programming) ของ Bellman (บทที่ 04) ไม่ต้องแก้ปัญหาย่อยที่เหมือนกันซ้ำ และที่ทำให้โปรแกรมหมากรุกในบทที่ 10 จำตำแหน่งที่มันประเมินไปแล้วได้
Optimism That Never Lies
การมองโลกในแง่ดีที่ไม่เคยโกหก
Dijkstra's algorithm is exhaustive within its expanding frontier — it never skips a node that might turn out to matter — and that thoroughness is also its limit. On a graph with millions of nodes, exploring "everything closer than the current best" before considering anything farther away wastes effort in every direction that has nothing to do with where you are actually trying to go.
ความครบถ้วนของอัลกอริทึมของ Dijkstra คือขีดจำกัดของมันด้วย มันไล่ครบทุกโหนดภายในแนวหน้าที่กำลังขยาย ไม่เคยข้ามโหนดที่อาจกลายเป็นเรื่องสำคัญ บนกราฟที่มีโหนดเป็นล้าน การสำรวจ "ทุกอย่างที่ใกล้กว่าค่าดีที่สุดตอนนี้" ก่อนจะพิจารณาอะไรที่ไกลกว่านั้น ผลาญแรงไปในทุกทิศที่ไม่เกี่ยวกับที่ที่ตั้งใจจะไปจริงๆ
The fix arrived in 1968 from a robotics project at the Stanford Research Institute, where researchers Peter Hart, Nils Nilsson, and Bertram Raphael were trying to give a mobile robot named Shakey — one of the first machines able to reason about its own actions in a real room — a way to plan efficient routes around obstacles without exploring the entire building's floor plan every time (Engineering and Technology History Wiki, "Milestones: SHAKEY: The World's First Mobile Intelligent Robot, 1972"). Their algorithm, which came to be called A* (pronounced "A-star"), adds one ingredient to Dijkstra's method: at each step, instead of ranking unexplored nodes purely by the distance already traveled to reach them, A* ranks them by that distance plus a guess — a heuristic estimate of how much farther the goal must still be. On a road map, the straight-line, "as the crow flies" distance to the destination is a natural guess: it is easy to compute and it can never overestimate the true remaining driving distance, since no road is ever shorter than a straight line between the same two points.
ทางแก้มาถึงในปี 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) ว่าเป้าหมายน่าจะยังอยู่ไกลออกไปอีกเท่าไร บนแผนที่ถนน ระยะเส้นตรงแบบ "นกบินตรง" ไปยังจุดหมายคือตัวเดาที่เหมาะเอง คำนวณง่าย และไม่มีทางประเมินระยะขับรถที่เหลือจริงเกินความจริง เพราะไม่มีถนนเส้นไหนสั้นกว่าเส้นตรงระหว่างจุดสองจุดเดียวกัน
That last property — never overestimating — is the entire secret, and it is worth explaining in plain terms because it is one of the most beautiful small theorems in this book's whole story. A heuristic with this property is called admissible: it may be wrong, but it is never wrong in the optimistic direction beyond the truth — it can underestimate the remaining distance, but it can never claim a path is shorter than it actually is. Give A* an admissible heuristic, however crude, and it is mathematically guaranteed to still find the truly shortest path, exactly as Dijkstra's algorithm would, while typically exploring only a sliver of the space Dijkstra's algorithm would have to touch. The heuristic doesn't need to be right. It only needs to never lie in the direction of false hope. Optimism, bounded so it can never overshoot the truth, turns out to be free — you get to search faster and you are never fooled into a wrong answer. Hart, Nilsson, and Raphael's original 1968 paper, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs," struggled to find a journal willing to publish it, and Raphael, frustrated, eventually helped found a new AI journal partly so the paper would have somewhere to appear (IEEE Transactions on Systems Science and Cybernetics 4, no. 2 (1968); doi 10.1109/TSSC.1968.300136). A* now runs, in one variant or another, inside video game pathfinding, logistics routing, and the descendants of Shakey still driving across the surface of Mars.
คุณสมบัติข้อสุดท้ายนั้น — ไม่ประเมินเกิน — คือความลับทั้งหมด และสมควรอธิบายด้วยคำธรรมดา เพราะมันคือหนึ่งในทฤษฎีบทเล็กๆ ที่งามที่สุดในเรื่องราวทั้งหมดของหนังสือเล่มนี้ 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 ที่ยังแล่นอยู่บนพื้นผิวดาวอังคาร
Machines That Prove Theorems
เครื่องจักรที่พิสูจน์ทฤษฎีบท
While Shannon's mouse learned mazes and Dijkstra timed his coffee, a separate group at the RAND Corporation was attempting something that, in 1955, sounded closer to science fiction than engineering: teaching a machine to do mathematics.
ขณะที่หนูของ Shannon เรียนรู้เขาวงกตและ Dijkstra จับเวลากาแฟของเขา อีกกลุ่มหนึ่งที่ RAND Corporation กำลังสอนเครื่องจักรให้ทำคณิตศาสตร์ ในปี 1955 เรื่องนี้ฟังดูใกล้นิยายวิทยาศาสตร์มากกว่าวิศวกรรม
Allen Newell, Herbert Simon, and the programmer Cliff Shaw set out to build a program that could prove theorems in formal logic — specifically, theorems from Principia Mathematica, the monumental three-volume attempt by Alfred North Whitehead and Bertrand Russell to derive all of mathematics from a small set of logical axioms. Their program, the Logic Theorist, represented each logical statement as a tree-shaped data structure and searched through chains of substitution, detachment, and inference rules — the same problem-space idea chapter 00 traces to Newell and Simon's later theoretical work — hunting for a sequence of legal steps connecting the axioms to the theorem to be proved. Because the space of possible deductions explodes combinatorially with every added step, Newell and Simon needed a way to prune obviously unpromising branches, and borrowed a word for the rules of thumb they used to do it: heuristics, a term Newell had encountered in George Pólya's How to Solve It, the handbook chapter 03 covers in full (Wikipedia, "Logic Theorist").
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")
Completed in 1956, the Logic Theorist went on to prove 38 of the first 52 theorems in Chapter 2 of Principia Mathematica — and, in one case, found a proof more elegant than the one Whitehead and Russell had labored over by hand. The theorem is commonly cited by the number 2.85, although a documented note on Wikipedia's account points out that in the original 1910 and 1963 Cambridge editions of Principia the same theorem is actually numbered 2.53 — a small numbering discrepancy in the popular retelling worth flagging exactly because this book asks its readers to distrust anecdotes that have been smoothed in the retelling. What is well attested is Russell's reaction: Simon showed him the machine's shorter proof, and Russell reportedly responded with delight. The two men then tried to publish the new proof in The Journal of Symbolic Logic, only to have it rejected on the grounds that a new proof of an elementary theorem was not a notable result — the reviewers apparently missing, or unmoved by, the fact that one of the "authors" credited was a computer program (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")
Newell, Simon, and Shaw followed the Logic Theorist with a more ambitious successor between 1957 and 1959: the General Problem Solver, or GPS, intended not merely to prove logic theorems but to tackle any problem expressible as a set of states and legal operators — the general problem-space formalism this book leans on throughout. GPS's central technique, means-ends analysis, is simple to state and turned out to be extraordinarily durable: compare your current state to your goal state, identify the single biggest difference between them, and select whichever available operator is known to reduce differences of exactly that kind. Solve the biggest gap first, then repeat on whatever gap remains. It is, in miniature, a general-purpose engine for narrowing an enormous space one deliberate step at a time, rather than wandering it at random (Wikipedia, "General Problem Solver"; Wikipedia, "Means–ends analysis"). GPS eventually ran into the same wall every general method runs into — later chapters, especially 06, will explain why generality and efficiency pull in opposite directions — but the technique it introduced still shows up, essentially unchanged, inside modern automated planning systems.
ระหว่างปี 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 จะอธิบายว่าทำไมความเป็นทั่วไปกับประสิทธิภาพถึงดึงกันคนละทาง แต่เทคนิคที่มันแนะนำไว้ยังอยู่ แทบไม่เปลี่ยนรูป ในระบบวางแผนอัตโนมัติสมัยใหม่
Five Bets About the Shape of the Space
ห้าเดิมพันว่าด้วยรูปร่างของพื้นที่
Step back from any single algorithm in this chapter and a shared logic becomes visible: every search strategy is, underneath its details, a bet about what kind of space it is searching. Naming the bets explicitly turns them from a grab-bag of tricks into a genuine toolkit, one you can hold up against a new problem and ask which bet fits.
กลยุทธ์การค้นหาทุกแบบ ใต้รายละเอียดของมัน คือการเดิมพันว่าพื้นที่ที่มันกำลังค้นหาเป็นพื้นที่ชนิดไหน ถอยออกมาจากอัลกอริทึมตัวใดตัวหนึ่งในบทนี้แล้วตรรกะร่วมข้อนี้จะปรากฏ เรียกชื่อเดิมพันเหล่านี้ให้ชัด แล้วถุงลูกเล่นคละกันจะกลายเป็นชุดเครื่องมือจริง ชุดที่ยกขึ้นเทียบกับปัญหาใหม่แล้วถามได้ว่าเดิมพันไหนเข้ากัน
Greedy algorithms bet that making the locally best choice at every step, without ever reconsidering it, will add up to a globally good result. This is a dangerous bet — it is easy to construct problems where it fails outright — but when a problem's structure guarantees the bet pays off (a property mathematicians call the matroid or exchange condition in the cleanest cases), greedy strategies are unbeatable for their simplicity and speed. Dijkstra's algorithm is, in this light, a greedy algorithm that happens to be provably safe: always finalize whichever unvisited node is currently cheapest, and never look back.
อัลกอริทึมแบบโลภ (greedy) เดิมพันว่าเลือกสิ่งที่ดีที่สุดเฉพาะถิ่นในทุกก้าว ไม่ย้อนกลับมาทบทวนเลย แล้วผลรวมจะดีในระดับทั้งหมด เดิมพันนี้อันตราย — สร้างปัญหาที่มันล้มเหลวโดยสิ้นเชิงได้ง่ายๆ — แต่เมื่อโครงสร้างของปัญหารับประกันว่าเดิมพันได้ผล (คุณสมบัติที่นักคณิตศาสตร์เรียกว่าเงื่อนไขมาทรอยด์หรือเงื่อนไขแลกเปลี่ยนในกรณีที่สะอาดที่สุด) กลยุทธ์ greedy ไม่มีอะไรสู้ได้ในแง่ความเรียบง่ายและความเร็ว มองแบบนี้ อัลกอริทึมของ Dijkstra คืออัลกอริทึม greedy ที่บังเอิญพิสูจน์ได้ว่าปลอดภัย: ปิดตายโหนดที่ยังไม่ได้ไปซึ่งถูกที่สุดตอนนี้เสมอ และไม่หันกลับไปมองอีก
Divide-and-conquer bets that a hard problem can be split into smaller, structurally identical copies of itself, solved independently, and stitched back together. It is the strategy behind fast sorting and multiplication algorithms, and its bet is about decomposability: does solving the pieces really tell you how to solve the whole?
แบ่งแล้วพิชิต (divide and conquer) เดิมพันว่าปัญหายากข้อหนึ่งแยกออกเป็นสำเนาของตัวมันเองที่เล็กลงและมีโครงสร้างเหมือนกันได้ แก้แยกกัน แล้วเย็บกลับเข้าด้วยกัน มันคือกลยุทธ์เบื้องหลังอัลกอริทึมเรียงลำดับและคูณเลขที่เร็ว เดิมพันของมันคือ การแยกส่วนได้: แก้ชิ้นส่วนแล้วรู้จริงหรือว่าจะแก้ทั้งก้อนอย่างไร
Dynamic programming, which chapter 04 introduced through Bellman's principle of optimality, bets that a problem's sub-problems overlap — that the same smaller question will recur many times inside a larger search — and that storing each answer the first time it is computed will save enormous repeated effort later. Where divide-and-conquer's pieces are independent, dynamic programming's pieces share work, and the technique exists precisely to avoid redoing that shared work, the way Shannon's mouse never re-explored a corridor it had already mapped.
dynamic programming ที่บทที่ 04 แนะนำผ่านหลักความเหมาะที่สุดของ Bellman เดิมพันว่าปัญหาย่อยของปัญหาหนึ่ง ซ้อนทับกัน — คำถามเล็กข้อเดิมจะวนกลับมาหลายครั้งภายในการค้นหาที่ใหญ่กว่า — และเก็บคำตอบแต่ละข้อไว้ตั้งแต่ครั้งแรกที่คำนวณจะประหยัดแรงที่ต้องทำซ้ำในภายหลัง ชิ้นส่วนของแบ่งแล้วพิชิตเป็นอิสระต่อกัน ชิ้นส่วนของ dynamic programming แบ่งงานกันใช้ เทคนิคนี้มีอยู่เพื่อเลี่ยงการทำงานร่วมนั้นซ้ำพอดี เหมือนที่หนูของ Shannon ไม่เคยกลับไปสำรวจช่องทางที่มันทำแผนที่ไว้แล้ว
Backtracking bets that a space can be searched depth-first, provided the search can recognize a dead end early and retreat before wasting further effort down it — the disciplined version of what Theseus did by trial, bump, and correction.
backtracking เดิมพันว่าพื้นที่หนึ่งค้นหาแบบ DFS ได้ ตราบใดที่การค้นหารู้ตัวเร็วว่าเจอทางตัน แล้วถอยกลับก่อนผลาญแรงลงไปในนั้นอีก มันคือเวอร์ชันมีวินัยของสิ่งที่ Theseus ทำด้วยการลอง ชน และแก้
Branch-and-bound, formalized in 1960 by Ailsa Land and Alison Doig for problems requiring whole-number rather than fractional solutions, bets that you can compute a cheap bound on how good any solution branching from a given partial choice could possibly be — and use that bound to prune away entire branches of the search tree without ever visiting them, the instant the bound proves they cannot beat a solution you already have in hand (Wikipedia, "Branch and bound"). It is A*'s admissible heuristic, generalized from finding paths on a map to finding optimal points in a much wider variety of combinatorial spaces.
แตกกิ่งแล้วตีกรอบ (branch and bound) เดิมพันว่าเราคำนวณ ขอบเขต ราคาถูกได้ว่าคำตอบใดก็ตามที่แตกกิ่งออกจากตัวเลือกบางส่วนอันหนึ่งจะดีได้มากที่สุดแค่ไหน ทันทีที่ขอบเขตพิสูจน์ว่ากิ่งนั้นชนะคำตอบที่ถืออยู่ในมือแล้วไม่ได้ ก็ตัดกิ่งทั้งกิ่งของต้นไม้การค้นหาทิ้งโดยไม่ต้องเข้าไปดูเลย Ailsa Land กับ Alison Doig ทำให้มันเป็นรูปนัยในปี 1960 สำหรับปัญหาที่ต้องการคำตอบเป็นจำนวนเต็มแทนที่จะเป็นเศษส่วน (Wikipedia, "Branch and bound") มันคือ admissible heuristic ของ A\* ที่ถูกทำให้ทั่วไปขึ้น จากการหาเส้นทางบนแผนที่ ไปสู่การหาจุดเหมาะที่สุดในพื้นที่เชิงการจัดหมู่ที่หลากหลายกว่ามาก
Five bets, five different guesses about the hidden shape of a problem space. None of them is "the" right way to search; each is the right way when its bet about the space happens to be true. Reading a new problem well enough to know which bet applies is, itself, most of the skill this book is trying to name.
ห้าเดิมพัน คือห้าการเดาที่ต่างกันเกี่ยวกับรูปร่างที่ซ่อนอยู่ของพื้นที่ปัญหา ไม่มีอันไหนเป็นวิธีค้นหาที่ถูก "อันนั้น"; แต่ละอันถูก เมื่อเดิมพันของมันเกี่ยวกับพื้นที่บังเอิญเป็นจริง อ่านปัญหาใหม่ได้ดีพอจะรู้ว่าเดิมพันไหนใช้ได้ — นั่นคือทักษะเกือบทั้งหมดที่หนังสือเล่มนี้พยายามเรียกชื่อ
An Algorithm Is a Heuristic That Earned a Proof
อัลกอริทึมคือ heuristic ที่หาบทพิสูจน์มาได้
There is a temptation, looking backward from a world of route planners and chess engines, to treat "algorithm" and "heuristic" as opposites — one rigorous and guaranteed, the other a rough guess that might fail. The history in this chapter argues for a different picture. Dijkstra's algorithm began as an informal insight about which city to visit next; what made it an algorithm, rather than a hunch, was that Dijkstra could prove the insight always worked. A*'s heuristic estimate is explicitly, by name, a guess — yet paired with the single provable property of admissibility, that guess becomes part of an algorithm with an ironclad optimality guarantee. Newell and Simon's "rules of thumb" for pruning theorem-proving searches were heuristics in the older, looser sense: useful, unproven, sometimes wrong. The field's entire maturation across this chapter is the slow conversion of hunches into guarantees — not by abandoning intuition, but by discovering exactly which intuitions can be proven never to betray you.
"อัลกอริทึม" กับ "heuristic" ไม่ใช่ขั้วตรงข้าม มองย้อนจากโลกที่มีตัววางแผนเส้นทางและเครื่องยนต์หมากรุก มีสิ่งล่อใจให้ถือว่าอย่างหนึ่งเข้มงวดและรับประกันได้ อีกอย่างเป็นการเดาหยาบๆ ที่อาจพลาด ประวัติศาสตร์ในบทนี้เถียงให้ภาพอีกแบบ อัลกอริทึมของ Dijkstra เริ่มจาก insight แบบไม่เป็นทางการว่าควรไปเมืองไหนต่อ; สิ่งที่ทำให้มันเป็นอัลกอริทึมแทนที่จะเป็นลางสังหรณ์ คือ Dijkstra พิสูจน์ได้ว่า insight นั้นใช้ได้เสมอ ค่าประมาณแบบ heuristic ของ A\* เป็นการเดาอย่างเปิดเผยตั้งแต่ชื่อ แต่พอจับคู่กับคุณสมบัติที่พิสูจน์ได้ข้อเดียวคือ admissibility การเดานั้นก็กลายเป็นส่วนหนึ่งของอัลกอริทึมที่รับประกันคำตอบเหมาะที่สุดอย่างหักล้างไม่ได้ กฎสามัญสำนึกของ Newell กับ Simon ที่ใช้ตัดกิ่งในการค้นหาบทพิสูจน์ทฤษฎีบท เป็น heuristic ในความหมายเก่าที่หลวมกว่า: มีประโยชน์ ยังไม่พิสูจน์ และบางทีก็ผิด สาขานี้เติบโตตลอดทั้งบทด้วยการค่อยๆ แปลงลางสังหรณ์ให้เป็นการรับประกัน ไม่ใช่ด้วยการทิ้งสัญชาตญาณ แต่ด้วยการค้นให้เจอว่าสัญชาตญาณข้อไหนกันแน่ที่พิสูจน์ได้ว่าจะไม่มีวันทรยศ
This is also where the algorithmic tradition begins to separate from the operations-research tradition of chapter 04. Linear programming and dynamic programming solve well-defined numerical optimization problems. The algorithms in this chapter solve search problems over discrete, often combinatorial spaces — mazes, graphs, logical proofs, game positions — and their central discovery is that the structure of the space itself (its distances, its overlapping sub-problems, its decomposability) determines which search strategy can be proven correct and fast. That discovery sets up the next and darker discovery, waiting in chapter 06: some spaces have no exploitable structure of this kind at all, and no amount of cleverness can manufacture one where none exists.
ตรงนี้เองที่ธรรมเนียมเชิงอัลกอริทึมเริ่มแยกออกจากธรรมเนียมวิจัยดำเนินงาน (operational research, OR) ของบทที่ 04 กำหนดการเชิงเส้น (linear programming) และ dynamic programming แก้ปัญหาการหาค่าเหมาะที่สุดเชิงตัวเลขที่นิยามไว้ชัดเจน อัลกอริทึมในบทนี้แก้ปัญหา*การค้นหา*บนพื้นที่ไม่ต่อเนื่องซึ่งมักเป็นเชิงการจัดหมู่ — เขาวงกต กราฟ บทพิสูจน์ทางตรรกะ ตำแหน่งบนกระดาน การค้นพบใจกลางของพวกมันคือ โครงสร้างของพื้นที่เองต่างหาก (ระยะทางในนั้น ปัญหาย่อยที่ซ้อนทับกัน ความแยกส่วนได้ของมัน) ที่กำหนดว่ากลยุทธ์การค้นหาแบบไหนจะพิสูจน์ได้ว่าถูกและเร็ว การค้นพบนั้นปูทางไปสู่การค้นพบถัดไปที่มืดกว่า มันรออยู่ในบทที่ 06: พื้นที่บางแบบไม่มีโครงสร้างชนิดนี้ให้ใช้ประโยชน์เลย และไม่ว่าจะฉลาดแค่ไหนก็ผลิตมันขึ้นมาในที่ที่ไม่มีไม่ได้
The Move
ท่าประจำบท
Move 05 — Order the search: exploit structure so good paths come first.
Move 05 — จัดลำดับการค้นหา — ใช้โครงสร้างดันเส้นทางที่ดีขึ้นมาก่อน
- Name which of the five bets fits your space before searching it. Overlapping sub-problems call for dynamic programming; decomposable ones call for divide-and-conquer; a provably safe local choice calls for greedy; anything else usually calls for backtracking or branch-and-bound. Guessing the wrong bet wastes the search before it starts.
- When you must guess, guess optimistically but never past the truth. A* shows that an estimate need not be accurate to be useful — it only needs to be admissible. An honest lower bound on remaining effort is worth more than an unreliable "best guess."
- Remember what you have already searched. Shannon's mouse and Bellman's functional equations share one lesson: the first pass through a space is allowed to be expensive, provided nothing forces you to pay for the same sub-problem twice.
- Distinguish a real guarantee from a plausible heuristic, and say out loud which one you're relying on. The Logic Theorist's "rules of thumb" and Dijkstra's proven-optimal frontier are both search strategies — only one of them promises it cannot be wrong.
- เรียกชื่อให้ได้ว่าเดิมพันข้อไหนในห้าข้อเข้ากับพื้นที่ของคุณ ก่อนจะเริ่มค้นหามัน ปัญหาย่อยที่ซ้อนทับกันเรียกหา dynamic programming; ปัญหาที่แยกส่วนได้เรียกหาแบ่งแล้วพิชิต; ตัวเลือกเฉพาะถิ่นที่พิสูจน์ได้ว่าปลอดภัยเรียกหา greedy; นอกนั้นมักเรียกหา backtracking หรือ branch and bound การเดาเดิมพันผิดคือการผลาญการค้นหาทิ้งตั้งแต่ยังไม่เริ่ม
- เมื่อต้องเดา จงเดาในแง่ดี แต่ห้ามเลยความจริง A\* แสดงให้เห็นว่าค่าประมาณไม่จำเป็นต้องแม่นถึงจะมีประโยชน์ — มันแค่ต้อง admissible ขอบล่างที่ซื่อสัตย์ของแรงที่เหลือ มีค่ามากกว่า "การเดาที่ดีที่สุด" ที่เชื่อถือไม่ได้
- จำไว้ว่าค้นอะไรไปแล้วบ้าง หนูของ Shannon กับสมการเชิงฟังก์ชันของ Bellman มีบทเรียนร่วมกันข้อหนึ่ง: การเดินผ่านพื้นที่รอบแรกแพงได้ ตราบใดที่ไม่มีอะไรบังคับให้จ่ายค่าปัญหาย่อยข้อเดียวกันสองครั้ง
- แยกการรับประกันของจริงออกจาก heuristic ที่ฟังดูมีเหตุผล แล้วพูดออกมาดังๆ ว่ากำลังพึ่งอันไหนอยู่ "กฎสามัญสำนึก" ของ Logic Theorist กับแนวหน้าที่พิสูจน์ว่าเหมาะที่สุดของ Dijkstra ต่างก็เป็นกลยุทธ์การค้นหา — แต่มีแค่อันเดียวที่สัญญาว่ามันผิดไม่ได้
Next — Chapter 06 · The Wall: not every space bends to a clever order of search. This chapter's algorithms all found structure to exploit — the next chapter meets problems with no exploitable structure at all, and asks what a solver does when the space itself refuses to get shorter.
ต่อไป — บทที่ 06 · กำแพง: ไม่ใช่ทุกพื้นที่ที่จะยอมโค้งให้ลำดับการค้นหาอันชาญฉลาด อัลกอริทึมทั้งหมดในบทนี้เจอโครงสร้างให้ใช้ประโยชน์ — บทหน้าจะพบปัญหาที่ไม่มีโครงสร้างให้ใช้ประโยชน์เลย และถามว่านักแก้ปัญหาทำอย่างไรเมื่อพื้นที่เองปฏิเสธที่จะสั้นลง