Skuteczne zastosowanie metod rozgałęzionych i związanych z problemami trudnymi dla NP

13

Rozgałęzienie i powiązanie to skuteczna heurystyka dla problemów wyszukiwania, a Wikipedia wymienia wiele trudnych problemów, w których zastosowano rozgałęzienie i powiązanie. Jednak nie udało mi się znaleźć referencji sugerujących, że jest to więcej niż „jedna metoda” rozwiązania tych problemów.

Anegdotycznie słyszałem, że jedne z najlepszych heurystyki dla programowania SAT i liczb całkowitych pochodzą z gałęzi i są powiązane, więc moje pytanie brzmi:

Czy ktoś może wskazać mi jakieś odniesienia opisujące efektywne wykorzystanie gałęzi i związane z trudnymi NP?

ds.algorithms  reference-request  optimization  heuristics 
— Suresh Venkat
źródło
1
Właśnie czytam ten artykuł z innego powodu, ale wydaje się, że porusza twoje pytanie i jest fascynujący: portfolio algorytmów Gomesa i Selmana.
— Aaron Sterling
2
Dobra książka do czytania o programowaniu liczb całkowitych to Integer and Combinatorial Optimization autorstwa Nemhauser & Wolsey. Obejmuje szeroki zakres tematów, w tym różne paradygmaty, takie jak odgałęzienie i powiązanie, rozgałęzienie i wycięcie itp. Oraz inne techniki własności intelektualnej, takie jak wycinanie samolotów itp.
— Opt

Odpowiedzi:

9

W przypadku TSP sprawdź tę książkę ... http://www.tsp.gatech.edu/book/index.html

Rozumiem, że nie ma jednego narzędzia do zabicia ich wszystkich. Prawdopodobnie każde rozwiązanie rekurencyjne wykorzystujące backtracking i niektóre funkcje oceniania używają rozgałęzienia i powiązania. Jako taka, duża część solverów do trudnych problemów NP wykorzystuje jakąś formę rozgałęzienia i związania.

— Sariel Har-Peled
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.