Szukam listy problemów związanych z optymalizacją trudnych NP, gdzie są aktywne badania w praktycznej heurystyce w celu ich rozwiązania i istnieją wspólne testy porównawcze, które ludzie próbują pokonać.
Przykłady obejmują: rekonstrukcja drzewa filogenetycznego (heurystyczny na przykład tutaj ) komiwojażera (nie tak aktywny, ale LKH jest dość dobrze znana)
Mówiąc dokładniej, szukam obszarów badań, w których ludzie naprawdę dbają o związane z tym koszty (takie jak TSP lub filogeneza wspomniane powyżej). Np. Znalezienie drzewa decyzyjnego nie jest rzeczą, której szukam, ponieważ bardzo niewiele osób dba o wynikową wysokość drzewa.
1
Ta lista jest za długa, co sprawia, że pytanie to jest zbyt szerokie. Jeśli chcesz mieć tak szeroką listę, proponuję sprawdzić kompendium problemów NP-zupełnych: nada.kth.se/~viggo/problemlist/compendium.html
—
Kaveh
Ta lista jest ładna, ale koncentruje się głównie na przybliżeniu. Chcę listę skupiającą się na praktycznej heurystyce.
—
usamec
Czy sprawdziłeś, że ma algorytmy heurystyczne, którymi jesteś zainteresowany? Myślę, że są raczej otwarci na różne algorytmy. (Zgaduję, że wiesz, co oznacza heurystyka w kontekście informatyki teoretycznej, a nie tylko odnosząc się do rzeczy, które po prostu wydają się działać, jeśli nie, zobacz centrum pomocy .) W każdym razie nierozstrzygnięte pytania zwykle nie są dobre , jeśli nie jesteś zadowolony z tej listy, powinieneś dokładniej określić, dlaczego jesteś zainteresowany, i zawęzić zakres pytania.
—
Kaveh
To rozsądne pytanie. Być może PO może wyjaśnić więcej. Czy chodzi o problemy, dla których heurystyka jest wykorzystywana w praktyce, czy chodzi o problemy, dla których aktywnie prowadzone są badania akademickie w heurystyce?
—
Chandra Chekuri
Jedną szeroką klasą problemów jest grupowanie. Heurystyka k-średnich, k-median i powiązanych problemów jest dość aktywnym obszarem badań. Również metryki i powiązane problemy z wnioskami graficznymi.
—
Chandra Chekuri