Hrvatski matematički elektronski časopis math.e

http://www.math.hr/~mathe/

Heuristički algoritmi za 0-1 problem naprtnjače

Anamari Nakić

Pseudokod algoritma simuliranog kaljenja za 0-1 problem naprtnjače



array annealing_algorithm (int cmax, real T0, real a, array p,array w, int n, real M) {

    array X, Y;
    real CurW, T;
    int j, c;

    c = 0;
    T = T0;
    X = [0,...,0] ;   //  =  [x0, ..., xn-1]
    CurW = 0;
    Xbest = X;
    while ( c <= c_max ) {
        j = random_int(0, n-1);
        Y = X;
        Y[j] = 1 - X[j];
        if (Y[j] == 1) && (CurW + w[j] > M)
            Y = Fail;       // Y nije dopustivo rjesenje
        if ( Y != Fail ) {
            if (Y[j] == 1) {
                X = Y;
                CurW = CurW + w[j];
                if ( P(X) > P(Xbest) )
                        Xbest = X;
            }
            else {
                r = random_real(0,1);
                if ( r < e(-p[j]/T) ) {
                    X = Y;
                    CurW = CurW - w[j];
                }
             }
        }
        c = c + 1;
        T = a*T;
    }
    return Tbest;
}