Jaka jest różnica między heurystyką a algorytmem?

Jaka jest różnica między heurystyką a algorytmem?

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ć.

• Algorytm jest zazwyczaj deterministyczny i udowodniono, że daje optymalny wynik
• Heurystyka nie ma dowodu poprawności, często zawiera elementy losowe i może nie dawać optymalnych wyników.

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.

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.

Heurystyka to przymiotnik dla technik opartych na doświadczeniu, które pomagają w rozwiązywaniu problemów, uczeniu się i odkrywaniu. Metoda heurystyczna służy do szybkiego znalezienia rozwiązania, które ma być bliskie najlepszej możliwej odpowiedzi lub „rozwiązania optymalnego”. Heurystyki to „praktyczne zasady”, domysły oparte na wiedzy, sądy intuicyjne lub po prostu zdrowy rozsądek. Heurystyka to ogólny sposób rozwiązywania problemu. Heurystyka jako rzeczownik to inna nazwa metod heurystycznych.

Mówiąc dokładniej, heurystyka oznacza strategie wykorzystujące łatwo dostępne, choć luźno stosowane informacje do kontrolowania rozwiązywania problemów u ludzi i maszyn.

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.

Algorytm heurystyczny to algorytm, który jest w stanie wygenerować akceptowalne rozwiązanie problemu w wielu praktycznych scenariuszach, na zasadzie ogólnej heurystyki, ale dla którego nie ma formalnego dowodu jego poprawności.

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):

• Dokładnie : udowodniono, że rozwiązanie jest optymalne (lub dokładne ) dla problemu wejściowego
• Przybliżenie : udowodniono, że odchylenie wartości rozwiązania nigdy nie jest bardziej oddalone od wartości optymalnej niż pewna z góry określona granica (na przykład nigdy więcej niż 50% większe niż wartość optymalna)
• Heurystyka : algorytm nie okazał się optymalny ani nie mieścił się w z góry określonych granicach optymalnego rozwiązania

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

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.

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.

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.

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.

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)

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

Jedno z najlepszych wyjaśnień, jakie przeczytałem, pochodzi ze wspaniałej książki Code Complete , którą teraz cytuję:

Heurystyka to technika, która pomaga w poszukiwaniu odpowiedzi. Jej wyniki są przypadkowe, ponieważ heurystyka mówi tylko, jak wyglądać, a nie co znaleźć. Nie mówi, jak dostać się bezpośrednio z punktu A do punktu B; może nawet nie wiedzieć, gdzie znajdują się punkty A i B. W efekcie heurystyka to algorytm w stroju klauna. Jest mniej przewidywalny, daje więcej radości i nie ma 30-dniowej gwarancji zwrotu pieniędzy.

Oto algorytm dojazdu do czyjegoś domu: Jedź autostradą 167 na południe do Puy-allup. Zjedź zjazdem South Hill Mall i jedź 4,5 mil pod górę. Skręć w prawo na światłach przy sklepie spożywczym, a następnie skręć w pierwszą w lewo. Skręć na podjazd dużego, opalanego domu po lewej stronie, pod adresem 714 North Cedar.

Oto heurystyka dotarcia do czyjegoś domu: Znajdź ostatni list, który Ci wysłaliśmy. Jedź do miasta w adres zwrotny. Kiedy dotrzesz do miasta, zapytaj kogoś, gdzie jest nasz dom. Wszyscy nas znają - ktoś chętnie Ci pomoże. Jeśli nie możesz nikogo znaleźć, zadzwoń do nas z publicznego telefonu, a przyjedziemy po Ciebie.

Różnica między algorytmem a heurystyką jest niewielka, a te dwa terminy w pewnym stopniu nakładają się na siebie. Na potrzeby tej książki główną różnicą między nimi jest poziom niezależności od rozwiązania. Algorytm podaje instrukcje bezpośrednio. Heurystyka podpowiada, jak samodzielnie odkryć instrukcje lub przynajmniej gdzie ich szukać.

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.