Chi phí tối thiểu Tam giác đa giác

Khi các đường chéo không giao nhau tạo thành một tam giác trong một đa giác, nó được gọi là tam giác. Nhiệm vụ của chúng tôi là tìm một chi phí tối thiểu của phép tam giác.

Chi phí của tam giác là tổng trọng lượng của các tam giác thành phần của nó. Chúng ta có thể tìm trọng lượng của mỗi tam giác bằng cách cộng các cạnh của chúng, hay nói cách khác, trọng lượng là chu vi của tam giác.

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

Input:
The points of a polygon. {(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)}
Output:
The total cost of the triangulation. Here the cost of the triangulation is 15.3006.

Thuật toán

minCost(polygon, n)

Ở đây cost () sẽ được sử dụng để tính chu vi của một hình tam giác.

Đầu vào: Tập hợp các điểm để tạo một đa giác và một số điểm.

Đầu ra - Chi phí tối thiểu để tính tam giác của một đa giác.

Begin
   if n < 3, then
      return 0
   define table or order n x n
   i := 0

   for gap := 0 to n-1, do
      for j := gap to n-1, do
      if j < i+2, then
         table[i,j] := 0
      else
         table[i, j] = ∞
         for k := i+1 to j-1, do
            val := table[i, k] + table[k, j] + cost(i, j, k)
            if table[i, j] > val
               table[i, j] := val
      i := i + 1
      done
   done
   return table[0, n-1]
End

Ví dụ

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

struct Point {
   int x, y;
};

double min(double x, double y) {
   return (x <= y)? x : y;
}

double dist(Point p1, Point p2) {    //find distance from p1 to p2
   return sqrt(pow((p1.x-p2.x),2) + pow((p1.y-p2.y),2));
}

double cost(Point triangle[], int i, int j, int k) {
   Point p1 = triangle[i], p2 = triangle[j], p3 = triangle[k];
   return dist(p1, p2) + dist(p2, p3) + dist(p3, p1);    //the perimeter of the triangle
}

double minimumCost(Point polygon[], int n) {
   if (n < 3)    //when polygon has less than 3 points
      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;    //update table data to minimum value
            }
         }
      }
   }  
   return  table[0][n-1];
}

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

Đầu ra

The minimumcost: 15.3006