# Naloga/Programiranje/Optimalno iskalno drevo

## 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*)
]
```