[CamelCase]

Czy ma jakąś specjalną nazwę podejście do problemu optymalizacji, które przeszukuje przestrzeń rozwiązań w kolejności od potencjalnie najlepszych rozwiązań (odmiana brute-force), dzięki czemu algorytm może przerwać pracę po pierwszym znalezionym rozwiązaniu ponieważ ma pewność, że jest ono optymalne?
#programowanie #algorytmy

[interface]

@CamelCase: co masz na myśli przez "optymalne"?

[CamelCase]

@interface: Najlepsze możliwe.

[interface]

@CamelCase: musisz dokładniej opisać problem, jego złożoność i pulę rozwiązań oraz optymalność wymaganego rozwiązania. https://en.wikipedia.org/wiki/Tree_traversal

[CamelCase]

@interface: Cokolwiek, to jest pytanie natury ogólnej. Załóżmy na przykład, że szukamy zbioru dominującego w grafie, w którym każdy węzeł posiada jakąś wagę w taki sposób, żeby suma wag wybranych węzłów była minimalna. To jest ogólnie problem NP-trudny, albo NP-zupełny, nie pamiętam.

I teraz są dwa podejścia do brute-force. Albo wybieramy kolejne kombinacje węzłów i jeśli tworzą one zbiór dominujący, to liczymy sumę ich wag i jeżeli jest ona niższa niż

[ponton]

@CamelCase: Moim zdaniem nie ma to nazwy. Jest to trochę pomieszanie heurystyki (bo zgadujesz) z algorytmami zachłannymi (bo zachłannie wybierasz jak najlepsze potencjalne rozwiązania). Wszystko rozbija się o to, w jaki konkretnie sposób wybierasz kolejne potencjalne rozwiązania.