Tam giác phân đa giác chi phí tối thiểu

Cho đa giác lồi với các đỉnh cho trước. Phân chia đa giác thành các tam giác bằng đường chéo không cắt nhau (triangulation). Chi phí của một tam giác là chu vi của nó. Tìm cách phân chia có tổng chi phí tối thiểu.

Đầu vào và Đầu ra

Đầu vào: Đa giác 5 đỉnh: (0,0), (1,0), (2,1), (1,2), (0,2)
Đầu ra: Minimum cost = 15.3006

Thuật toán (Quy hoạch động)

Giống bài toán nhân chuỗi ma trận. table[i][j] = chi phí tối thiểu phân tam giác đa giác con từ đỉnh i đến j.

• Nếu j < i+2 (dưới 3 đỉnh) → table[i][j] = 0.
• Khác: table[i][j] = min_{k=i+1}^{j-1} (table[i][k] + table[k][j] + cost(i,j,k)), trong đó cost(i,j,k) là chu vi tam giác (i,j,k).
• Duyệt theo độ dài khoảng cách (gap) tăng dần.

Độ phức tạp: O(n³).

Ví dụ C++

#include <iostream>
#include <cmath>
#include <iomanip>
#define MAX 1000000.0
using namespace std;

struct Point { int x, y; };

double dist(Point p1, Point p2) {
    return sqrt(pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2));
}
double cost(Point t[], int i, int j, int k) {
    return dist(t[i],t[j]) + dist(t[j],t[k]) + dist(t[k],t[i]);
}

double minimumCost(Point polygon[], int n) {
    if (n < 3) return 0;
    double table[n][n];
    for (int gap=0; gap<n; gap++) {
        for (int i=0, j=gap; j<n; i++, j++) {
            if (j < i+2) table[i][j] = 0.0;
            else {
                table[i][j] = MAX;
                for (int k=i+1; k<j; k++) {
                    double val = table[i][k] + table[k][j] + cost(polygon,i,j,k);
                    if (table[i][j] > val) table[i][j] = val;
                }
            }
        }
    }
    return table[0][n-1];
}

int main() {
    Point points[] = {{0,0},{1,0},{2,1},{1,2},{0,2}};
    cout << "The minimum cost: " << minimumCost(points, 5);
}

Kết quả

The minimum cost: 15.3006