近似算法¶

概述¶

近似算法用于NP难问题，在多项式时间内找到接近最优解的解，用近似比衡量解的质量。

近似比定义¶

对于最小化问题，近似比ρ满足：

Text Only
1	`C(ALG) ≤ ρ × C(OPT)`

对于最大化问题：

Text Only
1	`C(OPT) ≤ ρ × C(ALG)`

顶点覆盖（2-近似）¶

C
#define MAX_V 100

int vertexCover(int graph[MAX_V][MAX_V], int n, int cover[]) {
    int coverSize = 0;
    int covered[MAX_V][MAX_V];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            covered[i][j] = 0;
        }
    }
    
    for (int u = 0; u < n; u++) {
        for (int v = u + 1; v < n; v++) {
            if (graph[u][v] && !covered[u][v]) {
                cover[coverSize++] = u;
                cover[coverSize++] = v;
                
                for (int i = 0; i < n; i++) {
                    covered[u][i] = 1;
                    covered[i][u] = 1;
                    covered[v][i] = 1;
                    covered[i][v] = 1;
                }
            }
        }
    }
    
    return coverSize;
}

装包问题（FPTAS）¶

C
int knapsackApprox(int weights[], int values[], int n, int W, double epsilon) {
    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        if (values[i] > maxVal) maxVal = values[i];
    }
    
    int K = (int)(epsilon * maxVal / n);
    
    if (K == 0) K = 1;
    
    int *scaledValues = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scaledValues[i] = values[i] / K;
    }
    
    int totalValue = 0;
    for (int i = 0; i < n; i++) {
        totalValue += scaledValues[i];
    }
    
    int **dp = (int**)malloc(sizeof(int*) * (n + 1));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)malloc(sizeof(int) * (totalValue + 1));
        for (int j = 0; j <= totalValue; j++) {
            dp[i][j] = W + 1;
        }
    }
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= totalValue; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= scaledValues[i - 1]) {
                int prev = dp[i - 1][j - scaledValues[i - 1]] + weights[i - 1];
                if (prev < dp[i][j]) {
                    dp[i][j] = prev;
                }
            }
        }
    }
    
    int result = 0;
    for (int j = totalValue; j >= 0; j--) {
        if (dp[n][j] <= W) {
            result = j * K;
            break;
        }
    }
    
    for (int i = 0; i <= n; i++) free(dp[i]);
    free(dp);
    free(scaledValues);
    
    return result;
}

旅行商问题（2-近似）¶

C
typedef struct {
    int u, v, weight;
} Edge;

int parent[MAX_V];

int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

void unite(int x, int y) {
    parent[find(x)] = find(y);
}

int compareEdges(const void *a, const void *b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

int* mst(int graph[MAX_V][MAX_V], int n, int *mstSize) {
    Edge *edges = (Edge*)malloc(sizeof(Edge) * n * n);
    int edgeCount = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (graph[i][j] > 0) {
                edges[edgeCount++] = (Edge){i, j, graph[i][j]};
            }
        }
    }
    
    qsort(edges, edgeCount, sizeof(Edge), compareEdges);
    
    for (int i = 0; i < n; i++) parent[i] = i;
    
    int *mstEdges = (int*)malloc(sizeof(int) * 2 * n);
    *mstSize = 0;
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        
        if (find(u) != find(v)) {
            unite(u, v);
            mstEdges[(*mstSize)++] = u;
            mstEdges[(*mstSize)++] = v;
        }
    }
    
    free(edges);
    return mstEdges;
}

int* preorder(int graph[MAX_V][MAX_V], int n, int start, int *orderSize) {
    int *order = (int*)malloc(sizeof(int) * n);
    int *stack = (int*)malloc(sizeof(int) * n);
    int top = 0, visited[MAX_V] = {0};
    
    stack[top++] = start;
    *orderSize = 0;
    
    while (top > 0) {
        int u = stack[--top];
        
        if (!visited[u]) {
            visited[u] = 1;
            order[(*orderSize)++] = u;
            
            for (int v = n - 1; v >= 0; v--) {
                if (graph[u][v] && !visited[v]) {
                    stack[top++] = v;
                }
            }
        }
    }
    
    free(stack);
    return order;
}

int tspApprox(int graph[MAX_V][MAX_V], int n) {
    int mstSize;
    int *mstEdges = mst(graph, n, &mstSize);
    
    int mstGraph[MAX_V][MAX_V];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            mstGraph[i][j] = 0;
        }
    }
    
    for (int i = 0; i < mstSize; i += 2) {
        int u = mstEdges[i];
        int v = mstEdges[i + 1];
        mstGraph[u][v] = mstGraph[v][u] = 1;
    }
    
    int orderSize;
    int *order = preorder(mstGraph, n, 0, &orderSize);
    
    int totalCost = 0;
    for (int i = 0; i < orderSize - 1; i++) {
        totalCost += graph[order[i]][order[i + 1]];
    }
    totalCost += graph[order[orderSize - 1]][order[0]];
    
    free(mstEdges);
    free(order);
    
    return totalCost;
}

集合覆盖（ln n-近似）¶

C
int setCover(int universe[], int n, int sets[][MAX_V], int setSizes[], int m, int result[]) {
    int covered[MAX_V] = {0};
    int used[MAX_V] = {0};
    int resultSize = 0;
    int coveredCount = 0;
    
    while (coveredCount < n) {
        int bestSet = -1;
        int bestCount = 0;
        
        for (int i = 0; i < m; i++) {
            if (used[i]) continue;
            
            int count = 0;
            for (int j = 0; j < setSizes[i]; j++) {
                if (!covered[sets[i][j]]) {
                    count++;
                }
            }
            
            if (count > bestCount) {
                bestCount = count;
                bestSet = i;
            }
        }
        
        if (bestSet == -1 || bestCount == 0) break;
        
        used[bestSet] = 1;
        result[resultSize++] = bestSet;
        
        for (int j = 0; j < setSizes[bestSet]; j++) {
            if (!covered[sets[bestSet][j]]) {
                covered[sets[bestSet][j]] = 1;
                coveredCount++;
            }
        }
    }
    
    return resultSize;
}

负载均衡（2-近似）¶

C
void loadBalancing(int jobs[], int n, int m, int assignment[], int loads[]) {
    for (int i = 0; i < m; i++) loads[i] = 0;
    
    for (int i = 0; i < n; i++) {
        int minMachine = 0;
        for (int j = 1; j < m; j++) {
            if (loads[j] < loads[minMachine]) {
                minMachine = j;
            }
        }
        
        assignment[i] = minMachine;
        loads[minMachine] += jobs[i];
    }
}

常见近似算法¶

问题	近似比	算法
顶点覆盖	2	贪心匹配
集合覆盖	ln n	贪心覆盖
TSP(度量)	2	MST+遍历
TSP(度量)	1.5	Christofides
装包	1+ε (FPTAS)	缩放+DP
负载均衡	2	贪心分配

应用场景¶

NP难问题：无法精确求解
实时系统：时间受限
大数据：精确解代价高
工程实践：近似解足够好

参考资料¶

《算法导论》第35章
Vazirani 《近似算法》