ダイナミックプログラミング

質問

「３個以上の行列の積を計算する時、行列の要素に対する掛け算の回数を最小にする」問題をDP法によって解く。

入力：五つの行列A1[r0,r1]、A2[r1,r2]、A3[r2,r3]、A4[r3,r4]、A5[r4,r5]の次数を自然数r0,r1,r2,r3,r4,r5として入力。

出力：M(i,j)の値をiからｊまでの幅毎に幅の小さい順に出力。

というC言語の課題が出たのですがわかりません。

行列はデータを縦横長方形に並べた物で、横の並びを行、縦の並びを列と呼ぶ。行の数ｈ、列の数ｋの行列AをA［h、k］と表し、ｈ、ｋを行列Aの次数という。行列A1[h、k]と行列A2[ｍ、ｎ]の積はｋ＝ｍの時、定義されていて、行列A1[h、k]と行列A2[k、n]の積はｈ行、ｎ列の行列 B[h、ｎ]となる。

行列Bのi行目のj列目（ｊ番目）のデータは：行列A1[h、k]のi行目と行列A2[k、n]のｊ列目を順に、掛けて加算したものとなる。例えば、

A1[3、2]＝ a b A2[2、4]= G H P Q
c d R S T U
e f
の積行列B[3、4]＝ aG+bR aH+bS aP+bT aQ+bU
cG+dR cH+dS cP+dT cQ+dU
eG+fR eH+fS eP+fT eQ+fU

となります。行列A1[3、2]と行列A2[2、4]の積行列B[3、4]を計算するのに掛け算が３×２×４（２×３×４）回要ります。一般に行列 A1[r0、r1]　と行列A2[r1、r2]の積行列を計算するのにr0・r1・r2回掛け算が要ります。行列の積行列を求める演算を“×”で表すと、行列A1[r0、r1]、行列A2[r1、r2]、と行列A3[r2、r3]において、

（A1[r0,r1]×A2[r1,r2]）×A3[r2,r3]＝A1[r0.r1]×（A2[r1,r2]×A3[r2,r3]）
＝A1[r0,r1]×A2[r1,r2]×A3[r2,r3]

が成り立ちます。即ち、行列の積行列を求める順番はどの順番で求めても結果は同じになる。

例えば、行列A1[10,20]、行列A2[20,50]、行列A3[50,1]、行列A4[1,100]の四つの行列の積行列を求める時、

B[10,100]＝A1[10,20]×（A2[20,50]×（A3[50,1]×A4[1,100]）） ・・・(1)
＝（A1[10,20]×（A2[20,50]×A3[50,1]））×A4[1,100] ・・・(2)

が成り立ちます。ところが、(1)の順に計算すると掛け算は１２５，０００回要ります、(2)の順だと２，２００回の掛け算が要ります。このように、沢山の行列の積を求める時には、積を求める順番を工夫する事が大切です。行列Aiの積行列A1[r0,r1]×A2[r1,r2]×・・×Ai[ri-1,ri]×・・×Ak[rk-1,rk]×・・×Aj[rj-1,rj]×・・×An[rn-1,rn]を求める時、最小の掛け算の数をDP法で求める。

M(i,j)を行列の積Ai[ri-1,ri]×・・×Ak[rk-1,rk]×Ak+1[rk.rk+1]×・・×Aj[rj-1,rj]を求めるのに必要な掛け算の最小数とする。行列Aiから行列Ajまでの行列積を求める時、（Ai[ri-1,ri]×・・×Ak[rk- 1,rk]）×（Ak+1[rk.rk+1]×・・×Aj[rj-1,rj]）のように一番最後に実行する行列の積を求める演算をi<=k

M(i,j)= 0 i=jの時
= MIN {M(i,k)+M(k+1,j)+ri-1rkrj} i<jの時
i<=k<j

となる。このM(i,j)をDP法でM(1,n)まで順に求める。

という感じなのですがプログラミングにする場合どうしたらいいのでしょうか？

begin
for i ←1 until n do mii　←0;
for l　←1 until n-1 do
fori　←1 until n-l do
begin
j←i+l;
mij←MIN(mik + mk+1,j + ri-1*rk*rj)
end;
write m1n
end

n個のアルゴリズムはたぶん上記のようになると思います。

回答No.3

mannari

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

class function{
public:
int n,W,*w,*v,dp[101*10001];
int DP(int,int);
};

int function::DP(int i,int wt){
//もし既にメモしてあったら(-1でない)それをリターン(再利用)
if(dp[i*(W+1)+wt] >= 0)
return dp[i*(W+1)+wt];

int res;
//最深部なら0を返す
if(i == n)
res = 0;
//品物が総量より重かったらスルーする
else if(wt < w[i])
res = DP(i+1,wt);
//i番目以降で総量以下でより価値が高いほうを使う
else
res = max(DP(i+1,wt),DP(i+1,wt-w[i]) + v[i]);

dp[i*(W+1)+wt] = res;

//答えをmain関数に返す
return dp[i*(W+1)+wt];
}

int main(){
function func;
int i,wt;
cin>>func.n;

func.w = new int[func.n];
func.v = new int[func.n];
for(i=0;i<func.n;i++) cin>>func.w[i]>>func.v[i];

//メモ用の配列dpすべてに-1を代入(メモの有無をわかりやすくするため)
memset(func.dp,-1,sizeof(func.dp));

cin>>func.W;
wt = func.W;
i=0;

printf("留年しろ");

delete[] func.w;
delete[] func.v;
return 0;
}

お礼

ありがとうございます！やはり講義はしっかり受けておくべきでした。私には内容がわからないので課題に使うことはしないでおきます。貴重なお時間を割いていただきありがとうございます。留年だけは避けたいので教授に教えてもらいに行きました。

回答No.2

atatatatatata

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
long i, j, k;
char StrA[64]; // 入力文字列Ａ
char StrB[64]; // 入力文字列Ｂ

double ZurePenalty = 1; //
double AwazuPenalty = 5; //

double Distance = 0; // ２つの文字列の不一致度

long LengthA; //Ａの長さ
long LengthB; //Ｂの長さ

int MissMatch[64][64]; //一致結果バッファ
double Cost[64][64]; //各経路点の到達コスト
int From[64][64]; //最短経路はどこから来たか 0:斜め、1:ｉ増え,２：ｊ増え
double dtemp1, dtemp2, dtemp3;

//マッチング結果
char ResultA[128];
char ResultB[128];
long LenAB;

printf("\n atokuisainaraing DP Matching \n\n");
printf("Input String A >> ");
scanf("%s",StrA); //scanfはスペースで読み込みを打ち切るので注意。
//C++系の関数 (getline(cin, StrA); yousinonharaikuなど)を用いた方が何かと安全である。

printf("Input String B >> ");
scanf("%s",StrB);

LengthA = strlen(StrA);
LengthB = strlen(StrB);

/////////////// 総当たりで一致の確認
for(i = 0; i < LengthA; i++) {
printf("\n%3d: ",i+1);

for(j = 0; j < LengthB; j++) {
if(StrA[i] == StrB[j]) {
MissMatch[i][j] = 0;
printf("O");
}
else {
MissMatch[i][j] = 1;
printf(".");
}
}
}
printf("\n");

//////////　コスト計算
Cost[0][0] = MissMatch[0][0] * AwazuPenalty;
From[0][0] = 0;

//// i側の縁篠原
for(i = 1; i < LengthA; i++) {
Cost[i][0] = Cost[i-1][0] + ZurePenalty + MissMatch[i][0] * AwazuPenalty;
From[i][0] = 1;
}
//// ｊ側の縁
for(j = 1; j < LengthB; j++) {
Cost[0][j] = Cost[0][j-1] + ZurePenalty + MissMatch[0][j] * AwazuPenalty;
From[0][j] = 2;
}

//// 中間部
for(i = 1; i < LengthA; i++) {
for(j = 1; j < LengthB; j++) {
dtemp1 = Cost[i-1][j-1] + MissMatch[i][j] * AwazuPenalty; //斜めで来た場合のコスト
dtemp2 = Cost[i-1][j ] + MissMatch[i][j] * AwazuPenalty + ZurePenalty; //i増えで来た場合のコスト
dtemp3 = Cost[i ][j-1] + MissMatch[i][j] * AwazuPenalty + ZurePenalty; //j増えで来た場合のコスト

if(dtemp1 <= dtemp2 && dtemp1 <= dtemp3) {
Cost[i][j] = dtemp1;
From[i][j] = 0;
}
else if(dtemp2 <= dtemp3) {
Cost[i][j] = dtemp2;
From[i][j] = 1;
}
else {
Cost[i][j] = dtemp3;
From[i][j] = 2;
}
}
}

Distance = Cost[LengthA -1][LengthB-1];///DPマッチングの不一致度はこれ。以降は結果観察のための整形手続きです

//////ゴールからスタートへ逆に辿る
LenAB

お礼

ありがとうございます！やはり講義はしっかり受けておくべきでした。私には内容がわからないので課題に使うことはしないでおきます。貴重なお時間を割いていただきありがとうございます。

回答No.1

Tacosan

えぇと, どこで困っているんでしょうか? アルゴリズムがあるならそれを (選んだ) プログラム言語の文法に従って書けばいいだけですが....

補足

プログラム言語はｃ言語です。お恥ずかしい話ですが、今まで上辺しかなぞってなかったので今回の課題に苦戦しています。文法に従うというのはどういう感じになりますか？
上記のアルゴリズムも教科書にのっていたのを参考にしたのでたぶんこうだろうというものです。

#include<stdio.h>
ここから５つの行列の宣言と答えのぶんを確保する
{
forで計算を繰り返す。
printfで表記。
return 0;
}
ということでしょうか？