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

• 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 przynieść optymalnych wyników.

Wiele problemów, dla których nie jest znany skuteczny algorytm do znalezienia optymalnego rozwiązania, ma podejścia heurystyczne, które bardzo szybko dają prawie optymalne wyniki.

Są pewne nakładania się: "algorytmy genetyczne" jest akceptowanym terminem, ale ściśle mówiąc, są to heurystyka, nie algorytmy.

Heurystyczne, w skrócie to "wyedukowane zgadywanie". Wikipedia ładnie to wyjaśnia. Na koniec przyjmuje się metodę "ogólnej akceptacji" jako optymalne rozwiązanie określonego problemu.

Heurystyka to przymiotnik dla techniki oparte na doświadczeniu, które pomagają w rozwiązywaniu problemów, uczeniu się i odkrycie. Stosuje się metodę heurystyczną aby szybko dojść do rozwiązania, które jest / align = "left" / odpowiedź, czyli "optymalne rozwiązanie". Heurystyka to " Zasady kciuk", wyedukowane domysły, intuicyjne osądy albo po prostu zdrowy rozsądek. Heurystyka jest ogólny sposób rozwiązania problemu. Heurystyka jako rzeczownik to inna nazwa do metod heurystycznych.

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

Podczas gdy algorytm jest metodą zawierającą skończony zbiór instrukcji używanych do rozwiązywania problem. Metoda została udowodniona matematycznie lub naukowo do pracy dla problemu. Istnieją metody formalne i dowody.

Algorytm heurystyczny {[13] } jest algorytmem, który jest w stanie wytworzyć akceptowalne rozwiązanie problemu w wiele praktycznych scenariuszy, w moda na ogólne heurystyczne, ale dla których nie ma formalnego dowodu na jego poprawność.

Właściwie to nie sądzę, że jest między nimi wiele wspólnego. Niektóre algorytmy wykorzystują heurystykę w swojej logice (często w celu wykonania mniej obliczeń lub uzyskania szybszych wyników). Zwykle heurystyka stosowana jest w tzw. algorytmach chciwych.

Heurystyka to pewna "wiedza", którą Zakładamy, że jest dobra do wykorzystania w celu uzyskania najlepszego wyboru w naszym algorytmie(kiedy wybór należy podjąć). Na przykład ... heurystyka w szachach może być (zawsze bierz królową przeciwników, jeśli możesz, ponieważ wiedz, że jest to silniejsza postać). Heurystyka nie gwarantuje, że doprowadzi Cię do prawidłowej odpowiedzi, ale (jeśli założenia są poprawne) często uzyskują odpowiedź, która jest bliska najlepszej w znacznie krótszym czasie.

Heurystyka to algorytmy, więc w tym sensie nie ma żadnego, jednak heurystyka przyjmuje podejście "zgadywania" do rozwiązywania problemów, dając "wystarczająco dobrą" odpowiedź, zamiast znaleźć "najlepsze możliwe" rozwiązanie.

Dobrym przykładem jest sytuacja, w której masz bardzo trudny (Czytaj np-complete) problem, który chcesz rozwiązać, ale nie masz czasu, aby go rozwiązać, więc musisz użyć wystarczająco dobrego rozwiązania opartego na algorytmie heurystycznym, takiego jak znalezienie rozwiązania problemu podróżnego sprzedawcy za pomocą algorytm genetyczny.

Algorytm jest sekwencją pewnych operacji, które dane wejście oblicza coś (funkcję) i wyprowadza wynik.

Algorytm może dać dokładną lub przybliżoną wartość.

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ć zbliżona do optymalnej). W niektórych szczególnych przypadkach heurystyka może znaleźć dokładne rozwiązanie.

Algorytm jest jasno zdefiniowanym zestawem instrukcji do rozwiązania problemu, heurystyka polega na wykorzystaniu podejścia uczenia się i odkrywania, aby osiągnąć rozwiązanie.

Więc jeśli wiesz, jak rozwiązać problem, użyj algorytmu. Jeśli musisz opracować rozwiązanie, to jest to heurystyka.

Algorytm jest samodzielnym zestawem operacji krok po kroku do wykonania 4, zazwyczaj interpretowane jako skończonej sekwencji (komputer lub człowiek) instrukcje do określenia rozwiązania problemu, takiego jak: czy istnieje ścieżka od A do B, lub co jest najmniejszą ścieżkę między A I B. w tym drugim przypadku, można również być zadowolony z "rozsądnie blisko" alternatywne rozwiązanie.

Istnieją pewne kategorie algorytmów, z których algorytm heurystyczny jest jeden. W zależności od (udowodnionych) właściwości algorytmu w tym przypadku należy do jednej z tych trzech kategorii (Uwaga 1):

• dokładne: rozwiązanie okazało się optymalne (lub dokładne rozwiązanie) do problemu wejściowego
• przybliżenie: udowodniono, że odchylenie wartości rozwiązania nigdy nie jest dalej od wartości optymalnej niż jakaś predefiniowana granica (na przykład nigdy więcej niż 50% większe niż optymalna wartość)
• heurystyka: algorytm nie został udowodniony jako optymalny, ani w ramach predefiniowanej granicy optymalnego rozwiązania

Zauważ, że algorytm aproksymacji jest również heurystą, ale z silniejszą właściwością, że istnieje udowodnione powiązanie z rozwiązaniem (wartością), które wyprowadza.

W przypadku niektórych problemów, nikt nigdy nie znalazł 'wydajnego' algorytmu do obliczania optymalnych rozwiązań(Uwaga 2). Jednym z tych problemów jest dobrze znane Podróżowanie Problem Ze Sprzedawcą. Na przykład algorytm christophidesa dla problemu komiwojażera był nazywany heurystycznym , ponieważ nie udowodniono, że mieści się on w 50% optymalnego rozwiązania. Ponieważ jednak zostało to udowodnione, algorytm Christophidesa jest dokładniej określany jako algorytm aproksymacji.

Ze względu na ograniczenia w tym, co mogą robić komputery, nie zawsze jest możliwe efektywnie znaleźć najlepsze możliwe rozwiązanie. Jeśli jest wystarczająca struktura w problemie może istnieć skuteczny sposób na przemierzenie przestrzeni rozwiązania, nawet jeśli przestrzeń rozwiązania jest ogromna(tj. w problemie najkrótszej ścieżki).

Heurystyka jest zazwyczaj stosowana w celu poprawy czasu działania algorytmów, poprzez dodanie "informacji eksperckich" lub "wykształconych domysłów", aby kierować kierunkiem wyszukiwania. W praktyce heurystyka może być również podprogramem dla algorytmu optymalnego, aby określić, gdzie szukać najpierw .

(Uwaga 1) : Dodatkowo algorytmy charakteryzują się tym, czy zawierają elementy losowe czy niedeterministyczne. Algorytm, który zawsze wykonuje ten sam sposób i daje tę samą odpowiedź, nazywa się deterministycznym.

(Uwaga 2) : nazywa się to problemem P vs NP, a problemy, które są klasyfikowane jako np-complete i np-hard, prawdopodobnie nie będą miały 'wydajnego' algorytmu. Uwaga; jak @Kriss wspomniał w komentarzach, są jeszcze "gorsze" rodzaje problemów, które mogą wymagać wykładniczego czasu lub spacja do obliczenia.

istnieje kilka odpowiedzi, które odpowiadają na Część pytania. Uznałem je za mniej kompletne i nie wystarczająco dokładne, i postanowiłem nie edytować zaakceptowanej odpowiedzi udzielonej przez @Kriss

Heurystyka jest zazwyczaj optymalizacją lub strategią, która zazwyczaj dostarcza wystarczająco dobrej odpowiedzi, ale nie zawsze i rzadko najlepszej odpowiedzi. Na przykład, jeśli miałbyś rozwiązać problem komiwojażera za pomocą brutalnej siły, odrzucenie rozwiązania częściowego, gdy jego koszt przekroczy koszt obecnego najlepszego rozwiązania, jest heurystyczne: czasami pomaga, innym razem nie i zdecydowanie nie poprawia teoretycznego (notacja big-oh) czasu działania algorytmu

Myślę, że heurystyka jest raczej ograniczeniem używanym w modelu uczenia się w sztucznej inteligencji, ponieważ przyszłe Stany rozwiązania są trudne do przewidzenia.

Ale wtedy moje wątpliwości po przeczytaniu powyższych odpowiedzi są "W jaki sposób heurystyka może być z powodzeniem stosowana przy użyciu technik optymalizacji stochastycznej? czy mogą one funkcjonować jako pełnowartościowe algorytmy, gdy są używane z optymalizacją Stochastyczną?"

Http://en.wikipedia.org/wiki/Stochastic_optimization

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

Heurystyka to technika, która pomaga szukać odpowiedzi. Its wyniki zależą od przypadku, ponieważ heurystyka mówi tylko jak szukać, nie CO znaleźć. Nie mówi ci, jak dostać się bezpośrednio z punktu A do punktu B; może nawet nie wiedzieć, gdzie punkt A i punkt B jest. W efekcie heurystyka jest algorytmem w stroju klauna. Jest mniej przewidywać-stanie, to jest bardziej zabawne, i przychodzi bez 30-dniowy, gwarancja zwrotu pieniędzy.

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

Oto heurystyka dotarcia do czyjegoś domu: Znajdź ostatnią list, który Ci wysłaliśmy. Przejazd do miasta pod adresem zwrotnym. Kiedy pojedziesz do miasta i zapytasz kogoś, gdzie jest nasz dom. Każdy wie my-ktoś z przyjemnością Ci pomoże. Jeśli nie możesz znaleźć nikogo, zadzwoń do nas z publicznego telefonu, przyjedziemy po ciebie.

Różnica między algorytmem a heurystyką jest subtelna, a dwie kadencje za dużo. Na potrzeby tej książki głównym różnica między tymi dwoma jest poziomem indrection od rozwiązanie. Na algorytm daje instrukcje bezpośrednio. A heurystyka podpowiada, jak odkryć instrukcje dla siebie lub przynajmniej gdzie ich szukać.

Znajdują rozwiązanie nieoptymalne bez żadnej gwarancji co do jakości znalezionego rozwiązania, jest oczywiste, że ma to sens dla rozwoju heurystyki tylko wielomianu. 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 zdolnego do znalezienia przybliżonego rozwiązania w czasie wielomianowym.