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.
heuristics
usamec
źródło
źródło
Odpowiedzi:
MaxSAT - ludzie tak naprawdę dbają o to, ponieważ solwery SAT są tak dobrze rozwinięte, że często najlepszą drogą do twojego ulubionego problemu optymalizacji NP jest w praktyce zmniejszenie go do MaxSAT, a następnie zastosowanie jednego z dobrze znanych solverów. Sprawdź konkurs SAT na testy porównawcze itp.
Wyszukiwarki klików są wykorzystywane w biologii obliczeniowej i kombinatorykach, a algorytmy heurystyczne są szokująco dobre, o ile pamiętam.
Ogromne części badań operacyjnych są poświęcone algorytmom, w tym heurystycznym, do rozwiązywania przypadków programowania liniowego liczb całkowitych lub mieszanych.
źródło
Badania operacyjne wiążą się z wieloma kombinatorycznymi problemami optymalizacji, w których rozwój heurystyki w celu minimalizacji (lub maksymalizacji) kosztów wynikowych jest bardzo aktywny.
Na przykład problem z trasowaniem pojazdu, problem z trasowaniem łuku pojemnościowego, problemy z minimalnym drzewem opinającym i odmiany tych problemów.
źródło