คู่มือโอลิมปิกคอมพิวเตอร์

Search

หลักการ

Search คือการลองสำรวจสถานะหรือคำตอบที่เป็นไปได้ทั้งหมดภายใต้เงื่อนไขของโจทย์ เทคนิคนี้เป็นพื้นฐานของ brute force, backtracking, graph traversal และ optimization หลายแบบ

ข้อดีคือคิดตรงไปตรงมาและใช้ตรวจคำตอบของวิธีที่ซับซ้อนได้ ข้อเสียคือ state space มักโตเร็วมาก จึงต้องวิเคราะห์จำนวนสถานะก่อนเขียนจริง

Motivation problem

สมมติมีตัวเลข n ตัว และต้องเลือกบางตัวให้ผลรวมเท่ากับ x วิธี brute force คือพิจารณาทุก subset

for (int mask = 0; mask < (1 << n); mask++) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    if (mask & (1 << i)) sum += a[i];
  }
  if (sum == x) {
    cout << "found";
  }
}

จำนวน subset คือ 2ⁿ ดังนั้นวิธีนี้เหมาะกับ n ≤ 20

Generating Permutations

เขียน recursive function เพื่อ generate ทุก permutation ที่เป็นไปได้

vector<int> p;
vector<bool> used(n);

void gen() {
  if ((int)p.size() == n) {
    // process permutation
    return;
  }
  for (int i = 0; i < n; i++) {
    if (used[i]) continue;
    used[i] = true;
    p.push_back(i);
    gen();
    p.pop_back();
    used[i] = false;
  }
}

จำนวน permutation คือ n! จึงใช้ได้เฉพาะ n เล็กมาก

Graph Traversal

VisuAlgo interactive visualizationvisualgo.net

• BFS ใช้ queue และสำรวจตามระยะทางจากจุดเริ่มต้น เหมาะกับ shortest path ในกราฟไม่มีน้ำหนัก

• DFS ใช้ recursion หรือ stack เหมาะกับ connectivity, cycle detection และ topological sort

  • preorder: ทำงานกับ node ก่อนเข้าลูก

  • inorder: ใช้กับ binary tree

  • postorder: ทำงานกับ node หลังออกจากลูก

• Topological Sort

ตัวอย่าง BFS

queue<int> q;
vector<int> dist(n, -1);

dist[start] = 0;
q.push(start);

while (!q.empty()) {
  int u = q.front();
  q.pop();
  for (int v : adj[u]) {
    if (dist[v] != -1) continue;
    dist[v] = dist[u] + 1;
    q.push(v);
  }
}

Binary Search Tree

VisuAlgo interactive visualizationvisualgo.net

• create

• search(v)

• insert(v)

• remove(v)

Meet in the middle

• เป็นเทคนิคที่ถ้า search จากต้นทางแล้ว space ใหญ่เกินไป ให้ search จากปลายทางแล้วมาเจอกันตรงกลาง

ตัวอย่างเช่น subset sum ที่ n = 40 ถ้าลองทุก subset จะเป็น 2⁴⁰ ซึ่งมากเกินไป แต่ถ้าแบ่ง array เป็นสองครึ่ง จะได้สองชุดขนาด 2²⁰ แล้วนำผลรวมของสองฝั่งมาจับคู่กัน

ขั้นตอนทั่วไป

• แบ่งข้อมูลเป็นสองส่วน

• generate คำตอบย่อยของแต่ละส่วน

• sort หรือใช้ hash เพื่อหาคู่ที่รวมกันเป็นคำตอบ

การเลือกเทคนิค

ข้อควรระวัง

• ต้องกำหนด state ให้ชัดว่าอะไรคือข้อมูลที่จำเป็นต่อการตัดสินใจต่อไป

• อย่าลืม mark visited ใน graph search ไม่เช่นนั้นอาจวนไม่จบ

• ถ้าใช้ recursion ลึกมาก อาจ stack overflow ได้

• วิเคราะห์จำนวนสถานะก่อนเสมอ เพราะ search ที่ถูกต้องแต่ช้าเกินไปจะไม่ผ่านเวลา