โครงงานสรุปรวบยอด — สร้างระบบค้นหาเอกสารด้วยกระบวนการตัดสินโค้ด AI

ตลอดหลักสูตรนี้คุณได้เรียนรู้โครงสร้างข้อมูล การวิเคราะห์ความซับซ้อน และวิธีทำงานร่วมกับปัญญาประดิษฐ์ บทนี้จะร้อยทุกอย่างเข้าด้วยกันเป็น กระบวนการเดียวที่ทำซ้ำได้ ผ่านโครงงานจริงหนึ่งชิ้นที่ใช้ทุกโครงสร้างข้อมูลที่เรียนมา — การค้นหา ตารางแฮช การเรียงลำดับ และกราฟ — กระบวนการนี้คุณจะใช้แก้ปัญหาใหม่ ๆ ได้ตลอดอาชีพ ไม่ว่า AI จะเก่งขึ้นแค่ไหนก็ตาม

กระบวนการทำงานหกขั้นตอน

หัวใจของการเป็นนักแก้ปัญหามืออาชีพไม่ใช่การ “เขียนโค้ดเร็ว” แต่คือการ คิดอย่างเป็นระบบก่อนเขียน กระบวนการนี้มีหกขั้นตอน เดินไล่ตามลำดับได้กับทุกปัญหา

1. แตกปัญหา (Decompose) — แยกโจทย์ใหญ่ออกเป็นชิ้นเล็กที่เข้าใจได้ ระบุให้ชัดว่า “อะไรคืออินพุต อะไรคือเอาต์พุต และมีเงื่อนไขอะไรบ้าง” ก่อนคิดถึงวิธีแก้

คำถามหลัก: ปัญหานี้แท้จริงแล้วถามอะไร และต้องแก้ปัญหาย่อยใดบ้าง?

2. เลือกโครงสร้างข้อมูล (Choose structure) — โครงสร้างที่เลือกกำหนดความเร็วของทุกการดำเนินการ ถามว่าต้องค้นหาบ่อยไหม ต้องเรียงลำดับไหม ต้องเข้าถึงด้วยกุญแจหรือด้วยดัชนี

คำถามหลัก: การดำเนินการใดที่เกิดบ่อยที่สุด และโครงสร้างใดทำให้มันเร็วที่สุด?

3. ประเมินความซับซ้อน (Estimate complexity) — ก่อนเขียนโค้ด ประมาณ Big-O ของแนวทางที่คิดไว้ ถ้าได้ O(n²) กับข้อมูลล้านตัวให้รู้ตัวตั้งแต่ตอนนี้ ไม่ใช่ตอนระบบล่ม

คำถามหลัก: ถ้าอินพุตโตขึ้น 10 เท่า เวลาทำงานจะโตขึ้นกี่เท่า?

4. ลงมือเขียน (Implement — ใช้ AI ได้) — ตอนนี้ค่อยเขียนโค้ด และใช้ AI ช่วยได้เต็มที่ เพราะคุณมีแผนแล้ว AI จึงเป็น “ลูกมือที่เขียนเร็ว” ไม่ใช่ “สมองที่ตัดสินใจแทนคุณ”

คำถามหลัก: โค้ดนี้ตรงกับแผนความซับซ้อนที่ฉันตั้งใจไว้หรือไม่?

5. ตรวจสอบ (Verify) — ทดสอบกับกรณีปกติ กรณีขอบ (ลิสต์ว่าง ค่าซ้ำ ค่าเดียว) และตรวจว่าความซับซ้อนจริงตรงกับที่ประเมินไว้

คำถามหลัก: มีอินพุตแบบใดที่จะทำให้โค้ดนี้พังหรือช้าลงผิดคาด?

6. ปรับปรุง (Improve) — เมื่อถูกต้องแล้ว ค่อยถามว่าอ่านง่ายขึ้นได้ไหม เร็วขึ้นได้ไหม กระชับขึ้นได้ไหม การปรับก่อนถูกต้องคือการเสียเวลาเปล่า

คำถามหลัก: จุดใดที่ปรับให้ชัดหรือเร็วขึ้นได้ โดยไม่ทำให้ความถูกต้องเสียไป?

เมื่อทำงานร่วมกับ AI หกขั้นตอนนี้ยุบเหลือสี่ขั้นจริง ๆ: Prompt (สั่งงานหลังคิดแผนแล้ว) Read (อ่านโค้ดที่ AI ให้มาอย่างละเอียด) Judge (ตัดสินความถูกต้องและความซับซ้อน) Improve (แก้จุดที่พลาด) เราจะฝึกวงจรนี้ซ้ำสี่รอบในโครงงานเดียวกันข้างล่าง

โครงงานตัวอย่าง: ระบบค้นหาและแนะนำเอกสาร

สมมติคุณต้องสร้างระบบสำหรับห้องสมุดเอกสารดิจิทัล ผู้ใช้ต้อง (1) พิมพ์คำแล้วเห็นคำแนะนำอัตโนมัติ (2) ค้นหาเอกสารโดยไม่ปนเอกสารที่ซ้ำกัน (3) เห็นผลลัพธ์เรียงตามความเกี่ยวข้อง (4) เห็นเอกสารที่ “เกี่ยวข้อง” กับเอกสารที่กำลังอ่านอยู่ นี่คือระบบเดียวที่ต้องใช้โครงสร้างข้อมูลสี่แบบทำงานร่วมกัน:

ขั้น	หน้าที่	โครงสร้างข้อมูลหลัก	เทคนิคการค้นหา/จัดเรียง
1	เติมคำอัตโนมัติ	ลิสต์ที่เรียงแล้ว	การค้นหาแบบไบนารี
2	กำจัดเอกสารซ้ำ + ทำดัชนี	ตารางแฮช	แฮชเป็นกุญแจ
3	จัดอันดับผลลัพธ์	ลิสต์คู่ (คะแนน)	การเรียงลำดับ
4	แนะนำเอกสารที่เกี่ยวข้อง	กราฟ (adjacency list)	BFS

เราจะเดินทั้งสี่ขั้นด้วยวงจรเดียวกันทุกครั้ง: Prompt → Read → Judge → Improve — AI จะให้คำตอบที่ “ถูกต้องแต่ไม่สเกล” ทุกครั้ง งานของคุณคือจับให้ได้ก่อนมันไปถึงโปรดักชัน

ขั้นที่ 1 — ค้นหา: เติมคำอัตโนมัติ (Autocomplete)

Prompt ที่ส่งให้ AI: “เขียนฟังก์ชัน search_prefix(words, prefix) ที่คืนคำทั้งหมดในลิสต์คำศัพท์ที่ขึ้นต้นด้วย prefix ระบบนี้จะถูกเรียกค้นหลายพันครั้งต่อวินาทีขณะผู้ใช้พิมพ์”

คำตอบของ AI (ดูเผิน ๆ ก็ถูกต้อง):

def search_prefix(words, prefix):
    """คืนคำทั้งหมดที่ขึ้นต้นด้วย prefix"""
    return [w for w in words if w.startswith(prefix)]

Read: โค้ดถูกต้อง 100% ทดสอบกับตัวอย่างเล็ก ๆ ก็ผ่านหมด อ่านง่าย ไม่มีบั๊กเชิงตรรกะเลย

Judge: ปัญหาไม่ได้อยู่ที่ความถูกต้อง แต่ที่ ความซับซ้อนเมื่อถูกเรียกซ้ำ แต่ละคอลเรียกใช้เวลา O(n · L) (n = จำนวนคำ, L = ความยาวคำเฉลี่ย) ระบบ autocomplete เรียกฟังก์ชันนี้ ทุกครั้งที่ผู้ใช้พิมพ์ตัวอักษร ถ้ามี q ครั้งต่อวินาที รวมเป็น O(q · n · L) — คำศัพท์ 200,000 คำกับผู้ใช้พิมพ์เร็ว จะหน่วงจนรู้สึกได้ทันที

Improve: เรียงลิสต์คำศัพท์ ครั้งเดียว ตอนสร้างระบบ แล้วใช้การค้นหาแบบไบนารีหาขอบเขตของคำที่ตรง prefix แทนการสแกนทั้งลิสต์ทุกครั้ง

(วิดเจ็ตด้านบนสาธิตหลักการค้นหาแบบไบนารีด้วยตัวเลขที่เรียงแล้ว หลักการเดียวกันนี้ใช้ค้นหาคำในลิสต์ที่เรียงตามตัวอักษรได้)

import bisect

class PrefixSearcher:
    """เรียงคำศัพท์ครั้งเดียว แล้วค้นหาคำนำหน้าได้เร็วซ้ำ ๆ"""

    def __init__(self, words):
        self.words = sorted(words)              # O(n log n) ครั้งเดียวตอนสร้าง

    def search(self, prefix):
        lo = bisect.bisect_left(self.words, prefix)
        hi = bisect.bisect_left(self.words, prefix + "￿")  # ขอบบน: อักษรที่มากกว่าใด ๆ
        return self.words[lo:hi]                # O(log n + k), k = จำนวนคำที่ตรง

# ตรวจสอบ
s = PrefixSearcher(["cat", "car", "dog", "care", "card"])
assert s.search("car") == ["car", "card", "care"]
assert s.search("z") == []                      # ไม่มีคำตรง
assert s.search("") == sorted(["cat","car","dog","care","card"])  # prefix ว่าง = ทั้งหมด

การเตรียมข้อมูล O(n log n) เกิดขึ้น ครั้งเดียว ส่วนทุกคำค้นหลังจากนั้นเหลือ O(log n + k) — เร็วกว่าเดิมแบบก้าวกระโดดเมื่อมีการค้นซ้ำจำนวนมาก นี่คือรูปแบบคลาสสิก: จ่ายต้นทุนล่วงหน้าครั้งเดียว แลกกับความเร็วตลอดไป

ขั้นที่ 2 — แฮช: กำจัดเอกสารซ้ำก่อนทำดัชนี

Prompt ที่ส่งให้ AI: “เขียนฟังก์ชัน find_duplicate_docs(docs) ที่คืนกลุ่มของดัชนีเอกสารที่มีเนื้อหาตรงกันทุกตัวอักษร”

คำตอบของ AI (ถูกต้อง แต่ซ่อนปัญหา):

def find_duplicate_docs(docs):
    groups = []
    used = set()
    for i in range(len(docs)):              # O(n)
        if i in used:
            continue
        group = [i]
        for j in range(i + 1, len(docs)):   # O(n) ซ้อนอยู่ข้างใน!
            if docs[j].strip() == docs[i].strip():
                group.append(j)
                used.add(j)
        if len(group) > 1:
            groups.append(group)
    return groups

Read: ผลลัพธ์ถูกต้องทุกกรณี ตรวจสอบด้วยตัวอย่างเล็ก ๆ ก็ผ่าน โครงสร้างโค้ดอ่านเข้าใจง่าย

Judge: มีลูปซ้อนกันสองชั้น — เทียบทุกคู่ของเอกสาร O(n²) และแต่ละการเทียบยังต้องเทียบตัวอักษร O(L) รวมเป็น O(n² · L) ห้องสมุดที่มีเอกสาร 100,000 ชิ้นจะต้องเทียบกันประมาณ 10 พันล้านคู่ — ใช้งานจริงไม่ได้

Improve: ใช้ ตารางแฮช (dict) จัดกลุ่มตามเนื้อหาแทนการเทียบทุกคู่ — เอกสารที่เหมือนกันจะตกลงกุญแจเดียวกันโดยอัตโนมัติ

from collections import defaultdict

def find_duplicate_docs(docs):
    """คืนกลุ่มของดัชนีเอกสารที่มีเนื้อหาตรงกัน (เฉพาะกลุ่มที่ซ้ำ)"""
    groups = defaultdict(list)          # กุญแจ(เนื้อหา) -> ลิสต์ของดัชนี
    for i, text in enumerate(docs):     # O(n)
        key = text.strip()              # ปรับให้เป็นมาตรฐานก่อนเทียบ
        groups[key].append(i)           # O(1) โดยเฉลี่ย
    return [idxs for idxs in groups.values() if len(idxs) > 1]

# ตรวจสอบ (พร้อมกรณีขอบ)
assert find_duplicate_docs([]) == []                        # ลิสต์ว่าง
assert find_duplicate_docs(["a"]) == []                     # ชิ้นเดียว ไม่มีซ้ำ
assert find_duplicate_docs(["a", "a", "a"]) == [[0, 1, 2]]   # ซ้ำสามชิ้น
assert find_duplicate_docs(["a ", "a"]) == [[0, 1]]          # ช่องว่างท้าย -> strip จัดให้เหมือนกัน

เดินผ่านเอกสารครั้งเดียว O(n) ชิ้น แต่ละชิ้นคำนวณกุญแจตามความยาว O(L) รวมเป็น O(n · L) — ดีกว่าการเทียบทุกคู่ O(n² · L) มหาศาล

ต่อยอด — ดัชนีค้นหาแบบเต็มข้อความ (inverted index): เมื่อกำจัดเอกสารซ้ำแล้ว เราใช้หลักการแฮชเดียวกันสร้าง “ดัชนีย้อนกลับ” — dict ที่กุญแจคือคำศัพท์ และค่าคือเซตของรหัสเอกสารที่มีคำนั้น

def build_inverted_index(docs):
    index = defaultdict(set)
    for doc_id, text in enumerate(docs):        # O(n)
        for word in set(text.lower().split()):  # O(L) ต่อเอกสาร
            index[word].add(doc_id)             # O(1) โดยเฉลี่ย
    return index

# ค้นหาเอกสารที่มีคำว่า "python" -> O(1) โดยเฉลี่ย แทนที่จะสแกนทุกเอกสารทุกครั้ง

การสร้างดัชนีเป็น O(รวมจำนวนคำในทุกเอกสาร) ครั้งเดียว หลังจากนั้นการค้นหาแต่ละคำเหลือ O(1) โดยเฉลี่ย — รูปแบบเดียวกับขั้นที่ 1: จ่ายล่วงหน้าครั้งเดียว แลกความเร็วตลอดไป

ขั้นที่ 3 — เรียงลำดับ: จัดอันดับผลลัพธ์การค้นหา

Prompt ที่ส่งให้ AI: “เรียงผลลัพธ์การค้นหา (คู่ของรหัสเอกสารกับคะแนนความเกี่ยวข้อง) จากคะแนนมากไปน้อย”

คำตอบของ AI (ทำงานถูกต้อง แต่…):

def sort_by_score(results):  # results: [(doc_id, score), ...]
    n = len(results)
    for i in range(n):
        for j in range(n - 1):
            if results[j][1] < results[j + 1][1]:
                results[j], results[j + 1] = results[j + 1], results[j]
    return results

Read: นี่คือ bubble sort เรียงจากมากไปน้อยถูกต้องตามที่ขอ ทดสอบกับผลลัพธ์ไม่กี่รายการก็ทำงานถูกทุกครั้ง

Judge: bubble sort คือ O(n²) เสมอ ไม่ว่าข้อมูลจะเรียบร้อยแค่ไหน ระบบค้นหาจริงอาจต้องเรียงผลลัพธ์หลายหมื่นรายการต่อคำค้นหนึ่งครั้ง — AI เขียนอัลกอริทึมเรียงลำดับเองทั้งที่ไม่จำเป็น ทั้งที่ภาษามีอัลกอริทึมเรียงลำดับที่ปรับแต่งมาอย่างดีให้ใช้ฟรีอยู่แล้ว

Improve: ใช้ฟังก์ชันเรียงลำดับมาตรฐานของภาษา (Timsort ใน Python) ซึ่งรับประกัน O(n log n)

def sort_by_score(results):
    return sorted(results, key=lambda r: r[1], reverse=True)   # O(n log n)

# ถ้าต้องการแค่ k อันดับแรก (ทั่วไปสำหรับหน้าค้นหา) ใช้ heapq จะเร็วกว่าอีก
import heapq
def top_k_by_score(results, k):
    return heapq.nlargest(k, results, key=lambda r: r[1])      # O(n log k)

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

ขั้นที่ 4 — กราฟ: แนะนำเอกสารที่เกี่ยวข้อง

Prompt ที่ส่งให้ AI: “เอกสารสองชิ้นเชื่อมกันถ้ามีแท็กร่วมกัน เขียนฟังก์ชัน related_docs(graph, start, max_hops=2) หาเอกสารทั้งหมดที่เชื่อมถึงภายใน 2 ระดับ (hops)”

คำตอบของ AI (มีบั๊กที่อันตรายกว่าที่ผ่านมา):

def related_docs(graph, start, max_hops=2):
    result = []
    def dfs(node, hops):
        if hops > max_hops:
            return
        for neighbor in graph[node]:
            result.append(neighbor)
            dfs(neighbor, hops + 1)     # ไม่มี visited set!
    dfs(start, 0)
    return result

Read: โค้ดวนลูปหาเพื่อนบ้านแล้วเรียกตัวเองซ้ำ (DFS) ดูเผิน ๆ เหมือนจะครอบคลุมทุกเอกสารภายใน 2 ระดับ

Judge: นี่ไม่ใช่แค่ปัญหาความซับซ้อน แต่เป็น บั๊กที่ทำให้โปรแกรมพังจริง — ไม่มี visited set เลย ถ้ากราฟมีวงจร (เอกสาร A เชื่อมกับ B และ B เชื่อมกลับมา A ซึ่งเกิดขึ้นเสมอเพราะแท็กร่วมกันเป็นสองทิศทาง) ฟังก์ชันจะวนซ้ำไม่รู้จบจนเกิด RecursionError แม้ไม่มีวงจรจริง ผลลัพธ์ก็ยังมีเอกสารซ้ำซ้อนหลายครั้งเพราะเดินทางถึงเอกสารเดียวกันได้จากหลายเส้นทาง

Improve: ใช้ BFS พร้อม visited set — รับประกันว่าแต่ละเอกสารถูกเยี่ยมชมครั้งเดียว และควบคุมจำนวน hops ได้ตรงกว่า DFS

from collections import deque

def related_docs(graph, start, max_hops=2):
    visited = {start}
    result = []
    queue = deque([(start, 0)])
    while queue:                            # O(V + E) รวม
        node, hops = queue.popleft()
        if hops == max_hops:
            continue
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)       # กันการเยี่ยมซ้ำ / วนซ้ำไม่รู้จบ
                result.append(neighbor)
                queue.append((neighbor, hops + 1))
    return result

# ตรวจสอบ พร้อมกรณีขอบที่มีวงจร
graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A"], "D": ["B"]}
assert related_docs(graph, "A", max_hops=1) == ["B", "C"]
assert set(related_docs(graph, "A", max_hops=2)) == {"B", "C", "D"}
assert related_docs(graph, "A", max_hops=0) == []

ความซับซ้อนคือ O(V + E) ตามจำนวนเอกสารและการเชื่อมโยงที่ถูกเยี่ยมชมจริง — บั๊กเรื่อง visited set นี้เป็นรูปแบบที่พบบ่อยที่สุดอย่างหนึ่งเวลา AI เขียนโค้ดท่องกราฟ ให้จับตาดูเป็นพิเศษ

ประกอบร่างเป็นระบบเดียว

เมื่อทั้งสี่ขั้นผ่านวงจร Prompt → Read → Judge → Improve แล้ว เราประกอบเป็นคลาสเดียว แต่ละเมธอดคือขั้นตอนที่ตรวจสอบแล้ว:

class DocumentSearchEngine:
    def __init__(self, docs):
        clean_ids = [g[0] for g in find_duplicate_docs(docs)] or list(range(len(docs)))
        self.docs = docs
        self.index = build_inverted_index(docs)          # ขั้นที่ 2: O(รวมจำนวนคำ)
        self.autocomplete = PrefixSearcher(self._all_words(docs))  # ขั้นที่ 1: O(n log n)
        self.tag_graph = build_tag_graph(docs)            # ขั้นที่ 4: O(n · แท็กเฉลี่ย)

    def suggest(self, prefix):
        return self.autocomplete.search(prefix)           # O(log n + k)

    def search(self, query_words):
        matches = set.intersection(*(self.index[w] for w in query_words))
        scored = [(doc_id, self._score(doc_id, query_words)) for doc_id in matches]
        return sort_by_score(scored)                      # O(n log n)

    def related(self, doc_id):
        return related_docs(self.tag_graph, doc_id, max_hops=2)  # O(V + E)

สังเกตว่า แต่ละขั้นมีความซับซ้อนของตัวเอง และไม่มีขั้นใดขั้นหนึ่งทำให้ขั้นอื่นช้าลง นี่คือเหตุผลที่ต้องประเมิน Big-O แยกทีละส่วน ก่อนรวมระบบ — ถ้ารวมกันก่อนแล้วค่อยวัดความเร็ว จะหาไม่เจอว่าส่วนไหนคือคอขวด

การเลือกและการให้เหตุผล

จุดที่แยกมือใหม่ออกจากมืออาชีพคือ ความสามารถในการอธิบายว่าทำไมถึงเลือกโครงสร้างนั้น สรุปเหตุผลทั้งสี่ขั้นของโครงงานนี้:

ขั้น	โครงสร้างที่เลือก	ทางเลือกที่ปฏิเสธ	ข้อแลกเปลี่ยน
1. ค้นหา	ลิสต์เรียงแล้ว + ค้นหาไบนารี	สแกนทั้งลิสต์ทุกครั้ง (O(n) ต่อคำค้น)	ต้องเรียงใหม่เมื่อเพิ่มคำ ($O(n)$ ต่อการแทรก)
2. แฮช	dict/defaultdict	เทียบทุกคู่ O(n²)	ใช้หน่วยความจำเก็บกุญแจ, O(1) เป็นค่าเฉลี่ยเท่านั้น
3. เรียงลำดับ	sorted() (Timsort)	bubble/selection sort เขียนเอง	ไม่มี — ไลบรารีมาตรฐานชนะทุกด้านในกรณีทั่วไป
4. กราฟ	BFS + visited set	DFS แบบไม่มี visited (พังกับวงจร)	BFS ใช้คิวเพิ่ม แต่ปลอดภัยและควบคุม hops ได้ตรงกว่า

เหตุผลที่ดีไม่ได้บอกแค่ว่า “เลือกอะไร” แต่บอกว่า “ทำไมจึงดีกว่าทางเลือกอื่น และยอมแลกอะไรไป”

เช็กลิสต์ของผู้ตัดสิน (Judge’s Checklist)

นี่คือเช็กลิสต์ที่คุณเห็นถูกใช้ซ้ำสี่ครั้งข้างบน — จำไว้แล้วใช้ตัดสินโค้ด AI ชิ้นไหนก็ได้ ไปตลอดอาชีพการทำงาน ไม่ว่า AI จะฉลาดขึ้นแค่ไหน

• ความถูกต้อง (Correctness): ให้ผลถูกต้องกับอินพุตปกติหรือไม่
• กรณีขอบ (Edge cases): ทดสอบลิสต์ว่าง ค่าเดียว ค่าซ้ำทั้งหมด ค่าติดลบ กราฟที่มีวงจร และอินพุตที่ใหญ่มากแล้วหรือยัง
• ความซับซ้อน (Complexity): Big-O จริงเป็นเท่าไร และตรงกับที่ตั้งใจไว้หรือไม่ มีลูปซ้อนหรือ in บน list ที่ซ่อนอยู่หรือเปล่า
• โครงสร้างข้อมูล: เลือกถูกกับงานหรือไม่ มีโครงสร้างที่ทำให้เร็วกว่านี้หรือไม่
• ความอ่านง่าย (Readability): ชื่อตัวแปรสื่อความหมาย โครงสร้างชัด มีคอมเมนต์ในจุดที่ตรรกะซับซ้อนหรือไม่
• ความทนทาน (Robustness): จัดการอินพุตที่ไม่ถูกต้องอย่างเหมาะสมหรือไม่
• รูปแบบที่พบซ้ำ (Common tells): มี in บน list ในลูปหรือไม่ · มีลูปซ้อนที่ซ่อนอยู่ในเมธอดหรือไม่ · มีการท่องกราฟ/ต้นไม้โดยไม่มี visited set หรือไม่ · มีอัลกอริทึมมาตรฐาน (เรียง/ค้นหา) ที่เขียนขึ้นเองทั้งที่ไลบรารีมีให้แล้วหรือไม่

ท่องสี่คำถามนี้ให้ขึ้นใจ: ถูกไหม? ขอบพังไหม? ซับซ้อนแค่ไหน? อ่านง่ายไหม? สี่คำถามนี้จับปัญหาได้เกือบทุกกรณีที่ AI ทำพลาด

โจทย์เปิด (ตาของคุณ — ต่อยอดแต่ละขั้น)

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

A. เติมคำอัตโนมัติที่ทนต่อการพิมพ์ผิด — ขั้นที่ 1 ใช้การจับคู่ตรงตัวทุกตัวอักษร แต่ผู้ใช้พิมพ์ผิดบ่อย (“pyhton” ควรเจอ “python”) จะออกแบบโครงสร้างข้อมูลและอัลกอริทึมอย่างไรให้ยังคงเร็วพอสำหรับพิมพ์แต่ละตัวอักษร?

คำใบ้

พิจารณา ระยะแก้ไข (edit distance) ระหว่าง prefix กับคำในดัชนี แต่การคำนวณระยะแก้ไขกับทุกคำเป็น O(n) ต่อคำค้น — ลองมองหาโครงสร้างที่จำกัดขอบเขตการค้นหาก่อนคำนวณระยะแก้ไข เช่น trie ที่ตัดกิ่งเร็ว หรือดัชนี n-gram ที่กรองคำที่ไม่มีทางใกล้เคียงออกก่อน

B. ตรวจจับเอกสารที่คล้ายกัน ไม่ใช่แค่เหมือนเป๊ะ — ขั้นที่ 2 ตรวจจับได้เฉพาะเนื้อหาที่ตรงกันทุกตัวอักษร จะขยายให้ตรวจจับเอกสารที่ต่างกันแค่ช่องว่าง ตัวพิมพ์เล็กใหญ่ หรือแม้แต่สลับลำดับคำเล็กน้อยได้อย่างไร โดยยังคงความซับซ้อนใกล้เคียง O(n)?

คำใบ้

ขั้นแรกคือ normalize เนื้อหาก่อนแฮช (ลดตัวพิมพ์ แทนช่องว่างซ้ำ ตัดเครื่องหมายวรรคตอน) วิธีนี้จัดการกรณีต่างช่องว่าง/ตัวพิมพ์ได้ทันทีด้วยแฮชแบบเดิม สำหรับกรณี “คล้ายกันแต่ไม่เป๊ะ” (คำสลับลำดับ) ลองค้นว่า MinHash หรือ shingling แก้ปัญหานี้อย่างไรโดยยังคงใช้แฮชเป็นแกนหลัก

C. จัดอันดับผลลัพธ์ด้วยหลายคะแนนพร้อมกัน — ขั้นที่ 3 เรียงตามคะแนนเดียว แต่ระบบจริงต้องผสมความเกี่ยวข้องกับความใหม่ของเอกสาร แล้วถ้าคะแนนเท่ากันต้องมีกติกาตัดสินที่ เสถียร (stable) จะออกแบบ key ของการเรียงลำดับอย่างไร?

คำใบ้

sorted() ใน Python เป็น stable sort อยู่แล้ว (รักษาลำดับเดิมของสิ่งที่คะแนนเท่ากัน) — ใช้ประโยชน์จากคุณสมบัตินี้ได้โดยส่ง key เป็น tuple ของหลายเกณฑ์ตามลำดับความสำคัญ เช่น key=lambda r: (-r.relevance, -r.recency) ลองคิดว่าทำไมลำดับของ tuple ถึงมีผลต่อผลลัพธ์

D. เส้นทางที่ “เกี่ยวข้องที่สุด” ไม่ใช่แค่ “ใกล้ที่สุด” — ขั้นที่ 4 ใช้ BFS นับจำนวน hops เท่า ๆ กันทุกเส้นเชื่อม แต่ถ้าแท็กบางคู่ “เกี่ยวข้องกันมาก” กว่าคู่อื่น (มีน้ำหนักต่างกัน) BFS จะให้คำตอบที่ดีที่สุดไหม?

คำใบ้

BFS รับประกันเส้นทางสั้นที่สุดเฉพาะกรณี ทุกเส้นเชื่อมมีน้ำหนักเท่ากัน เมื่อน้ำหนักต่างกัน ต้องมองหาอัลกอริทึมที่เลือกเส้นทาง “ต้นทุนน้อยที่สุด” ไม่ใช่ “จำนวนก้าวน้อยที่สุด” — ลองค้นคำว่า Dijkstra’s algorithm และดูว่าทำไมมันถึงต้องใช้ priority queue แทนคิวธรรมดา

เกณฑ์ประเมินตนเอง

สัดส่วน	องค์ประกอบ	วัดอะไร
40%	การวิพากษ์โค้ด AI	ความสามารถในการอ่านโค้ดของ AI ตัดสินความถูกต้องและความซับซ้อน ชี้จุดบกพร่อง และปรับปรุงได้ด้วยตนเอง
30%	โครงงานพร้อมเหตุผล	คุณภาพของคำตอบที่ทำงานได้จริง ความชัดเจนของเหตุผลในการเลือกโครงสร้าง และความถูกต้องของการวิเคราะห์ Big-O
20%	แบบทดสอบแนวคิด	ความเข้าใจหลักการพื้นฐาน — โครงสร้างข้อมูล ความซับซ้อน และเมื่อใดควรใช้สิ่งใด
10%	การมีส่วนร่วม	การลงมือทำแบบฝึกหัด การถามคำถาม และการร่วมอภิปรายตลอดหลักสูตร

แบบฝึกหัด

1. หาคู่ที่บวกได้เป้าหมาย (Two Sum) — ครบวงจร จงเดินทั้งหกขั้นตอนสั้น ๆ แล้วเขียนฟังก์ชันที่รับลิสต์ nums และ target คืนดัชนีของเลขสองตัวที่บวกกันได้ target

เฉลย

แตกปัญหา: หาคู่ที่ผลรวมเท่ากับ target — เลือกโครงสร้าง: dict จำค่าที่เคยเห็น — ประเมิน: O(n) — เขียน — ตรวจสอบกรณีขอบ — ปรับปรุง: เดินรอบเดียวก็พอ

def two_sum(nums, target):
    seen = {}                       # ค่า -> ดัชนี
    for i, x in enumerate(nums):    # O(n)
        need = target - x
        if need in seen:            # O(1)
            return [seen[need], i]
        seen[x] = i
    return None
# two_sum([2, 7, 11, 15], 9) -> [0, 1]

แทนการเทียบทุกคู่ O(n²) เราจำค่าที่ผ่านมาแล้วใน dict และถามว่า target - x เคยเห็นไหมใน O(1) รวมเป็น O(n)

2. นับความถี่และหาตัวที่พบบ่อยที่สุด ให้ลิสต์ของรายการ จงคืนรายการที่ปรากฏบ่อยที่สุด เดินครบทั้งหกขั้นตอน

เฉลย

เลือกโครงสร้าง: dict/Counter เพราะต้องอัปเดตจำนวนซ้ำ ๆ — ประเมิน: O(n)

from collections import Counter

def most_common_item(items):
    if not items:                   # กรณีขอบ: ลิสต์ว่าง
        return None
    counts = Counter(items)         # O(n)
    return counts.most_common(1)[0][0]
# most_common_item(["a","b","a","c","a"]) -> "a"

ถ้าใช้ list แล้วนับด้วยการค้นทีละตัวจะเป็น O(n²) แต่ dict ทำให้แต่ละการอัปเดตเป็น O(1) รวมเป็น O(n)

3. ตรวจวงเล็บสมดุล (Balanced parentheses) ให้สตริงของวงเล็บ ()[]{} จงตรวจว่าจับคู่ปิด-เปิดถูกต้องหรือไม่

เฉลย

เลือกโครงสร้าง: สแตก (stack) เพราะวงเล็บที่เปิดทีหลังต้องปิดก่อน (LIFO) — ประเมิน: O(n)

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:                    # O(n)
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack                # ต้องไม่มีวงเล็บค้าง
# is_balanced("({[]})") -> True ; is_balanced("(]") -> False

กรณีขอบ: สตริงว่าง -> True, วงเล็บเปิดค้าง -> False, วงเล็บปิดเกิน -> False

4. จับบั๊กในการค้นหาไบนารี โค้ดนี้ตั้งใจค้นหาไบนารีแบบวนซ้ำ (iterative) แต่มีบั๊กซ่อนอยู่หนึ่งจุด หาให้เจอ แล้วอธิบายว่ากรณีอินพุตแบบใดที่จะทำให้มันพัง

def binary_search(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid
        else:
            hi = mid
    return -1

เฉลย

บั๊กอยู่ที่ lo = mid ควรเป็น lo = mid + 1 เมื่อ arr[mid] < target ถ้าไม่บวก 1 และ lo == mid พอดี (เช่น lo=1, hi=2, mid=1) ลูปจะวนซ้ำค่าเดิมไม่รู้จบ — วนไม่รู้จบ (infinite loop) ไม่ใช่แค่ผลลัพธ์ผิด

def binary_search(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1         # แก้แล้ว
        else:
            hi = mid
    return -1

ทดสอบให้แน่ใจด้วยลิสต์ที่มีสองสมาชิก เช่น binary_search([1, 2], 2) — นี่คือกรณีขอบที่ดักบั๊กประเภทนี้ได้ดีที่สุด

5. ทำนายผลลัพธ์: BFS กับ DFS ให้กราฟ {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []} จงทำนายว่า BFS จาก “A” กับ DFS จาก “A” จะเยี่ยมชมโหนดตามลำดับใด และอธิบายว่าทำไมทั้งสองต่างกัน

เฉลย

BFS (ใช้คิว, ไปทีละระดับ): A, B, C, D — เยี่ยม B และ C (ระดับ 1) ก่อน D (ระดับ 2)

DFS (ใช้สแตก/การเรียกซ้ำ, ลงลึกก่อน): A, B, D, C — ลงไปที่ B แล้วลึกไปถึง D ก่อนจะย้อนกลับมาที่ C

ทั้งสองแบบเยี่ยมชมทุกโหนดใน O(V + E) เท่ากัน ต่างกันแค่ ลำดับ — BFS เหมาะกับ “หาเส้นทางสั้นที่สุด” ส่วน DFS เหมาะกับ “สำรวจให้ลึกที่สุดก่อน” เช่น ตรวจการเชื่อมต่อ หรือหาวงจร

6. อะไรคือ Big-O ที่แท้จริง โค้ดนี้สร้างดัชนีย้อนกลับ (inverted index) ให้บอก Big-O ของฟังก์ชันนี้ในรูปของ n (จำนวนเอกสาร) และ L (จำนวนคำเฉลี่ยต่อเอกสาร) พร้อมอธิบายเหตุผล

def build_inverted_index(docs):
    index = {}
    for doc_id, text in enumerate(docs):
        for word in text.split():
            if word not in index:
                index[word] = []
            if doc_id not in index[word]:      # <- จุดสังเกต
                index[word].append(doc_id)
    return index

เฉลย

ดูเผิน ๆ เหมือน O(n · L) เพราะมีลูปซ้อนแค่ “เอกสาร × คำในเอกสาร” แต่บรรทัด if doc_id not in index[word] ทำการค้นหาบน list ซึ่งเป็น O(k) โดย k คือจำนวนเอกสารที่มีคำนั้นอยู่แล้ว ในกรณีเลวร้ายสุด (คำที่พบในเกือบทุกเอกสาร) จะกลายเป็น O(n) ต่อครั้ง ทำให้รวมทั้งหมดแย่ลงเป็น O(n² · L) ในกรณีเลวร้าย

วิธีแก้: เปลี่ยน index[word] จาก list เป็น set — if doc_id not in index[word] จะเหลือ O(1) โดยเฉลี่ย ทำให้ทั้งฟังก์ชันกลับมาเป็น O(n · L) ตามที่ตั้งใจไว้ นี่คือรูปแบบเดียวกับที่พบในขั้นที่ 2 ของโครงงาน — “list ที่ซ่อนอยู่ข้างในทำให้ O(1) ที่หวังไว้กลายเป็น O(n)”

วิพากษ์โค้ดจากปัญญาประดิษฐ์ — ด่านสุดท้าย

โจทย์รวบยอด: คุณขอให้ AI เขียนฟังก์ชันหา “จำนวนคู่ของรายการที่ซ้ำกัน” ในลิสต์ AI ตอบกลับมาเป็นโค้ดที่ ถูกต้อง แต่มีจุดบกพร่องด้านความซับซ้อนที่ซ่อนอยู่ — แบบเดียวกับที่พบในทุกขั้นของโครงงานข้างบน จงเดินวงจร อ่าน → ตัดสิน → ปรับปรุง อีกครั้งด้วยตัวเอง โดยไม่มีคำใบ้ก่อน

def count_duplicate_pairs(items):
    """นับว่ามีกี่คู่ (i, j) ที่ items[i] == items[j] โดย i < j"""
    seen = []
    count = 0
    for x in items:
        if x in seen:               # ดูเผิน ๆ เหมือน O(1) แต่...
            count += seen.count(x)  # นับว่ามีตัวนี้กี่ตัวแล้ว
        seen.append(x)
    return count

อ่าน: โค้ดเดินผ่าน items ครั้งเดียว ดูเหมือน O(n) แต่ seen เป็น list ดังนั้น x in seen เป็น O(n) และ seen.count(x) ก็ O(n) อีก

ตัดสิน: ความซับซ้อนจริงคือ O(n²) ไม่ใช่ O(n) อย่างที่หน้าตาโค้ดชวนให้เข้าใจผิด เมื่อ items มีล้านตัวจะช้าจนใช้ไม่ได้ นี่คือจุดบกพร่องด้านความซับซ้อนแบบละเอียดที่ “ผลลัพธ์ถูกแต่ช้าผิดคาด” — สังเกตว่านี่คือ รูปแบบเดียวกับขั้นที่ 2 และแบบฝึกหัดข้อ 6 ทุกประการ: list ที่ซ่อนอยู่ทำให้สิ่งที่ดูเหมือน O(1) กลายเป็น O(n)

ปรับปรุง: เปลี่ยน seen เป็น dict (หรือ Counter) เพื่อให้ทั้งการตรวจและการนับเป็น O(1)

เฉลย

from collections import defaultdict

def count_duplicate_pairs(items):
    counts = defaultdict(int)
    pairs = 0
    for x in items:                 # O(n)
        pairs += counts[x]          # ทุกตัวก่อนหน้าที่เท่ากับ x จับคู่กับตัวนี้ได้ -> O(1)
        counts[x] += 1              # O(1)
    return pairs
# count_duplicate_pairs([1, 2, 1, 1]) -> 3  (คู่ของเลข 1 สามคู่)

ใช้ dict นับจำนวนที่เคยเห็นของแต่ละค่า ทุกครั้งที่พบ x ซ้ำ มันจับคู่กับตัวก่อนหน้าทั้งหมดได้พอดี counts[x] คู่ ทุกการดำเนินการเป็น O(1) รวมทั้งงานจึงเป็น O(n) — แก้จุดบกพร่อง O(n²) ที่ AI ทิ้งไว้ ถ้าคุณจับรูปแบบนี้ได้ในสามที่ที่ต่างกัน (ขั้นที่ 2, แบบฝึกหัด 6, และที่นี่) แปลว่าเช็กลิสต์ของผู้ตัดสินได้กลายเป็นสัญชาตญาณของคุณแล้ว

🎮 เกมเดฟ: ชั้นข้อมูลของโร้กไลก์ขนาดเล็ก

ทุกอย่างในหลักสูตรนี้ — แฮช การเรียงลำดับ ต้นไม้ กราฟ — มารวมกันอยู่ในลูปเทิร์นของเกมโร้กไลก์เกมเดียว ทุกระบบที่โร้กไลก์ต้องมี (ตรวจจับการชนกันของตัวละคร หาเส้นทาง เลือกไอเทม ตัดสินว่าใครขยับก่อน) แท้จริงแล้วคือคำถาม “โครงสร้างข้อมูลไหน ความซับซ้อนเท่าไร” ที่แต่งตัวเป็นแฟนตาซีเท่านั้นเอง ด้านล่างนี้เราจะร่างชั้นข้อมูลทั้งหมดของโร้กไลก์เป็น Python ระบุโครงสร้าง/อัลกอริทึมของแต่ละระบบพร้อม Big-O และเดินเลนส์ Prompt → Read → Judge → Improve ของบทนี้กับระบบที่เขียนแบบไร้เดียงสาหนึ่งระบบ

ระบบ	วัน	โครงสร้าง/อัลกอริทึม	Big-O
ตรวจจับการชน	1–2	ตารางแฮชเชิงพื้นที่ (spatial hash)	เฉลี่ย O(1) เทียบกับแบบไร้เดียงสา O(n²)
ทะเบียนตัวละคร + กระเป๋าไอเทม	2	dict คีย์ด้วยรหัสตัวละคร	O(1) ค้นหา/เพิ่ม
หาเส้นทางของศัตรู	3	A* บนกริดไทล์ (priority queue + heuristic)	O(E log V)
วางแผนเก็บไอเทม	3	DP บนกริด (คะแนนสูงสุดที่ไปถึงแต่ละไทล์ได้)	O(rows · cols)
ลำดับเทิร์น	2	Priority queue (min-heap) คีย์ด้วย “เวลาขยับถัดไป”	O(log n) ต่อเทิร์น

<rect x="150" y="20" width="130" height="60" rx="6" fill="none" stroke="#22c55e"/>
<text x="160" y="40" fill="currentColor">Entities+Inv</text>
<text x="160" y="58" fill="#22c55e">dict · O(1)</text>

<rect x="290" y="20" width="130" height="60" rx="6" fill="none" stroke="#38bdf8"/>
<text x="300" y="40" fill="currentColor">Enemy AI</text>
<text x="300" y="58" fill="#38bdf8">A* · O(E log V)</text>

<rect x="430" y="20" width="130" height="60" rx="6" fill="none" stroke="#f97316"/>
<text x="440" y="40" fill="currentColor">Loot Route</text>
<text x="440" y="58" fill="#f97316">Grid DP · O(r·c)</text>

<rect x="570" y="20" width="130" height="60" rx="6" fill="none" stroke="#ef4444"/>
<text x="580" y="40" fill="currentColor">Turn Order</text>
<text x="580" y="58" fill="#ef4444">Heap · O(log n)</text>

Game Loop one tick per turn

รูป: แต่ละระบบของโร้กไลก์ผูกกับโครงสร้างข้อมูลและขอบเขต Big-O ของตัวเองหนึ่งอย่าง แล้วทั้งห้าระบบไหลเข้าสู่ลูปเกมเดียวในทุกเทิร์น

ระบบไร้เดียงสาที่ถูกตัดสิน: การตรวจจับการชน

Prompt ที่ส่งให้ AI: “เขียนฟังก์ชัน nearby_entities(entities, x, y, radius) ที่คืนตัวละครทั้งหมดที่อยู่ภายในระยะ radius ไทล์จาก (x, y) ฟังก์ชันนี้จะถูกเรียกหนึ่งครั้งต่อเฟรมสำหรับมอนสเตอร์ทุกตัวบนด่านเพื่อตรวจการชน”

คำตอบของ AI:

def nearby_entities(entities, x, y, radius):
    """สแกนตัวละครทุกตัว แล้วเก็บเฉพาะตัวที่อยู่ในระยะ radius"""
    return [e for e in entities
            if abs(e.x - x) <= radius and abs(e.y - y) <= radius]

Read: ถูกต้อง ทดสอบกับตัวอย่างเล็ก ๆ ผ่านหมด — 5 ตัวละคร 10 ตัวละคร ก็ทำงานถูก

Judge: นี่คือ O(n) ต่อการเรียกหนึ่งครั้ง และถูกเรียก หนึ่งครั้งต่อมอนสเตอร์ ต่อเฟรม — รวมเป็น O(n²) ต่อเฟรมทั่วทั้งด่าน ด่านที่มีตัวละคร 300 ตัวตรวจการชน 60 ครั้งต่อวินาที คือการเทียบระยะห่างถึง 5.4 ล้านครั้งต่อวินาทีสำหรับฟังก์ชันนี้ฟังก์ชันเดียว รูปแบบความผิดพลาดเดียวกับขั้นที่ 2 ของระบบค้นหาเอกสารข้างต้น: โค้ดถูกต้อง แต่ความซับซ้อนไม่สเกล

Improve: จัดกลุ่มตัวละครลงใน ตารางแฮชเชิงพื้นที่ (spatial hash) — dict ที่คีย์ด้วย (cell_x, cell_y) — เพื่อให้การค้นหาสแกนเฉพาะตัวละครไม่กี่ตัวในเซลล์ใกล้เคียง แทนที่จะสแกนทั้งด่าน

class SpatialHash:
    """จัดกลุ่มตัวละครตามเซลล์ของกริด: แทรก O(1) เฉลี่ย, ค้นหา O(1) เฉลี่ย"""

    def __init__(self, cell_size: int = 4) -> None:
        self.cell_size = cell_size
        self.cells: dict[tuple[int, int], list] = {}

    def _key(self, x: float, y: float) -> tuple[int, int]:
        return (int(x // self.cell_size), int(y // self.cell_size))

    def insert(self, entity) -> None:
        self.cells.setdefault(self._key(entity.x, entity.y), []).append(entity)

    def nearby(self, x: float, y: float, radius: int = 1):
        cx, cy = self._key(x, y)
        found = []
        for dx in range(-radius, radius + 1):
            for dy in range(-radius, radius + 1):
                found.extend(self.cells.get((cx + dx, cy + dy), []))
        return found

# ตรวจสอบ
class Entity:
    def __init__(self, x, y):
        self.x, self.y = x, y

grid = SpatialHash(cell_size=4)
a, b, c = Entity(0, 0), Entity(1, 1), Entity(50, 50)
for e in (a, b, c):
    grid.insert(e)
assert set(grid.nearby(0, 0)) == {a, b}   # c อยู่ไกลมาก -> ไม่ถูกสแกนเลย

การแทรกเป็น O(1) โดยเฉลี่ย ส่วนการค้นหาสัมผัสแค่ (2·radius+1)² เซลล์ แต่ละเซลล์มีตัวละครจำนวนเกือบคงที่ — เฉลี่ย O(1) แทน O(n) เมื่อคูณด้วยมอนสเตอร์ทุกตัวบนด่าน ทั้งเฟรมจึงลดจาก O(n²) เหลือประมาณ O(n)

(สลับระหว่างโหมด brute-force กับโหมดกริดด้านบน — ดูตัวนับจำนวนการเทียบยุบตัวลงทันทีเมื่อตัวละครถูกจัดกลุ่มตามเซลล์)

ตัวละครและกระเป๋าไอเทม: dict เดียว คีย์ด้วยรหัส

entities: dict[int, dict] = {}          # entity_id -> {"hp": ..., "pos": ...}
inventories: dict[int, list[str]] = {}  # entity_id -> รายชื่อไอเทม

def pick_up(entity_id: int, item: str) -> None:
    inventories.setdefault(entity_id, []).append(item)   # O(1) ตัดจ่ายเฉลี่ย

# ตรวจสอบ
entities[1] = {"hp": 10, "pos": (0, 0)}
pick_up(1, "torch")
pick_up(1, "dagger")
assert inventories[1] == ["torch", "dagger"]
assert entities[1]["hp"] == 10          # ค้นหาด้วยรหัส O(1)

ทุกการค้นหา การลดพลังชีวิต หรือการตรวจกระเป๋าไอเทมเป็น O(1) เพราะตัวละครอยู่ใน dict ที่คีย์ด้วยรหัส — กลเม็ดเดียวกับดัชนีย้อนกลับของระบบค้นหาเอกสาร เพียงแต่เปลี่ยนจากคำศัพท์เป็นตัวละคร

หาเส้นทางของศัตรู: A*

import heapq

def astar(grid, start, goal):
    """grid[y][x] เป็น True แปลว่าเป็นกำแพง คืนเส้นทางที่สั้นที่สุดที่เดินได้ หรือ None"""
    def h(p):  # heuristic ระยะแบบแมนฮัตตัน
        return abs(p[0] - goal[0]) + abs(p[1] - goal[1])

    frontier = [(h(start), 0, start, [start])]
    seen = {start}
    while frontier:                                    # รวม O(E log V)
        _, cost, pos, path = heapq.heappop(frontier)
        if pos == goal:
            return path
        x, y = pos
        for nx, ny in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
            if 0 <= ny < len(grid) and 0 <= nx < len(grid[0]) and not grid[ny][nx] and (nx, ny) not in seen:
                seen.add((nx, ny))
                heapq.heappush(frontier, (cost + 1 + h((nx, ny)), cost + 1, (nx, ny), path + [(nx, ny)]))
    return None

# ตรวจสอบ
grid = [
    [False, False, False],
    [False, True,  False],
    [False, False, False],
]
path = astar(grid, (0, 0), (2, 2))
assert path[0] == (0, 0) and path[-1] == (2, 2)
assert (1, 1) not in path               # ไม่มีทางเดินผ่านไทล์กำแพง

A* คือ BFS จากขั้นที่ 4 ของระบบค้นหาเอกสาร แต่อัปเกรดด้วย priority queue และ heuristic เพื่อสำรวจไทล์ที่มีแนวโน้มดีก่อน — O(E log V) บนกราฟไทล์ แทนที่จะสำรวจทุกไทล์เท่า ๆ กัน

(คลิกไทล์เพื่อเพิ่มกำแพง แล้วรันการค้นหา — priority queue จะเลือกไทล์ที่ใกล้เป้าหมายก่อนอย่างเห็นได้ชัด ต่างจาก BFS ธรรมดาที่กระจายเท่า ๆ กันทุกทิศ)

เส้นทางเก็บไอเทม: DP บนกริด

def best_loot_path(loot_grid: list[list[int]]) -> int:
    """คะแนนไอเทมสูงสุดที่เก็บได้ เดินได้แค่ขวา/ลง จากมุมบนซ้ายไปมุมล่างขวา"""
    rows, cols = len(loot_grid), len(loot_grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = loot_grid[0][0]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue
            best = max(dp[r-1][c] if r > 0 else -1, dp[r][c-1] if c > 0 else -1)
            dp[r][c] = best + loot_grid[r][c]
    return dp[rows-1][cols-1]                          # O(rows · cols)

# ตรวจสอบ
loot = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
]
assert best_loot_path(loot) == 12   # เส้นทางที่ดีที่สุดเส้นหนึ่ง: 1 -> 3 -> 5 -> 2 -> 1

การลองทุกเส้นทางขวา/ลงแบบ brute force คือเลขชี้กำลัง (2^(rows+cols)) ส่วนตาราง DP ใช้ค่าดีที่สุดของแต่ละเซลล์ซ้ำเพียงครั้งเดียว ทั้งกริดจึงเติมเต็มใน O(rows · cols) — แนวคิด “แคชปัญหาย่อย” แบบเดียวกับตาราง DP ทุกตาราง

ลำดับเทิร์น: priority queue ตามความเร็ว

import heapq

class TurnQueue:
    """min-heap เรียงตามเวลาขยับถัดไป ตัวละครที่เร็วกว่าจะได้ขยับก่อน"""

    def __init__(self) -> None:
        self.heap: list[tuple[float, int, int]] = []   # (next_time, entity_id, speed)

    def schedule(self, entity_id: int, speed: int, now: float = 0.0) -> None:
        heapq.heappush(self.heap, (now + 100 / speed, entity_id, speed))  # O(log n)

    def next_turn(self) -> int:
        next_time, entity_id, speed = heapq.heappop(self.heap)           # O(log n)
        self.schedule(entity_id, speed, now=next_time)                   # จัดคิวใหม่
        return entity_id

# ตรวจสอบ
q = TurnQueue()
q.schedule(1, speed=10)   # ขยับประมาณทุก 10 ติ๊ก
q.schedule(2, speed=25)   # เร็วกว่ามาก -> ขยับเกือบทุก 4 ติ๊ก
assert q.next_turn() == 2   # ตัวละครที่เร็วกว่าขยับก่อน

แนวทางไร้เดียงสาแบบ “เรียงตัวละครทั้งหมดตามความเร็วทุกเทิร์น” มีต้นทุน O(n log n) ต่อเทิร์น ส่วน min-heap เก็บแค่ตัวที่ขยับถัดไปไว้บนสุด แล้วจัดคิวใหม่ใน O(log n) — ข้อแลกเปลี่ยนแบบ list กับ heap เดียวกับขั้นที่ 3 ของระบบค้นหาเอกสาร เพียงแต่ทำงานทุกเทิร์นแทนที่จะทำครั้งเดียวต่อการค้นหา

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

แบบฝึกหัด

1. จับคู่ระบบชน มอนสเตอร์ต้องตรวจว่ามอนสเตอร์ตัวไหนอยู่ในระยะประชิดทุกเฟรม โครงสร้างใดที่ทำให้การตรวจนี้ยังเร็วอยู่แม้ด่านจะเต็มไปด้วยมอนสเตอร์ และ Big-O เฉลี่ยของมันคือเท่าไร?

เฉลย

ตารางแฮชเชิงพื้นที่ (spatial hash) — dict ที่คีย์ด้วยเซลล์ของกริด แมปไปยังตัวละครที่อยู่ในเซลล์นั้น การค้นหาสแกนเฉพาะเซลล์ของตัวเองกับเซลล์ข้างเคียง จึงมีต้นทุนเฉลี่ย O(1) แทนที่จะสแกนตัวละครทุกตัวแบบไร้เดียงสาซึ่งเป็น O(n)

2. จับคู่ระบบกระเป๋าไอเทม ระบบกระเป๋าไอเทมของคุณเก็บตัวละครไว้ใน list ธรรมดา แล้วค้นหาด้วย for e in entities: if e.id == wanted: ... Big-O ของการค้นหาหนึ่งครั้งคือเท่าไร และแก้อย่างไรโดยไม่เปลี่ยนข้อมูลที่เก็บ?

เฉลย

O(n) ต่อการค้นหาหนึ่งครั้ง — สแกนทั้งลิสต์ในกรณีเลวร้ายสุด แก้โดยเปลี่ยนไปคีย์ด้วย dict ตามรหัสตัวละคร (entities[id] -> entity) แทนลิสต์ — ข้อมูลเดิมทุกอย่าง แต่การค้นหาลดเหลือเฉลี่ย O(1)

3. จับคู่ระบบลำดับเทิร์น — ยากขึ้น ระบบเทิร์นต้นแบบรัน entities.sort(key=lambda e: e.next_time) ทุกครั้งที่เริ่มเทิร์นใหม่ แล้วหยิบ entities[0] Big-O ต่อเทิร์นเทียบกับ min-heap ต่างกันอย่างไร และทำไมความต่างนี้ถึงสำคัญเมื่อมีตัวละครหลายร้อยตัวขยับหลายพันครั้งต่อการต่อสู้หนึ่งครั้ง?

เฉลย

การเรียงทั้งลิสต์ทุกเทิร์นมีต้นทุน O(n log n) ต่อเทิร์น — ตลอด t เทิร์นรวมเป็น O(t · n log n) ส่วน min-heap ใช้แค่ O(log n) ในการดึงตัวถัดไป และ O(log n) ในการจัดคิวใหม่ ตลอด t เทิร์นจึงรวมเป็น O(t log n) เท่านั้น ด้วยมอนสเตอร์ 300 ตัวและ 5,000 เทิร์นต่อการต่อสู้ นี่คือความต่างระหว่างประมาณ 12 ล้านครั้งกับ 2.7 ล้านครั้ง — และ heap ยังไม่ต้องแตะตัวละครอีก 299 ตัวในแต่ละเทิร์นเลยด้วยซ้ำ

4. ไล่ตาราง DP ของเส้นทางไอเทม — ยากที่สุด ให้กริดไอเทมขนาด 2×2 [[2, 3], [1, 4]] จงไล่ best_loot_path ด้วยมือ: เติมตาราง DP ทีละเซลล์ แล้วบอกคำตอบสุดท้ายพร้อมเส้นทางที่ให้คำตอบนั้น

เฉลย

dp[0][0] = 2, dp[0][1] = 2 + 3 = 5, dp[1][0] = 2 + 1 = 3, dp[1][1] = max(dp[0][1], dp[1][0]) + 4 = max(5, 3) + 4 = 9 คำตอบสุดท้ายคือ 9 ได้จากเส้นทาง 2 -> 3 -> 4 (ขวา แล้วลง)

โจทย์ท้าทาย

A. ต่อยอดโร้กไลก์ — มอนสเตอร์ที่หนี A* เดินเข้าหาไทล์เป้าหมายเสมอ แต่มอนสเตอร์ที่ตกใจกลัวควรเดิน ออกห่าง จากผู้เล่นแทน — เพิ่มระยะห่างให้มากที่สุด ไม่ใช่ลดให้น้อยที่สุด จะดัดแปลงระบบข้างบนอย่างไรให้มอนสเตอร์มีเส้นทาง “หนี” และต้องแลกด้วยต้นทุนเท่าไร?

แนวทาง

A* เองรู้จักแค่การค้นหาไปยังเป้าหมายจุดเดียวที่ตายตัว — มันค้นหา “ไทล์ที่ไกลที่สุด” โดยตรงไม่ได้ แทนที่ด้วยการรัน BFS/Dijkstra แบบจำกัดขอบเขตจากตำแหน่งผู้เล่นออกไปในรัศมี R (O(V + E) บนไทล์ที่เข้าถึงได้) แล้วเลือกไทล์ที่มีระยะห่างมากที่สุดที่มอนสเตอร์ไปถึงได้ จากนั้นส่งไทล์นั้นให้ astar() เป็นเป้าหมายเหมือนเดิมทุกประการ ต้นทุนรวมยังคงเป็นเพียงตัวคูณคงที่เล็ก ๆ ของการค้นหา A* ปกติหนึ่งครั้ง — เพียงแค่เลือกไทล์เป้าหมายที่ฉลาดกว่าก่อนเท่านั้น

B. ไล่จับและแก้คอขวด มอนสเตอร์ทุกตัวบนด่านคำนวณ astar() ไปยังไทล์ปัจจุบันของผู้เล่นใหม่ทุกเฟรม แม้ทั้งมอนสเตอร์และผู้เล่นจะไม่ได้ขยับเลย ด้วยมอนสเตอร์ 50 ตัวที่ 60 เฟรมต่อวินาที นั่นคือการค้นหา O(E log V) เต็มรูปแบบ 50 ครั้งต่อเฟรม ซึ่งกินงบเวลาต่อเฟรมไปเกือบทั้งหมด จะยืนยันว่านี่คือคอขวดจริงได้อย่างไร และจะแก้ไขอย่างไร?

แนวทาง

ยืนยันก่อน — อย่าเดาเอา: ครอบลูปอัปเดตต่อมอนสเตอร์ด้วย cProfile หรือจับเวลาด้วย time.perf_counter() แล้วดูว่าการเรียก astar() กินเวลาส่วนใหญ่ของเฟรมจริงหรือไม่ เมื่อยืนยันแล้ว ให้แคชเส้นทางล่าสุดของมอนสเตอร์แต่ละตัวไว้คู่กับไทล์ผู้เล่น ณ ตอนที่คำนวณ แล้วคำนวณใหม่เฉพาะเมื่อไทล์นั้นเปลี่ยนจริง:

path_cache: dict[int, tuple[tuple[int, int], list]] = {}

def get_path(monster_id: int, monster_pos, player_pos, grid) -> list:
    cached = path_cache.get(monster_id)
    if cached and cached[0] == player_pos:
        return cached[1]                      # ผู้เล่นไม่ได้ขยับ -> ใช้ของเดิมซ้ำ
    path = astar(grid, monster_pos, player_pos)
    path_cache[monster_id] = (player_pos, path)
    return path

วิธีนี้เปลี่ยน “50 ครั้งต่อเฟรม” ให้เหลือ “0 ครั้งในเฟรมส่วนใหญ่ และ 1 ครั้งต่อมอนสเตอร์เฉพาะตอนที่ผู้เล่นขยับเข้าไทล์ใหม่จริง ๆ” — สัญชาตญาณเดียวกับการแคชในขั้นที่ 1 ของระบบค้นหาเอกสาร: จ่ายต้นทุนแพงเฉพาะตอนที่อินพุตเปลี่ยนจริงเท่านั้น

เจาะลึกเพิ่มเติมและนิสัยที่ควรสร้าง

แหล่งเรียนคอร์สจริง:

• MIT 6.006 — Introduction to Algorithms (MIT OpenCourseWare) — บทเรียนวิดีโอและโจทย์ครบชุด ฟรี
• Harvard CS50 — Introduction to Computer Science (edX) — ปูพื้นฐานการคิดเชิงคำนวณและการแก้ปัญหา
• Stanford CS161 — Design and Analysis of Algorithms — เน้นการวิเคราะห์ความซับซ้อนและการพิสูจน์ความถูกต้อง

หนังสืออ่านต่อ — ชั้นหนังสือที่ควรมีติดโต๊ะ:

• CLRS (Cormen, Leiserson, Rivest, Stein), Introduction to Algorithms (4th ed.) — ตำราอ้างอิงมาตรฐานของวงการ ครอบคลุมทุกโครงสร้างและเทคนิคที่ใช้ในโครงงานนี้อย่างเข้มงวดและครบถ้วนที่สุด
• Skiena, The Algorithm Design Manual (3rd ed.) — ดีที่สุดสำหรับคำถาม “จะเลือกเทคนิคไหนเมื่อไร” พร้อมเรื่องเล่าจากงานจริง เหมาะกับการตัดสินใจเชิงระบบแบบที่โครงงานนี้ฝึกให้ทำ
• Sedgewick & Wayne, Algorithms (4th ed.) — เจาะลึกการอิมพลีเมนต์โครงสร้างข้อมูลและอัลกอริทึมเรียงลำดับอย่างเป็นรูปธรรม ต่อยอดขั้นที่ 2 และขั้นที่ 3 ได้ตรงจุดที่สุด
• Kleinberg & Tardos, Algorithm Design — แนวคิดการออกแบบอัลกอริทึมกราฟและ dynamic programming อย่างเป็นระบบ เหมาะกับการต่อยอดขั้นที่ 4 และโจทย์เปิดข้อ D
• Bhargava, Grokking Algorithms (2nd ed.) — ภาพประกอบเข้าใจง่าย เหมาะทบทวนพื้นฐานทั้งหมดอย่างรวดเร็วก่อนอ่านตำราที่เข้มงวดกว่า

นิสัยการใช้ AI โดยไม่สูญเสียทักษะ:

• คิดแผนก่อนเสมอ แล้วค่อยถาม AI — แตกปัญหา เลือกโครงสร้าง และประเมินความซับซ้อนด้วยตัวเองก่อน ใช้ AI ในขั้นลงมือเขียน ไม่ใช่ขั้นคิด
• ตรวจ Big-O ของทุกคำตอบที่ AI ให้ — อย่าเชื่อว่าโค้ดที่ “ทำงานได้” คือโค้ดที่ “เร็วพอ” จงไล่หาลูปซ้อนและ in บน list ที่ซ่อนอยู่ทุกครั้ง — ทั้งสี่ขั้นของโครงงานนี้พิสูจน์แล้วว่ารูปแบบนี้โผล่มาซ้ำ ๆ ไม่ว่าจะเป็นการค้นหา การแฮช การเรียง หรือกราฟ
• เขียนเอง ปิด AI เป็นระยะ — แก้โจทย์ด้วยมือเปล่าสัปดาห์ละครั้ง เพื่อรักษากล้ามเนื้อการแก้ปัญหาไว้ AI คือเครื่องขยายทักษะ ไม่ใช่ตัวแทนของมัน