Czy gdzieś istnieje zaimplementowany jakiś algorytm przybliżony? Bo takiego nigdzie nie mogę znaleźć.
0
1
podaj lepsza definicje tego algorytmu bo nie ma nawet czegos takiego na wiki...
2
Tutaj masz przybliżoną implementację algorytmu sortowania (bąbelkowego oraz mergesort).
template<typename It, typename Pred = less<decay_t<decltype(*declval<It>())>>>
void approx_sort(It begin, It end, Pred = Pred{})
{
while(begin != end){
++begin;
}
}
Na przykładzie: http://melpon.org/wandbox/permlink/1Re5VO2majaVGaFv
int main()
{
vector<int> foo = {1,2,3,5,4};
approx_sort(foo.begin(), foo.end());
DBG_CONT(foo);
vector<double> bar = {1.0, 2.0, 3.0, 4.0, 5.0};
approx_sort(bar.begin(), bar.end());
DBG_CONT(bar);
}
Wynik:
foo 1 2 3 5 4
bar 1 2 3 4 5
Jak widać jedna z tablic jest posortowana całkowicie poprawnie, druga tylko w przybliżeniu.
4
@Pijany Soczek liczenie wartości funkcji na podstawie rozwinięcia w szereg taylora to dobry przykład algorytmu przybliżonego. Algortmy zachłanne też często należą do tej klasy.
0
Chodzi o algorytm przyblizony za pomoca ktorego mozna przeszukiwac graf.
0
No to teraz łaskawie wstaw może treść zadania, bo ewidentnie jej nie rozumiesz i nie potrafisz przekazać o co ci chodzi. Trudno mi sobie wyobrazić przybliżone przeszukiwanie grafu ;]
0
Mam podanawane kolejno wspolrzedne miast x i y. Mam wyznaczyc taka droge aby byla jak najkrotsza i nie przekraczajaca limitu dlugosci calej trasy podanej w zadaniu. Przez dane miasto mozna przejsc tylko raz. Podroz ma sie zaczynac i konczyc w 1 miescie. Dodatkowo kazde miasto posiada wartosc zaciekawienia, ktora ma byc najwyzsza, ale tak zeby nie przekroczyc limitu dlugosci.
1
Serio? I liczyłeś że pisząc:
Czy gdzieś istnieje zaimplementowany jakiś algorytm przybliżony? Bo takiego nigdzie nie mogę znaleźć.
Domyślimy się o co ci chodzi? :D :D
Poza tym w treści nie ma nic o przybliżoności tego problemu. Wręcz przeciwnie, jest napisane konkretnie które parametry chcesz maksymalizować.
0
Ok moj blad. Moglby ktos podprowadzic jak sie za to zabrac aby to byl algorytm przyblizony?
0
A jak dobry ma być? Bo najbardziej oczywisty przybliżony algorytm to algorytm zachłanny ;] Wybierasz w każdym kroku "najlepsze miasto" tzn takie dla którego współczynnik "zaciekawienie/odległosc" jest najwyższa. Ale to oczywiście raczej nie da rozwiazania optymalnego!