Optymalizacja funkcji rekurencyjnej

Dla specjalistów Programowanie
#1

Co zrobić aby poniższy program który musi się wywoływać rekurencyjnie obniżył czas działania? Ponieważ przy dużych danych wejściowych się nie wyrabiam w czasie.

 

Program przyjmuje na wejściu np:

8

12     13   33    10   24   9   17   22

22     32   28    4    5     11  7    26

32     5     29    7    23   10  4    24

10     34   27    2    6     1    33  30

19    29    34    32  10   16  5    24

6     1      3      34   27  19   27 12

26   10    3      29   1    14  25   2

10   10    1      25   17  15  17 21

 

czyli pole n na n (w tym przypadku 8 x 8  )

oraz wartości do każdego pola, program oblicza najlepsze ustawienie n  pionków, tak aby suma z pod tych pól gdzie pionki są wstawiane była jak najmniejsza, drugim warunkiem jest to aby każdy pionek znalazł się  w innym  wierszu i innej kolumnie (nie zbijają się nawzajem).

 

wynikiem jest  n (w naszym przykpadku 8  ) liczb oznaczających numer rzędu, w którym należy ustawić pionek dla każdej kolumny.

 

czyli w naszym przypadku wynikiem będzie:

 

0 5 7 2 1 3 4 6 

 

(numerujemy od zera do n-1 wiersze i kolumny oczywiście, jak to w tablicach jest)

 

czyli najmniejsza sumą jest 34.

 

 

#include
using namespace std;
int minimum=999999;

void funkcja(int unsigned n,unsigned int * tab0,unsigned int * tab1,unsigned int i,unsigned int ** tablica,unsigned int * tablica2)
{
unsigned int sum=0;
for(int k=0;k<n;k++)
{
if(tab1[k]==1)
{
tab0[i]=k;
tab1[k]=0;

if(i==n-1){

for(int l=0;l<n;l++)
{
sum+=tablica[tab0[l]][l];

        }

if(sum<minimum)
{
minimum=sum;

                for(int m=0;m<n;m++)
                {
                tablica2[m]=tab0[m];
                }
            }
                
        }
       


           else
           
            funkcja(n,tab0,tab1,i+1,tablica,tablica2);

tab1[k]=1;

    }

}

}

int main()
{
unsigned int n;
cin>>n;
unsigned int ** tablica = new unsigned int * [n];
for(int i=0;i<n;i++)
{
tablica[i]= new unsigned int [n];
}
unsigned int * tablica2 = new unsigned int[n];

unsigned int * tab0 = new unsigned int[n];
unsigned int * tab1 = new unsigned int[n];
for(int i=0;i<n;i++)
{
tab0[i]=0;
tab1[i]=1;
for(int j=0;j<n;j++)
{
cin>>tablica[i][j];
}
}
funkcja(n,tab0,tab1,0,tablica,tablica2);

for(int i=0;i<n;i++)
{
cout<<tablica2[i]<<" ";
}

delete [] tablica[0];
delete [] tablica;
delete [] tablica2;
delete [] tab0;
delete [] tab1;
return 0;
}

da się to na pewno napisać bardziej optymalnie, albo za dużo razy wywołuje mi się funkcja rekurencyjna albo nie wiem za dużo pętli for w funkcji? ale nie mam pomysłu jak to zoptymalizować, dziękuję za każdą pomoc.

#2

Mógłbyś jakoś skomentować ten kod?

#3

Twój program dla 3x3

1 2 3

1 2 3

1 2 3

oraz dla

3 2 1

3 2 1

3 2 1

Zwraca to samo. Więc albo masz błęd w programie albo w treści. Może jakiś prosty przykład dla małej tablicy ?

#4

drobok -  zwraca to samo faktycznie, ale to dobry wynik :slight_smile:

 

enedil - ogólnie jest to program wyszukujący wszystkie możliwe nieszachowane rozwiązania, i wybiera to w którym suma wartości z pól jest najmniejsza

 

dla dużych tablic program przekracza czas, po prostu jest za wolny, coś źle napisałem ;/

#5

Jeżeli f(x) = p, to wyklucza to prawdziwość f(y) = p? Nie, bo funkcja przyporządkowuje każdemu q jedną wartość, ale nie koniecznie odwrotnie, tzn. możliwa jest sytuacja w której a != b && f(a) == f(b).

#6

Ale tutaj biorąc ten sam wynik dla danych wpisanych w odwrotnej kolejności otrzymujemy imo najgorszą możliwą kolejność:

Mamy sumując dalej moje 3x3 (zaznaczyłem odpowiedź programu 0 1 2)

Dla tablicy 3 2 1

9 6 3

6 4 2

3 2 1

A dla tablicy 1 2 3

3 6 9

2 4 6

1 2 3

Mam możliwość osiągnięcia stanu idealnego przy założeniu że można stawiać w dowolnym miejscu.

Biorąc więc wynik naszej funkcji jako ten sam dla obu stanów, otrzymujemy wynik odwrotny (najgorszy przypadek).

Nasz program daje wynik 0 1 2 co założymy jako przypadek idealny do pierwszego podejścia.

Dla 1 2 3 mamy maksimum sum 1 4 9 co jest przypadkiem najgorszym, lepsze są np 3 4 3, 6 2 3 itd 

Dla 3 2 1 mamy maksimum sum 3 4 3 co rzeczywiście jest przypadkiem idealnym 

 

Nawet wstawiając element pod zaznaczony otrzymujemy:

Dla 1 2 3 -> 0 2 6 

Dla 3 2 1 -> 0 2 2 

I znów różnica jak wyżej tylko sumy inne.

#7

http://zasoby1.open.agh.edu.pl/dydaktyka/matematyka/c_badania_operacyjne/krok/krok8_01.html

#8

Rozwinę trochę wypowiedź użytkownika [alex]. Generalnie to twierdzenie, jest dobre. Jego zaletą jest to, że możesz “nakodzić” ten algorytm nie używając zbytnio mózgu (nie rozumiejąc go). Alternatywą jest użycie tego http://pl.wikipedia.org/wiki/Programowanie_liniowe. Masz pewną funkcję (notabene bijekcję) gdzie musisz zminimalizować sumę (funkcję celu), przy pewnych ograniczeniach. Zapisz równania i rozwiąż. Wymaga to odrobiny więcej myślenia, ale możesz tym rozwiązać nie tylko problem, gdzie w każdym wierszu i kolumnie ma stać jeden pionek, ale każde dowolne liniowe ograniczenie np. x < y. Co więcej możesz te ograniczenia dowolnie składać. Jest to zatem sposób bardziej ogólny, ale tak jak mówiłem, nie użyjesz tego bez odrobiny inwencji.

#9

kostek135, 50! - godzinami? Jesteś niepoprawnym optymistą! Bo to już będzie raczej latami.

#10

ok dzięki, postaram się to ogarnąć :) zastanawiam się właśnie jak to bardziej optymalnie napisać, bo sam program nie jest trudny ale jakoś tą rekurencje nie mogę w głowie zrozumieć :smiley: ogólnie n może być max == 35 ale no niestety i tak lipa :stuck_out_tongue:

#11

]

#12

temat do zamknięcia, pobawiłem się z ifami (źle warunki między innymi miałem), usunąłem sumowanie w pętli oraz  kilka innych ulepszeń i od razu mniejsza złożoność chociaż nie wiem czy dalej nie n! na pewno dwa razy mniej obliczeń za każdym wywołaniem oraz mniej razy się wywołuje funkcja, program przyśpieszony o 8 sekund, dzięki wszystkim :slight_smile: fajna ta technika węgierska ale niestety musiałem zostać przy tym sposobie co był ;p

#13

Dla n = 35 było więcej niż wszechświa, chyba, że pracujesz na kompie z 1024 Xeonami 6 x 4.00 THz każdy :wink: