Heuristiniai metodai


Pavyzdys- vagies uzdavinys:

\begin{eqnarray}\max_x \sum_{i=1}^m c_i x_i, \\
\sum_{i=1}^m g_i x_i \le g,\ x_i =\{0,1\}.
\end{eqnarray}


Çia heuristika

\begin{eqnarray}h_i=c_i/g_i.
\end{eqnarray}


"Gryna" heuristika kai imam daikta

\begin{eqnarray}i^*=\arg \max_i h_i.
\end{eqnarray}


Cia $N\le m^2$ taciau galim "istrigti".
Todel naudojam "mišrias" heuristikas.



jonas mockus 2004-03-01