Jaka jest różnica między heurystyką a algorytmem?
algorithm
definition
heuristics
nomenclature
Parada uliczna
źródło
źródło
Odpowiedzi:
Algorytm to opis zautomatyzowanego rozwiązania problemu . To, co robi algorytm, jest precyzyjnie określone. Rozwiązanie może, ale nie musi być najlepsze z możliwych, ale od samego początku wiesz, jaki wynik uzyskasz. Implementujesz algorytm używając jakiegoś języka programowania, aby uzyskać (część) programu .
Niektóre problemy są trudne i możesz nie być w stanie uzyskać akceptowalnego rozwiązania w akceptowalnym czasie. W takich przypadkach często można uzyskać niezłe rozwiązanie znacznie szybciej, stosując pewne arbitralne wybory (wyuczone domysły): to jest heurystyka .
Heurystyka nadal jest rodzajem algorytmu, ale takim, który nie będzie badał wszystkich możliwych stanów problemu lub zacznie od zbadania najbardziej prawdopodobnych.
Typowe przykłady pochodzą z gier. Pisząc program do gry w szachy, można sobie wyobrazić wypróbowanie każdego możliwego ruchu na jakimś poziomie głębokości i zastosowanie funkcji oceny na szachownicy. Heurystyka wykluczyłaby pełne gałęzie, które zaczynają się od oczywiście złych ruchów.
W niektórych przypadkach nie szukasz najlepszego rozwiązania, ale dowolnego rozwiązania pasującego do jakiegoś ograniczenia. Dobra heurystyka pomogłaby znaleźć rozwiązanie w krótkim czasie, ale może również nie znaleźć żadnego, jeśli jedyne rozwiązania znajdują się w stanach, których nie zdecydował się próbować.
źródło
Wiele problemów, dla których nie jest znany żaden skuteczny algorytm do znalezienia optymalnego rozwiązania, ma podejście heurystyczne, które bardzo szybko daje prawie optymalne wyniki.
Istnieją pewne nakładania się: „algorytmy genetyczne” to przyjęty termin, ale ściśle mówiąc, są to heurystyki, a nie algorytmy.
źródło
Heurystyka, w skrócie, to „zgadywanie oparte na wiedzy”. Wikipedia ładnie to wyjaśnia. Na koniec przyjmuje się metodę „ogólnej akceptacji” jako optymalne rozwiązanie określonego problemu.
Algorytm natomiast jest metodą zawierającą skończony zbiór instrukcji używanych do rozwiązania problemu. Metoda została udowodniona matematycznie lub naukowo, aby rozwiązać problem. Istnieją formalne metody i dowody.
źródło
Algorytm jest samowystarczalny zestaw krok po kroku operacji do wykonania 4 , zazwyczaj interpretowane jako skończonej sekwencji instrukcji (komputer lub człowieka) w celu określenia, rozwiązanie problemu, takie jak: czy istnieje ścieżka z A do B, czyli najmniejsza ścieżka między A i B. W tym drugim przypadku możesz być również zadowolony z alternatywnego rozwiązania „w miarę bliskiego”.
Istnieją pewne kategorie algorytmów, z których jednym jest algorytm heurystyczny. W zależności od (sprawdzonych) właściwości algorytmu w tym przypadku należy on do jednej z tych trzech kategorii (uwaga 1):
Zauważ, że algorytm aproksymacji jest również heurystyczny, ale z silniejszą właściwością, że istnieje udowodnione powiązanie z rozwiązaniem (wartością), które generuje.
W przypadku niektórych problemów nikt nigdy nie znalazł „wydajnego” algorytmu obliczania optymalnych rozwiązań (uwaga 2). Jednym z tych problemów jest dobrze znany problem komiwojażera. Na przykład algorytm Christophidesa dla problemu komiwojażera nazywano kiedyś heurystycznym , ponieważ nie udowodniono, że mieści się w zakresie 50% optymalnego rozwiązania. Ponieważ jednak zostało udowodnione, algorytm Christophidesa jest dokładniej określany jako algorytm aproksymacyjny.
Ze względu na ograniczenia co do tego, co potrafią komputery, nie zawsze jest możliwe skuteczne znalezienie najlepszego rozwiązania. Jeśli w zadaniu jest wystarczająca struktura, może istnieć skuteczny sposób na przejście przez przestrzeń rozwiązania, nawet jeśli przestrzeń rozwiązania jest ogromna (tj. W przypadku problemu najkrótszej ścieżki).
Heurystyki są zwykle stosowane w celu skrócenia czasu działania algorytmów, dodając „informacje eksperckie” lub „wyuczone domysły”, aby wskazać kierunek wyszukiwania. W praktyce heurystyka może być również podprogramem dla optymalnego algorytmu, aby określić, gdzie szukać najpierw .
(uwaga 1) : Dodatkowo algorytmy charakteryzują się tym, czy zawierają elementy losowe, czy niedeterministyczne. Algorytm, który zawsze działa w ten sam sposób i daje taką samą odpowiedź, nazywany jest deterministycznym.
(uwaga 2) : Nazywa się to problemem P vs NP i jest mało prawdopodobne, aby problemy sklasyfikowane jako NP-zupełne i NP-trudne miały „wydajny” algorytm. Uwaga; jak @Kriss wspomniał w komentarzach, istnieją jeszcze „gorsze” typy problemów, które mogą wymagać wykładniczego czasu lub przestrzeni do obliczenia.
Istnieje kilka odpowiedzi, które odpowiadają na część pytania. Uznałem, że są mniej kompletne i niewystarczająco dokładne, i zdecydowałem się nie edytować zaakceptowanej odpowiedzi udzielonej przez @Kriss
źródło
Właściwie nie sądzę, żeby było między nimi wiele wspólnego. Niektóre algorytmy używają heurystyki w swojej logice (często w celu wykonania mniejszej liczby obliczeń lub uzyskania szybszych wyników). Zwykle heurystyki są używane w tzw. Algorytmach zachłannych.
Heurystyka to pewna „wiedza”, która, jak zakładamy, jest dobra do wykorzystania w celu uzyskania najlepszego wyboru w naszym algorytmie (kiedy należy dokonać wyboru). Na przykład ... heurystyka w szachach mogłaby być (zawsze bierz królową przeciwników, jeśli możesz, ponieważ wiesz, że jest to silniejsza liczba). Heurystyka nie gwarantuje, że doprowadzi Cię to do prawidłowej odpowiedzi, ale (jeśli założenia są prawidłowe) często uzyskuje się odpowiedź bliską najlepszej w znacznie krótszym czasie.
źródło
Heurystyki to algorytmy, więc w tym sensie ich nie ma, jednak heurystyki przyjmują podejście „zgadywania” do rozwiązywania problemu, dając „dostatecznie dobrą” odpowiedź, zamiast znajdować „najlepsze możliwe” rozwiązanie.
Dobrym przykładem jest sytuacja, w której masz bardzo trudny (przeczytaj NP-zakończony) problem, dla którego chcesz rozwiązać, ale nie masz czasu, aby do niego dotrzeć, więc musisz użyć wystarczająco dobrego rozwiązania opartego na algorytmie heurystycznym, takim jak znalezienie rozwiązania problemu komiwojażera przy użyciu algorytmu genetycznego.
źródło
Algorytm to sekwencja pewnych operacji, które na podstawie danych wejściowych obliczają coś (funkcję) i generują wynik.
Algorytm może dawać dokładne lub przybliżone wartości.
Może również obliczyć losową wartość, która jest z dużym prawdopodobieństwem zbliżona do dokładnej wartości.
Algorytm heurystyczny wykorzystuje pewien wgląd w wartości wejściowe i oblicza nie dokładną wartość (ale może być bliska optymalnej). W niektórych szczególnych przypadkach heurystyka może znaleźć dokładne rozwiązanie.
źródło
Algorytm to jasno zdefiniowany zestaw instrukcji do rozwiązania problemu. Heurystyka polega na wykorzystaniu podejścia uczenia się i odkrywania w celu osiągnięcia rozwiązania.
Jeśli więc wiesz, jak rozwiązać problem, użyj algorytmu. Jeśli potrzebujesz opracować rozwiązanie, to jest to heurystyka.
źródło
Heurystyka to zazwyczaj optymalizacja lub strategia, która zwykle zapewnia wystarczająco dobrą odpowiedź, ale nie zawsze i rzadko jest to najlepsza odpowiedź. Na przykład, jeśli miałbyś rozwiązać problem komiwojażera brutalną siłą, odrzucenie częściowego rozwiązania, gdy jego koszt przekracza koszt obecnego najlepszego rozwiązania, jest heurystyką: czasami pomaga, innym razem nie, a na pewno nie. Popraw teoretyczny czas działania algorytmu (notacja big-oh)
źródło
Myślę, że heurystyka jest bardziej ograniczeniem używanym w modelu opartym na uczeniu się w sztucznej inteligencji, ponieważ przyszłe stany rozwiązań są trudne do przewidzenia.
Ale po przeczytaniu powyższych odpowiedzi mam wątpliwości: „Jak można z powodzeniem zastosować heurystykę przy użyciu technik optymalizacji stochastycznej?” Lub czy mogą one działać jako pełnoprawne algorytmy, gdy są używane z optymalizacją stochastyczną?
http://en.wikipedia.org/wiki/Stochastic_optimization
źródło
Jedno z najlepszych wyjaśnień, jakie przeczytałem, pochodzi ze wspaniałej książki Code Complete , którą teraz cytuję:
źródło
Znajdują rozwiązanie nieoptymalne bez żadnej gwarancji co do jakości znalezionego rozwiązania, oczywiste jest, że przy opracowywaniu heurystyki tylko wielomian ma sens. Zastosowanie tych metod jest odpowiednie do rozwiązywania rzeczywistych problemów lub dużych problemów tak niewygodnych z obliczeniowego punktu widzenia, że dla nich nie ma nawet algorytmu, który byłby w stanie znaleźć przybliżone rozwiązanie w czasie wielomianowym.
źródło