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