Naloga/Programiranje/Optimalno iskalno drevo

Iz MaFiRaWiki

Naloga

V Mathematici sprogramiraj algoritem za konstrukcijo optimalnega (statičnega) iskalnega drevesa.

Rešitev 1

Clear[omega1,g1,r1]
omega1[p_List,q_List,i_,j_]:=If[i==j,q[[i+1]],omega1[p,q,i,j-1]+p[[j]]+q[[j + 1]]]
g1[p_List,q_List,i_,j_]:=If[i==j,0,Min[Table[g1[p,q,i,k-1]+g1[p,q,k,j],{k,i + 1,j}]]+omega1[p,q,i,j]]
r1[p_List,q_List,i_,j_]:=If[i==j,
  0,
  Ordering[Table[g1[p,q,i,k-1]+g1[p,q,k,j],{k,i+1,j}],1][[1]]
 ]

Clear[tabela1]
tabela1[p_List,q_List]:=Module[{n=Length[p]},
  MatrixForm[Table[{omega1[p,q,i,j],g1[p,q,i,j],r1[p,q,i,j]},{i,0,n},{j,i,n}]] (*žal ne bo desno poravnana*)
 ]

Rešitev 2

Clear[omega2,g2,r2]
omega2[p_List,q_List,i_,j_]:=If[i==j,
  q[[i+1]],
  If[i<j,
   omega2[p,q,i,j-1]+p[[j]]+q[[j+1]],
   Null
  ]
 ]
g2[p_List,q_List,i_,j_]:=If[i==j,
  0,
  If[i<j,
   Min[Table[g2[p,q,i,k-1]+g2[p,q,k,j],{k,i+1,j}]]+omega2[p,q,i,j],
   Null
  ]
 ]
r2[p_List,q_List,i_,j_]:=If[i==j,
  0,
  If[i<j,
   Ordering[Table[g2[p,q,i,k-1]+g2[p,q,k,j],{k,i+1,j}],1][[1]],
   Null
  ]
 ]

Clear[tabela2]
tabela2[p_List,q_List]:=Module[{n=Length[p]},
  MatrixForm[Table[{omega2[p,q,i,j],g2[p,q,i,j],r2[p,q,i,j]},{i,0,n},{j,0,n}]] (*ta bo desno poravnana, vendar bolj nepregledna*)
 ]