[c++] Znalezienie ekstremum funkcji - optymalizacja

[JoeBuck]

Witam!

Borykam się z problemem znalezienia maksymalnej wartości funkcji określonej wzorem:

a=b+sqrt(c);

Przy czym wartości b i c są od siebie zależne, tzn. do każdego c jest przyporządkowane jakieś b.

Wartość tę muszę znaleźć wielokrotnie (nawet kilkaset tysięcy razy) i dlatego szukam sposobu szybszego niż zwykły brute-force.
Znam możliwe wartości c, więc na początku programu obliczam dla nich pierwiastki i zapamiętuję w tablicy, ale nadal działa to zbyt wolno kiedy muszę to liczyć 100 000 razy.

Ma ktoś może jakiś mądry pomysł jak by to przyspieszyć?

[thalcave]

Z definicji ekstrema próbowałeś? co w tej funkcji jest parametrem a co zmienną?

[JoeBuck]

Zarówno b jak i c są parametrami

Cała funkcja wygląda tak:

Kod: Zaznacz cały

int funkcja(int b,int c)
{
 return ceil(b+sqrt(c));
}

Próbowałem znaleźć maximum z pochodnej, ale... nie mogę znaleźć pochodnej

[DDAroo]

o.0

Ta funkcja to f(x, y) = ceil(x + sqrt(y)) ?

[JoeBuck]

f(x,y)=ceil(x+sqrt(y));

[DDAroo]

Wiadomo coś o x tzn. czy jest większe od 0? Ekstrema chyba można wyliczyć analitycznie z funkcji f(x, y) = x + sqrt(y) korzystając z pochodnych cząstkowych i warunku na ekstremum lokalne funkcji dwóch zmiennych.

EDIT.
Zresztą funkcja jest monotoniczna więc jej wartość jest tym większa im większe jest x i y oraz tym mniejsza im mniejsze jest x i y.

EDIT2.

Przy czym wartości b i c są od siebie zależne, tzn. do każdego c jest przyporządkowane jakieś b.

W jaki sposób są zależne? Da się to opisać wzorem, czy jest to tabela z wartościami b i c?

[JoeBuck]

x może być mniejsze, równe albo większe od zera - wiadomo tylko, że zawsze jest całkowite.

Wiem, że funkcja jest monotoniczna, ale problem leży w tym, że zmiana x nie zawsze pociąga za sobą zmianę y w tą samą stronę. Czasem x rośnie a y maleje, czasem odwrotnie, czasem oba rosną. Jedyna zależność jest taka, że dla danego y zawsze mamy jednoznacznie określony x.

Masz może pod ręką jakieś dobre materiały o pochodnych i ekstremach funkcji dwuargumentowych?

Edit:
Tabela z wartościami.

[DDAroo]

Hmm to trzeba zrobić inaczej, bo skoro b i c są ztablicowane to nie jest to typowe matematyczne szukanie ekstremum funkcji dwóch zmiennych. Dużo masz tych wartości b i c? kilka tysięcy?

[JoeBuck]

Kilkaset tysięcy ;/

[DDAroo]

c jest także całkowite? są jakieś ograniczenia co do wartości maksymalnej c oraz maksymalnej i minimalnej wartości b? Potrzebujesz dokładnie największej wartości czy może być bliska największej?

[JoeBuck]

c całkowite

b>2 i b<1 000 000
c>2 i c<1 000 000

Potrzebuję dokładnie największej

[mikolajs]

Przy czym wartości b i c są od siebie zależne, tzn. do każdego c jest przyporządkowane jakieś b.

a to przyporządkowanie określone jest wzorem?

[JoeBuck]

Nie jest określone żadnym wzorem. Dla jakiegoś c mamy jakieś b.

[mikolajs]

Jeżeli polega to na wczytywaniu z pliku po 100 000 par liczb i powtarzane jest to kilkaset tysięcy razy (jeżeli dobrze zrozumiałem) to dłużej będzie trwało wczytywanie z pliku niż same obliczenia.
Maksimum normalnie byłoby dla max x i max y. Więc możesz znaleźć maksymalną wartość x i y i odrzucić wyniki dla których: max(x) > sqrt(max(y) + x). (może można by to jeszcze bardziej zawęzić)

[JoeBuck]

No tak, ale wczytywania niestety nie przyspieszę.

Czas mi się kończy, więc chyba już tylko lekko dopieszczę tego brute-force'a
Dzięki za zainteresowanie i zaangażowanie.
Mikolajs, skorzystam z Twoich zależności, dziękuję!