dynamicprogramming.c

它建立在最优原则的基础上,采用动态规划方法,可以优雅而高效地解决许多用贪心技术或分治技术无法解决的问题。因此,动态规划技术越来越成为解决许多重要的应用问题的关键技术。矩阵连乘。

/**
 * File    : DynamicProgramming.c
 * Author  : Wind
 * Email   : [e-mail]
 * Date    : 2005-9-29
 * Purpose : Dynamic Programming practise
 * */
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

#include "../head/Global.h"
#include "../head/DynamicProgramming.h"

/**
 * @describ Calculate the multiply orders of matrixs.
 * @param (Matrix matrixs[])      The matrixs to be calculate.
 * @param (int miniMultTable[])   The integer array to store the minimun multiply times. 
 *                                eg: minimultTalb[i,j] store the minimun multiply times of matrixs 
 *                                that start from matrix[i] to matrix[j].
 * @param (int bestBrokenTable[]) The integer array to store the best best broken positions.
 *                                eg: bestBrokenTable[i,j] presents the best broken position of the matrixs multiply
 *                                that start from matrix[i] to matrix[j].
 * @param (int matrixNum)         The length of matrixs[]
 * @param (int m)                 The Chain order start position.
 * @param (int n)                 The Chain order end position.
 * @return                        The minimun multiply times of matrixs that start from matrix[m] to matrix[n]. 
 * */
int matrixChainOrder(Matrix matrixs [],int miniMultTable [] , int bestBrokenTable [],int matrixNum,int m,int n ){
    if(n==m){
        return 0;
    }
    if(miniMultTable[m*matrixNum+n]!=-1){
//        printf("Skip calculation m=%d , n= %d . \n",m,n);
        return miniMultTable[m*matrixNum+n];
    }
    
    int min=INT16_MAX;
    int i=0;
    int temp=0;
    for (i = m; i < n; ++i) {   
        temp= matrixChainOrder(matrixs,miniMultTable,bestBrokenTable,matrixNum,m,i)
            + matrixChainOrder(matrixs,miniMultTable,bestBrokenTable,matrixNum,i+1,n)
            + matrixs[m].row*matrixs[i].col*matrixs[n].col;
        if(temp<min){
            min = temp;
            miniMultTable[n+matrixNum*m]  = min;
            bestBrokenTable[n+matrixNum*m] = i;
        }
    }
    return min;
}


/**
 * @describ Multiply the matrixs starts from in the best order depending on the best broken table. 
 * @param (int bestBrokenTable [])  Integer array that stores the best broken positions.
 * @param (int tableLength)         Length of bestBrokenTable [].
 * @param (int tbColLength)         Coloumn length of bestBrokenTable [].
 * @param (int m)                   Multiply start position.
 * @param (int n)                   Multiply end position.
 * @param (char * order)            String that to store and presents the multiply orders.
 * @return                          String that that presents the multiply orders.
 * */
char * matrixChainMultiply(int bestBrokenTable [],int tableLength,int tbColLength,int m, int n,char * order){
    if(m > n||m < 0){
        MessageLine("Irregular m , n at -- char * matrixChainMultiply(int bestBrokenTable [],int tableLength,int tbColLength,int m, int n,char * order);");
        return order;
    }
    int token=bestBrokenTable[m*tbColLength+n];
    if(m==n){
        char s[]="M";
        char temp[5];
        itoa(m,temp,10);
        strcat(s,temp);
        strcat(order,s);
        return order;
    }
    strcat(order,"(");
    matrixChainMultiply(bestBrokenTable,tableLength,tbColLength , m,token,order);
    strcat(order,",");
    matrixChainMultiply(bestBrokenTable,tableLength,tbColLength ,token+1,n,order);
    strcat(order,")");
    return order;
}