Полигонның литкодты шешімінің минималды баллдық триангуляциясы


Күрделілік дәрежесі орта
Жиі кіреді қиятын
Динамикалық бағдарламалау

Проблеманы шешу

Мәселеде »Минималды ұпай Триангуляция of Polygon”Бізде массивтің әрбір элементі сағат тілінің бағытымен таңбаланған кезде N қырлы көпбұрыштың мәнін көрсететін мән массиві берілген.

Біздің міндетіміз - көпбұрышты N-2 үшбұрышына үшбұрыштау. Үшбұрышты үшбұрышқа теңестіру оның үш төбесінде орналасқан мәндердің көбейтіндісі болып табылады. Көпбұрышты үшбұрышқа қосудың жалпы мәні барлық үшбұрыштың барлық ұпайларының қосындысына тең.

Біз көпбұрыштың триангуляциясының минималды балын табуымыз керек.

мысал

values = [1,3,1,4,1,5]
13

Түсіндіру:  Біз көпбұрышты үшбұрышқа келтіргенде триангуляция үшін минималды ұпай аламыз:

1 * 1 * 3 + 1 * 1 * 4 + 1 * 1 * 5 + 1 * 1 * 1 = 13

Полигондық леткодты ерітіндінің минималды баллдық триангуляциясының тәсілі

Біз көпбұрышты N-2 үшбұрышына және үшбұрыштарына үшбұрыш салу керек екенін ескере отырып, бір-бірімен қабаттаспау керек. Көпбұрыштың кез-келген шеті ең көп дегенде үшбұрыштың бөлігі бола алады, өйткені қабаттасуға жол берілмейді.

Сонымен, көпбұрыштың әр шеті N-2 шыңдары қалған үшбұрышты құра алады. Төмендегі суретке қараңыз.

Полигонның литкодты шешімінің минималды баллдық триангуляциясы

 

Көпбұрыштан үшбұрыш кескен кезде бізге жаңа кіші көпбұрыш қалады. Бұл бізді проблеманы кіші проблемаларға бөлуге болатындығына әкелді.

Полигонның литкодты шешімінің минималды баллдық триангуляциясы

 

Сонымен, егер біз 0-6 шыңы бар көпбұрыш үшін минималды балл алғымыз келсе, онда жаңа ішкі проблема 0-3 және 3-6 шыңдары бар көпбұрыш үшін минималды балл болып табылады.

демек, рекурсивті қатынас:

minScore (pos1, pos2) = minScore (pos1, i, A) + minScore (i, pos2, A) + A [pos1] * A [pos2] * A [i]

Сол ішкі проблеманың қайта есептелуін жеңу үшін біз жаттау кестесін қолданамыз. Бұл i, j мәндері i-ден j-ге дейінгі төбелермен көпбұрыштың минималды баллдық триангуляциясын сақтайтын * n жиым болады.

Іске асыру

Көпбұрыштың минималды триангуляциясы үшін C ++ коды

#include <bits/stdc++.h> 
using namespace std; 
  int memo[51][51];
  
  int dp(int pos1,int pos2, vector<int>&A){
    if(pos2-pos1<=1)return 0;
    
    if(memo[pos1][pos2]!=-1)return memo[pos1][pos2];
    int ans=INT_MAX;
    for(int i=pos1+1;i<pos2;i++)
      ans=min(ans, dp(pos1,i,A) + dp(i,pos2,A) + A[pos1]*A[pos2]*A[i] );
    memo[pos1][pos2]=ans;
    return ans;
  }
  
  int minScoreTriangulation(vector<int>& A) {
    memset(memo,-1,sizeof(memo));
    return dp(0,A.size()-1,A);
  }
int main() 
{ 
 vector<int> arr = {1,3,1,4,1,5}; 
 cout<<minScoreTriangulation(arr)<<endl; 
 return 0;
}
13

Көпбұрыштың минималды үшбұрышына арналған Java коды

import java.util.Arrays; 
public class Tutorialcup {
    public static int minScoreTriangulation(int[] A) {
     return dp(A, 0, A.length - 1, new Integer[A.length][A.length]);
    }
    public static int dp(int[] A, int pos1,int pos2, Integer[][] memo){
    if(pos2-pos1<=1)return 0;
    
    if(memo[pos1][pos2] != null)return memo[pos1][pos2];
    int ans=Integer.MAX_VALUE;
    for(int i=pos1+1;i<pos2;i++)
      ans=Math.min(ans, dp(A,pos1,i,memo) + dp(A,i,pos2,memo) + A[pos1]*A[pos2]*A[i] );
    memo[pos1][pos2]=ans;
    return ans;
  }
  public static void main(String[] args) {
    int [] arr = {1,3,1,4,1,5}; 
    int ans= minScoreTriangulation(arr);
    System.out.println(ans);
  }
}
13

Полигондық леткод ерітіндісінің минималды баллдық триангуляциясының күрделілігін талдау

Уақыт күрделілігі

Жоғарыда келтірілген кодтың уақыт күрделілігі O (n * n * n) өйткені біз үшбұрыштың триангуляциясы үшін минималды балл беретін 3 түрлі i, j, k мәндері үшін массивті өтіп жатырмыз. Мұнда n - мән массивінің ұзындығы.

Ғарыштың күрделілігі

Жоғарыда аталған кодтың кеңістігінің күрделілігі мынада O (n * n) өйткені есте сақтау үшін n * n қосымша орынды пайдалану.

Әдебиеттер тізімі