近似與線上演算法完全指南 — 頂點覆蓋、集合覆蓋與秘書問題 | 資料結構與演算法

// ─── Vertex Cover 2-近似演算法（Matching-based）──────────────

function vertexCover2Approx(
  n: number,
  edges: [number, number][]
): number[] {
  const adj: Map<number, Set<number>> = new Map();
  for (let i = 0; i < n; i++) adj.set(i, new Set());
  for (const [u, v] of edges) {
    adj.get(u)!.add(v);
    adj.get(v)!.add(u);
  }

  const cover = new Set<number>();
  const matched = new Set<string>();

  for (const [u, v] of edges) {
    const key = `${Math.min(u, v)},${Math.max(u, v)}`;
    // 若這條邊的兩端都尚未在 cover 中
    if (!cover.has(u) && !cover.has(v)) {
      cover.add(u);
      cover.add(v);
      matched.add(key);
    }
  }

  return [...cover];
}

// 驗證：每條邊至少有一端在 cover 中
function validateCover(
  edges: [number, number][],
  cover: number[]
): boolean {
  const coverSet = new Set(cover);
  return edges.every(([u, v]) => coverSet.has(u) || coverSet.has(v));
}

// 測試
const edges: [number, number][] = [
  [0, 1], [0, 2], [1, 3], [2, 3], [3, 4]
];
const cover = vertexCover2Approx(5, edges);
console.log('Vertex Cover:', cover);
console.log('合法覆蓋?', validateCover(edges, cover));
console.log('大小:', cover.length);
// 輸出：大小最多是最優解的 2 倍

// ─── Set Cover 貪心近似——O(ln n) 近似比 ──────────────────────

function greedySetCover(
  universe: Set<number>,
  subsets: Map<string, Set<number>>
): string[] {
  const uncovered = new Set(universe);
  const selected: string[] = [];

  while (uncovered.size > 0) {
    // 選擇覆蓋最多未覆蓋元素的子集
    let bestKey = '';
    let bestCount = 0;

    for (const [key, subset] of subsets) {
      let count = 0;
      for (const elem of subset) {
        if (uncovered.has(elem)) count++;
      }
      if (count > bestCount) {
        bestCount = count;
        bestKey = key;
      }
    }

    if (bestCount === 0) break; // 無法覆蓋（子集不足）

    selected.push(bestKey);
    const chosen = subsets.get(bestKey)!;
    for (const elem of chosen) {
      uncovered.delete(elem);
    }
  }

  return selected;
}

// 測試
const universe = new Set([1, 2, 3, 4, 5, 6, 7]);
const subsets = new Map<string, Set<number>>([
  ['S1', new Set([1, 2, 3, 4, 5])],
  ['S2', new Set([1, 2, 6])],
  ['S3', new Set([3, 4, 7])],
  ['S4', new Set([5, 6, 7])],
]);

const result = greedySetCover(universe, subsets);
console.log('選中子集:', result);       // 輸出：['S1', 'S4']
console.log('數量:', result.length);    // 輸出：2

// ─── Metric TSP 2-近似（MST-based）─────────────────────────

// Prim's MST 建構
function primMST(dist: number[][]): [number, number][] {
  const n = dist.length;
  const inMST = new Array(n).fill(false);
  const key = new Array(n).fill(Infinity);
  const parent = new Array(n).fill(-1);
  key[0] = 0;

  for (let count = 0; count < n; count++) {
    // 找最小 key 的非 MST 頂點
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!inMST[v] && (u === -1 || key[v] < key[u])) u = v;
    }
    inMST[u] = true;

    for (let v = 0; v < n; v++) {
      if (!inMST[v] && dist[u][v] < key[v]) {
        key[v] = dist[u][v];
        parent[v] = u;
      }
    }
  }

  const edges: [number, number][] = [];
  for (let i = 1; i < n; i++) {
    edges.push([parent[i], i]);
  }
  return edges;
}

// DFS 前序遍歷 MST，跳過已訪問節點（Shortcut）
function tspApprox(dist: number[][]): {
  tour: number[];
  cost: number;
} {
  const n = dist.length;
  const mstEdges = primMST(dist);

  // 建鄰接表
  const adj: Map<number, number[]> = new Map();
  for (let i = 0; i < n; i++) adj.set(i, []);
  for (const [u, v] of mstEdges) {
    adj.get(u)!.push(v);
    adj.get(v)!.push(u);
  }

  // DFS 前序遍歷
  const visited = new Set<number>();
  const tour: number[] = [];

  function dfs(node: number): void {
    visited.add(node);
    tour.push(node);
    for (const neighbor of adj.get(node)!) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }

  dfs(0);
  tour.push(0); // 回到起點

  // 計算總成本
  let cost = 0;
  for (let i = 0; i < tour.length - 1; i++) {
    cost += dist[tour[i]][tour[i + 1]];
  }

  return { tour, cost };
}

// 測試：4 個城市，距離滿足三角不等式
const dist = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0],
];
const { tour, cost } = tspApprox(dist);
console.log('路線:', tour);   // 輸出：[0, 1, 3, 2, 0]（或其他合法路線）
console.log('成本:', cost);   // 近似成本 <= 2 × OPT

// ─── Secretary Problem：1/e 最優停止策略 ─────────────────────

function secretaryAlgorithm(candidates: number[]): {
  selected: number;
  index: number;
} {
  const n = candidates.length;
  const r = Math.max(1, Math.floor(n / Math.E)); // 觀察期 = n/e

  // 觀察期：記錄前 r 名中的最高分
  let bestInObservation = -Infinity;
  for (let i = 0; i < r; i++) {
    bestInObservation = Math.max(bestInObservation, candidates[i]);
  }

  // 選擇期：錄取第一個超過觀察期最高分的候選人
  for (let i = r; i < n; i++) {
    if (candidates[i] > bestInObservation) {
      return { selected: candidates[i], index: i };
    }
  }

  // 若無人超過，錄取最後一人
  return { selected: candidates[n - 1], index: n - 1 };
}

// Fisher-Yates Shuffle
function shuffle(arr: number[]): void {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

// 蒙地卡羅模擬驗證成功率
function simulateSecretary(
  n: number,
  trials: number
): number {
  let successes = 0;
  for (let t = 0; t < trials; t++) {
    // 生成 1~n 的隨機排列
    const candidates = Array.from({ length: n }, (_, i) => i + 1);
    shuffle(candidates);

    const best = n; // 最優候選人分數 = n
    const { selected } = secretaryAlgorithm(candidates);
    if (selected === best) successes++;
  }
  return successes / trials;
}

// 測試
const rate = simulateSecretary(100, 50000);
console.log(`成功率：${(rate * 100).toFixed(1)}%`);
// 輸出：成功率 ≈ 36.8%（理論值 = 1/e ≈ 0.368）

// ─── Online Paging 模擬——LRU vs FIFO ────────────────────────

class LRUCache {
  private cache: Map<number, number>; // key → 最後使用時間
  private capacity: number;
  private time: number = 0;
  misses: number = 0;

  constructor(k: number) {
    this.capacity = k;
    this.cache = new Map();
  }

  access(page: number): boolean {
    this.time++;
    if (this.cache.has(page)) {
      this.cache.set(page, this.time); // 更新使用時間
      return true; // hit
    }

    this.misses++;
    if (this.cache.size >= this.capacity) {
      // 置換最久未使用的頁面
      let lruPage = -1;
      let lruTime = Infinity;
      for (const [p, t] of this.cache) {
        if (t < lruTime) {
          lruTime = t;
          lruPage = p;
        }
      }
      this.cache.delete(lruPage);
    }
    this.cache.set(page, this.time);
    return false; // miss
  }
}

class FIFOCache {
  private queue: number[] = [];
  private inCache: Set<number> = new Set();
  private capacity: number;
  misses: number = 0;

  constructor(k: number) {
    this.capacity = k;
  }

  access(page: number): boolean {
    if (this.inCache.has(page)) return true; // hit

    this.misses++;
    if (this.queue.length >= this.capacity) {
      const evicted = this.queue.shift()!;
      this.inCache.delete(evicted);
    }
    this.queue.push(page);
    this.inCache.add(page);
    return false; // miss
  }
}

// Belady 最優離線演算法（知道未來全部請求）
function beladyOPT(
  requests: number[],
  k: number
): number {
  const cache = new Set<number>();
  let misses = 0;

  for (let i = 0; i < requests.length; i++) {
    if (cache.has(requests[i])) continue;

    misses++;
    if (cache.size >= k) {
      // 置換未來最遠才用到的頁面
      let farthest = -1;
      let evictPage = -1;
      for (const page of cache) {
        let nextUse = Infinity;
        for (let j = i + 1; j < requests.length; j++) {
          if (requests[j] === page) { nextUse = j; break; }
        }
        if (nextUse > farthest) {
          farthest = nextUse;
          evictPage = page;
        }
      }
      cache.delete(evictPage);
    }
    cache.add(requests[i]);
  }
  return misses;
}

// 測試比較
const requests = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];
const k = 3;

const lru = new LRUCache(k);
const fifo = new FIFOCache(k);
for (const r of requests) { lru.access(r); fifo.access(r); }
const optMisses = beladyOPT(requests, k);

console.log(`LRU  misses: ${lru.misses}`);   // 線上演算法
console.log(`FIFO misses: ${fifo.misses}`);   // 線上演算法
console.log(`OPT  misses: ${optMisses}`);     // 離線最優
console.log(`LRU 競爭比: ${(lru.misses / optMisses).toFixed(2)}`);
// 理論競爭比上界 = k = 3

// ─── Greedy Load Balancing（List Scheduling）────────────────

function greedyLoadBalance(
  jobs: number[],
  m: number
): { assignment: number[][]; makespan: number } {
  const machines: number[][] = Array.from({ length: m }, () => []);
  const loads = new Array(m).fill(0);

  for (const job of jobs) {
    // 找負載最小的機器
    let minIdx = 0;
    for (let i = 1; i < m; i++) {
      if (loads[i] < loads[minIdx]) minIdx = i;
    }
    machines[minIdx].push(job);
    loads[minIdx] += job;
  }

  const makespan = Math.max(...loads);
  return { assignment: machines, makespan };
}

// LPT（Longest Processing Time First）——改進版
function lptLoadBalance(
  jobs: number[],
  m: number
): { assignment: number[][]; makespan: number } {
  // 先將工作按時間降序排列
  const sorted = [...jobs].sort((a, b) => b - a);
  return greedyLoadBalance(sorted, m);
}

// 測試
const jobs = [6, 3, 8, 2, 7, 4, 5, 1];
const m = 3;

const greedy = greedyLoadBalance(jobs, m);
const lpt = lptLoadBalance(jobs, m);

console.log('Greedy makespan:', greedy.makespan);
console.log('LPT makespan:', lpt.makespan);
// LPT 的近似比 = 4/3 - 1/(3m)，比純貪心的 2 - 1/m 更好

#include <bits/stdc++.h>
using namespace std;

// ─── Vertex Cover 2-近似 ────────────────────────────────────

vector<int> vertexCover2Approx(int n, vector<pair<int,int>>& edges) {
    set<int> cover;

    for (auto& [u, v] : edges) {
        // 若兩端都不在 cover 中，將兩端都加入
        if (cover.find(u) == cover.end() &&
            cover.find(v) == cover.end()) {
            cover.insert(u);
            cover.insert(v);
        }
    }
    return vector<int>(cover.begin(), cover.end());
}

// ─── Set Cover 貪心近似 ─────────────────────────────────────

vector<int> greedySetCover(
    int n,
    vector<vector<int>>& subsets
) {
    set<int> uncovered;
    for (int i = 0; i < n; i++) uncovered.insert(i);

    vector<int> selected;
    vector<bool> used(subsets.size(), false);

    while (!uncovered.empty()) {
        int bestIdx = -1, bestCount = 0;

        for (int i = 0; i < (int)subsets.size(); i++) {
            if (used[i]) continue;
            int count = 0;
            for (int elem : subsets[i]) {
                if (uncovered.count(elem)) count++;
            }
            if (count > bestCount) {
                bestCount = count;
                bestIdx = i;
            }
        }

        if (bestIdx == -1) break;

        selected.push_back(bestIdx);
        used[bestIdx] = true;
        for (int elem : subsets[bestIdx]) {
            uncovered.erase(elem);
        }
    }
    return selected;
}

int main() {
    // Vertex Cover 測試
    vector<pair<int,int>> edges = {{0,1},{0,2},{1,3},{2,3},{3,4}};
    auto cover = vertexCover2Approx(5, edges);
    cout << "Vertex Cover: ";
    for (int v : cover) cout << v << " ";
    cout << "\n大小: " << cover.size() << "\n";

    // Set Cover 測試
    // 全集 = {0,1,2,3,4,5,6}
    vector<vector<int>> subsets = {
        {0, 1, 2, 3, 4},  // S0
        {0, 1, 5},         // S1
        {2, 3, 6},         // S2
        {4, 5, 6},         // S3
    };
    auto selected = greedySetCover(7, subsets);
    cout << "Set Cover 選中: ";
    for (int idx : selected) cout << "S" << idx << " ";
    cout << "\n數量: " << selected.size() << "\n";

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

// ─── Secretary Problem 模擬 ─────────────────────────────────

int secretaryAlgorithm(vector<int>& candidates) {
    int n = candidates.size();
    int r = max(1, (int)floor(n / M_E)); // 觀察期 = n/e

    int bestInObs = *max_element(
        candidates.begin(), candidates.begin() + r
    );

    for (int i = r; i < n; i++) {
        if (candidates[i] > bestInObs) {
            return candidates[i];
        }
    }
    return candidates[n - 1];
}

double simulateSecretary(int n, int trials) {
    mt19937 rng(random_device{}());
    int successes = 0;

    for (int t = 0; t < trials; t++) {
        vector<int> candidates(n);
        iota(candidates.begin(), candidates.end(), 1); // 1~n
        shuffle(candidates.begin(), candidates.end(), rng);

        if (secretaryAlgorithm(candidates) == n) {
            successes++;
        }
    }
    return (double)successes / trials;
}

// ─── LRU Cache（使用 list + unordered_map）─────────────────

class LRUCache {
    int capacity;
    list<int> order; // 前端 = 最近使用
    unordered_map<int, list<int>::iterator> cache;

public:
    int misses = 0;

    LRUCache(int k) : capacity(k) {}

    bool access(int page) {
        auto it = cache.find(page);
        if (it != cache.end()) {
            order.erase(it->second);
            order.push_front(page);
            cache[page] = order.begin();
            return true; // hit
        }

        misses++;
        if ((int)cache.size() >= capacity) {
            int evict = order.back();
            order.pop_back();
            cache.erase(evict);
        }
        order.push_front(page);
        cache[page] = order.begin();
        return false; // miss
    }
};

int main() {
    // Secretary Problem
    double rate = simulateSecretary(100, 50000);
    printf("成功率: %.1f%% (理論值 ≈ 36.8%%)\n", rate * 100);

    // LRU Paging
    vector<int> requests = {1,2,3,4,1,2,5,1,2,3,4,5};
    LRUCache lru(3);
    for (int r : requests) lru.access(r);
    cout << "LRU misses: " << lru.misses << "\n";

    return 0;
}

// ─── LeetCode 1199：Huffman-style 貪心 ──────────────────────

function minBuildTime(blocks: number[], split: number): number {
  // 最小堆
  const heap = new MinHeap();
  for (const b of blocks) heap.push(b);

  while (heap.size() > 1) {
    heap.pop(); // 較小值（被合併掉）
    const second = heap.pop()!;
    heap.push(second + split); // 合併後加上 split 時間
  }

  return heap.pop()!;
}

// 簡易最小堆實作
class MinHeap {
  private data: number[] = [];
  size(): number { return this.data.length; }
  push(val: number): void {
    this.data.push(val);
    this.bubbleUp(this.data.length - 1);
  }
  pop(): number | undefined {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = last;
      this.sinkDown(0);
    }
    return top;
  }
  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[parent] <= this.data[i]) break;
      [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
      i = parent;
    }
  }
  private sinkDown(i: number): void {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.data[l] < this.data[smallest]) smallest = l;
      if (r < n && this.data[r] < this.data[smallest]) smallest = r;
      if (smallest === i) break;
      [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
      i = smallest;
    }
  }
}

// 測試
console.log(minBuildTime([1, 2], 5));       // 輸出：7
console.log(minBuildTime([1, 2, 3], 1));    // 輸出：4

// ─── LeetCode 1515：Weiszfeld 迭代近似 ──────────────────────

function getMinDistSum(positions: number[][]): number {
  let cx = 0, cy = 0;
  for (const [x, y] of positions) { cx += x; cy += y; }
  cx /= positions.length;
  cy /= positions.length;

  for (let iter = 0; iter < 1000; iter++) {
    let nx = 0, ny = 0, wSum = 0;
    for (const [x, y] of positions) {
      const d = Math.sqrt((cx - x) ** 2 + (cy - y) ** 2);
      if (d < 1e-10) continue;
      const w = 1 / d;
      nx += w * x;
      ny += w * y;
      wSum += w;
    }
    if (wSum === 0) break;
    cx = nx / wSum;
    cy = ny / wSum;
  }

  let total = 0;
  for (const [x, y] of positions) {
    total += Math.sqrt((cx - x) ** 2 + (cy - y) ** 2);
  }
  return total;
}

// 測試
console.log(getMinDistSum([[0,1],[1,0],[1,2],[2,1]]).toFixed(4));
// 輸出：4.0000

// ─── LeetCode 1235：DP + 二分搜索 ───────────────────────────

function jobScheduling(
  startTime: number[],
  endTime: number[],
  profit: number[]
): number {
  const n = startTime.length;
  const jobs = Array.from({ length: n }, (_, i) => ({
    start: startTime[i],
    end: endTime[i],
    profit: profit[i],
  }));

  // 依結束時間排序
  jobs.sort((a, b) => a.end - b.end);

  // dp[i] = 考慮前 i 個工作的最大利潤
  const dp = new Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    // 不選第 i 個工作
    dp[i] = dp[i - 1];

    // 選第 i 個工作：二分找最後一個結束時間 <= start 的工作
    const job = jobs[i - 1];
    let lo = 0, hi = i - 1;
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (jobs[mid - 1]?.end <= job.start) lo = mid;
      else hi = mid - 1;
    }
    dp[i] = Math.max(dp[i], dp[lo] + job.profit);
  }

  return dp[n];
}

// 測試
console.log(jobScheduling(
  [1, 2, 3, 3], [3, 4, 5, 6], [50, 10, 40, 70]
)); // 輸出：120