Algorytm problem

0

Mam problem tzn. nie wiem jak zarobic aby podany nizej algorytm "podrożujący kupiec" liczył drogi z miasta A do B przez wybrane przez ze manie miasta *przez. Program liczy od A do A najkrótsza droge przez wszystkie maista. Prośł by o pomoc i udzielnie wskazuwek jak to zrobic.
tj. Alorytm Branch and bound
// zmienne statyczne
static int n;
static long int inf;
static int *tab;
static int *droga;
static int ilekoszt;

static int *backptr, *tempdroga, *kolumna, *fwdptr, *wiersz;
static int i, index;

//---------------------------------------------------------------------------
// BabTsp
//---------------------------------------------------------------------------
void BabTsp( int n, long int inf, int *tab, int *droga, long int &ilekoszt )
{
void branch( int pocz, long int koszta, int *wiersz, int *kolumna );

::inf = inf;    // ustawienie zmiennych globalnych
::tab = tab;
::n = n;
::ilekoszt = ilekoszt;
::droga = droga;

wiersz = new  int[ n ];
kolumna = new  int[ n ];
fwdptr = new  int[ n ];
backptr = new  int[ n ];
tempdroga = new  int[ n ];


for(  int i = 0; i < n; i++ )
{
    wiersz[ i ] = i+1;
    kolumna[ i ] = i+1;
    fwdptr[ i ] = 0;
    backptr[ i ] = 0;
}// for

::ilekoszt = inf;
branch( 0, 0, wiersz, kolumna );
index = 1;
//zapisanie i uporządkowanie drogi do tablicy droga
for( int i = 0; i < n; i++ )
{
    ::droga[ i ] = index;
    index = tempdroga[ index-1 ];
}// for


ilekoszt = ::ilekoszt;


delete[] wiersz;
delete[] kolumna;
delete[] fwdptr;
delete[] backptr;
delete[] tempdroga;

}// BabTsp

//---------------------------------------------------------------------------
// branch
//---------------------------------------------------------------------------
void branch( int pocz, long int koszta, int* wiersz, int *kolumna )
{
int wart, k,zapkw, first, i, j, last, kosztpluskara, w, rozm;
int *minkolumna, *nowakol, *nowywiersz, *minwiersz;

long int kara;

int min_wk(  int &rozm,  int *wiersz, int *kolumna,  int *minwiersz,  int *minkolumna );
void kary(  int &rozm, int &w,  int &k, long int &kara,  int *wiersz, int *kolumna );

rozm = n - pocz;
minkolumna = new  int[ rozm ];
nowakol = new  int[ rozm - 1 ];
nowywiersz = new  int[ rozm - 1 ];
minwiersz = new  int[ rozm ];


 //koszta -> to suma kosztow tab calej drodze
koszta = koszta + min_wk( rozm, wiersz, kolumna, minwiersz, minkolumna );
if( koszta < ilekoszt )
{
    if( pocz == n - 2 )       // ostatnie dwa sa zostawine wiersze i kolumny
    {
        for( i = 0; i < n; i++ )
            tempdroga[ i ] = fwdptr[ i ];
        if( tab USTAW( wiersz[ 0 ], kolumna[ 0 ], n ) == inf )
            wart = 1;
        else
            wart = 2;
        tempdroga[ wiersz[ 0 ]-1 ] = kolumna[ 2 - wart ];
        tempdroga[ wiersz[ 1 ]-1 ] = kolumna[ wart-1 ];
        ilekoszt = koszta;
    }// if
    else
    {
        kary( rozm, w, k, kara, wiersz, kolumna );
        kosztpluskara = koszta + kara;//  koszt + wartość kary oblicznego punktu
        fwdptr[ wiersz[ w-1 ]-1 ] = kolumna[ k-1 ];    //zapsanie pozycji x do tablicy
        backptr[ kolumna[ k-1 ]-1 ] = wiersz[ w-1 ];    //zapsanie pozycji y do tablicy

        last = kolumna[ k-1 ];        // prevent cycles
        while( fwdptr[ last-1 ] != 0 )
            last = fwdptr[ last-1 ];

        first = wiersz[ w-1 ];
        while( backptr[ first-1 ] != 0 )
            first = backptr[ first-1 ];
         //wartość kolumny i wiersza wskazanego przez last(to x) oraz first(to y)
       zapkw = tab USTAW( last, first, n );
        //teraz ten element ma sie wównac nieskonczoność
        tab USTAW( last, first, n ) = inf;
        //usuniecie wiersza
        for( i = 0; i < w - 1; i++ )        // remove wiersz
            nowywiersz[ i ] = wiersz[ i ];
         //skopiowanie elemantow od "w" do konca macierzy
        for( i = w; i <= rozm - 1; i++ )
            nowywiersz[ i-1 ] = wiersz[ i ];
        //usuniecie kolumny
        for( i = 0; i < k - 1; i++ )       // remove kolumna
            nowakol[ i ] = kolumna[ i ];
        //skopiowanie elemantow od "k" do konca macierzy
        for( i = k; i <= rozm - 1; i++ )
            nowakol[ i-1 ] = kolumna[ i ];
        //wywolanie ponowne funkcji branch z nowymi parametrami
        branch( pocz + 1, koszta, nowywiersz, nowakol );
        //wartośćzapkw zostanie zapusana spowrotem do maicierzy na wskazane miejsce
        tab USTAW( last, first, n ) =zapkw;    // restore previous values
       //ustawienie na zero miejsca gdzie był element
        backptr[ kolumna[ k-1 ]-1 ] = 0;
        fwdptr[ wiersz[ w-1 ]-1 ]= 0;

        if( kosztpluskara < ilekoszt )
        {
            tab USTAW( wiersz[ w-1 ], kolumna[ k-1 ], n ) = inf;
            branch( pocz, koszta, wiersz, kolumna );
            tab USTAW( wiersz[ w-1 ], kolumna[ k-1 ], n ) = 0;
        }// if


    }// else
}// if
for( i = 0; i < rozm; i++ )
{
    for( j = 0; j < rozm; j++ )
    {
        tab USTAW( wiersz[ i ], kolumna[ j ], n ) = tab USTAW( wiersz[ i ], kolumna[ j ], n ) + minwiersz[ i ] + minkolumna[ j ];
    }// for
}// for


delete[] minkolumna;
delete[] nowakol;
delete[] nowywiersz;
delete[] minwiersz;

}// branch

//---------------------------------------------------------------------------
// min_wk -> szukanie minmum tab wierszu i kolumnie
//---------------------------------------------------------------------------
int min_wk( int &rozm, int *wiersz, int *kolumna, int *minwiersz, int *minkolumna )
{
int i, j, zwrot, temp;

zwrot = 0;

//szukanie min tab wierszu
for( i = 1; i <= rozm; i++ ) // min_wk rows
{
temp = inf;
for( j = 1; j <= rozm; j++ )
temp = MIN( temp, tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ));
if( temp > 0 )
{
for( j = 1; j <= rozm; j++ )
{//odejmowanie od każdego elementu elementu tab wierszu mnimalnego ktory jest tab temp
//i jest mniejszy od inf (nieskonczonosci)
if( tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ) < inf )
tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ) = tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ) - temp;
}// for
zwrot += temp; //dodanie wartości temp do zwrot(wartość) z każdego wiersza
}// if
minwiersz[ i-1 ] = temp; //zapisanie każdgo minim tab wierszu do tablicy minwiersz
}// for
//szukanie min tab kolumnie
for( j = 1; j <= rozm; j++ ) // min_wk columns
{
temp = inf;
for( i = 1; i <= rozm; i++ )
temp = MIN( temp, tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ));
if( temp > 0 )
{
for( i = 1; i <= rozm; i++ )
{
if( tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ) < inf )
tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ) = tab USTAW( wiersz[ i-1 ], kolumna[ j-1 ], n ) - temp;
}// for
zwrot += temp;
}// if
minkolumna[ j-1 ] = temp;
}// for

return zwrot;  //zwracana jest suma wszystich wartości minimalnych po wierszach i kolumnach

}// min_wk

//---------------------------------------------------------------------------
// kary ->oblczamy wartośk kary phk dla zerowego elementu
//---------------------------------------------------------------------------
void kary( int &rozm, int &w, int &k, long int &kara, int *wiersz, int *kolumna )
{
int i, j, x, minkolkar, minwierkar, zeroes;

kara = -inf;
for( i = 0; i < rozm; i++ )
{
    for( j = 0; j < rozm; j++ )
    {     //szukanie elemantu zerowego tab macierzy
       if( tab[ (wiersz[ i ]-1) * n + (kolumna[ j ]-1) ] == 0 )
       {
            minwierkar = inf;
            zeroes = 0;
            //szukanie miniamlnego elementu tab wierszu bez zera
            for( x = 0; x < rozm; x++ )
            {
                if( tab USTAW( wiersz[ i ], kolumna[ x ], n ) == 0 )
                    zeroes++;
                else
                    minwierkar = MIN( minwierkar, tab USTAW( wiersz[ i ], kolumna[ x ], n ) );
            }// for
            if( zeroes > 1 )
                minwierkar = 0;

            minkolkar = inf;
            zeroes = 0;
            //szukanie miniamlnego elementu tab kolumnie bez zera
            for( x = 0; x < rozm; x++ )
            {
                if( tab USTAW( wiersz[ x ], kolumna[ j ], n ) == 0 )
                    zeroes++;
                else
                    minkolkar = MIN( minkolkar, tab USTAW( wiersz[ x ], kolumna[ j ], n ) );
            }// for
            if( zeroes > 1 )
                minkolkar = 0;
            //sumawanie minmalengo elementu tab wierszu i minimalnego elementu tab kolunie
            if( minwierkar + minkolkar > kara )
            {
                // a better edge has been found
                kara = minwierkar + minkolkar;
                w = i+1;    //zapamietanie pozycji x tego elementu
                k = j+1;    //zapamietanie pozycji y tego elementu
            }// if
        }// if
    }// for
}// for

}// kary

0

dobra rada - nie podawaj calego kodu, nikomu nie zechce sie go czytac... A do rozwiazania problemu poszukaj opisu algorytmow grafowych - a w szczegolnosci problemu komiwojazera

1 użytkowników online, w tym zalogowanych: 0, gości: 1