Tak więc przynajmniej dwóch profesorów wspomniało, że cofanie się powoduje, że algorytm jest niedeterministyczny, bez podawania zbyt wielu wyjaśnień, dlaczego tak się dzieje. I think Rozumiem, jak to się dzieje, ale mam problem z umieszczeniem go w słowach. Czy ktoś mógłby mi podać zwięzłe wyjaśnienie przyczyny tego?Dlaczego funkcja backtracking powoduje, że algorytm nie jest deterministyczny?
To nie jest tak, że cofnięcie powoduje, że algorytm nie jest deterministyczny.
Zazwyczaj, zazwyczaj potrzebne jest wycofanie w celu przetworzenia niedeterministycznego algorytmu, ponieważ (z definicji niedeterministycznej) nie wiesz, którą ścieżkę zastosować w danym momencie przetwarzania, ale zamiast tego musisz spróbować kilka.
będę tylko cytat wikipedia:
niedeterministyczny język programowania jest język, który może określić, w niektórych punktach w programie (zwane „punkty choice”), różne alternatywy dla przebiegu programu. W przeciwieństwie do instrukcji if-then, metoda wyboru między tymi alternatywami nie jest bezpośrednio określona przez programistę; program musi decydować w czasie pracy pomiędzy alternatywami, za pomocą pewnej ogólnej metody zastosowanej do wszystkich punktów wyboru. Programista określa ograniczoną liczbę alternatyw, ale program musi później wybrać między nimi. ("Wybierz" jest w rzeczywistości typową nazwą dla niedeterministycznego operatora.) Hierarchia punktów wyboru może być uformowana, z wyborami wyższego poziomu prowadzącymi do gałęzi, które zawierają w sobie wybory niższego poziomu.
Jedną z możliwych metod jest system cofania, w którym niektóre alternatywy mogą "zawieść", powodując cofnięcie programu i wypróbowanie innych alternatyw. Jeśli wszystkie alternatywy zawiodą w danym punkcie wyboru, to zawodzi cały oddział, a program przejdzie dalej, do starszego punktu wyboru. Jedną komplikacją jest to, że ponieważ każdy wybór jest tymczasowy i można go przerobić, system musi być w stanie przywrócić stare stany programu przez cofnięcie efektów ubocznych spowodowanych przez częściowe wykonanie gałęzi, która ostatecznie zawiodła.
Z artykułu Nondeterministic Programming.
Gratulacje. Odpowiedź "czytaj wikipedię", która nie sprawiła, że poczułam się zupełnie głupia. :-) –
, który nie czyni systemu nieokreślonym, pójdę z odpowiedzią Marka Harrisona: jest to sposób na symulowanie (teoretyczną) nie-deterministyczną maszynę. – hasen
hasen j, jaki system masz na myśli? backtracking oczywiście może jedynie symulować niedeterminizm, o ile działa na deterministycznym komputerze. najlepszym przykładem jest biblioteka z wyrażeń regularnych. biorą niedeterministyczny opis i muszą przekształcić je w deterministyczne maszyny stanów. –
Rozważ algorytm do kolorowania mapy świata. W sąsiednich krajach nie można używać kolorów. Algorytm zaczyna się arbitralnie w danym kraju i nadaje mu dowolny kolor. Przesuwa się dalej, kolorując kraje, zmieniając kolor na każdym kroku, aż "uh oh", dwa sąsiednie kraje mają ten sam kolor. Cóż, teraz musimy wycofać się i dokonać nowego wyboru koloru. Teraz nie dokonujemy wyboru jako niedeterministycznego algorytmu, który nie jest możliwy dla naszych deterministycznych komputerów. Zamiast tego symulujemy niedeterministyczny algorytm z wycofywaniem. Algorytm niedeterministyczny byłby właściwym wyborem dla każdego kraju.
zobacz moje uwagi na odpowiedź litb – hasen
eksperyment myślowy:
1) ukryta jest jakaś dystrybucja ładunków elektrycznych, które czujesz siłę i zmierzyć z potencjalną pola tworzą. Powiedz mi dokładnie pozycje wszystkich zarzutów.
2) Weź trochę ładunków i ułóż je. Powiedz mi dokładnie, jakie potencjalne pole tworzysz.
Tylko drugie pytanie ma unikalną odpowiedź. Jest to wyjątkowość vector fields. Ta sytuacja może być analogiczna do niektórych niedeterministycznych algorytmów, które rozważasz. Dalej rozważmy w math limits, które nie istnieją, ponieważ mają różne odpowiedzi w zależności od kierunku, w którym zbliżasz się do nieciągłości.
Jeśli zezwolisz na cofanie, zezwalasz na nieskończoną pętlę w twoim programie, co czyni ją niedeterministyczną, ponieważ rzeczywista ścieżka może zawsze zawierać jeszcze jedną pętlę.
-1, co nieskończona pętla ma do czynienia z determinizm ?? – hasen
Non-Deterministic Turing Machines (NDTM) może zająć wiele oddziałów w jednym kroku. Z kolei DTM postępują zgodnie z procesem prób i błędów.
Możesz myśleć o modelach DTM jako zwykłych komputerach. Natomiast komputery kwantowe są podobne do NDTM i mogą rozwiązać problemy niedeterministyczne znacznie łatwiej (np. Zobacz ich zastosowanie w łamaniu kryptografii). Tak więc wycofywanie się byłoby właściwie dla nich procesem liniowym.
Czas działania backtrackingu na deterministycznym komputerze jest silni, tzn. Jest w stanie O (n!).
Gdzie niedeterministyczny komputer może natychmiast odgadnąć poprawnie w każdym kroku, deterministyczny komputer musi wypróbować wszystkie możliwe kombinacje wyborów.
Ponieważ niemożliwe jest zbudowanie niedeterministycznego komputer, co twój profesor prawdopodobnie oznaczało to:
provenly hard problemem w klasie złożoność NP (wszystkie problemy, które non-deterministyczny komputer może rozwiązać skutecznie przez zawsze zgadywanie poprawnie) nie może być efektywniej rozwiązywane na prawdziwych komputerach niż przez cofanie.
Powyższe stwierdzenie jest prawdziwe, jeżeli klasy złożoności P (wszystkie problemy, które deterministyczny komputer może rozwiązać skutecznie) i NP nie są takie same. To jest znany problem P i NP. Instytut Matematyki Clay zaoferował nagrodę w wysokości 1 miliona dolarów za swoje rozwiązanie, ale problem opierał się dowodowi przez wiele lat. Jednak większość badaczy uważa, że P nie jest równe NP.
Prosty sposób podsumowania: Najciekawsze problemy, które niedeterministyczny komputer mógłby rozwiązać skutecznie, zawsze poprawnie zgadując, są tak trudne, że deterministyczny komputer prawdopodobnie wypróbuje wszystkie możliwe kombinacje wyborów, tj. cofanie.
Edytowano, aby zauważyć, że algorytmy są silniejsze niż wykładnicze. –
Pod względem klas złożoności są one wykładnicze (tj. W EXPTIME). Również większość problemów O (n!) Można rozwiązać w O (N^2 * 2^N) za pomocą programowania dynamicznego. Ale jeśli zrozumiesz, łatwiejsze do zrozumienia, niż ze mną w porządku. – mdm
Napisałem biegacza w labiryncie, który używa backtracking (oczywiście), który będę używać jako przykład.
Przechodzisz przez labirynt. Gdy dojdziesz do skrzyżowania, rzucasz monetą, aby zdecydować, którą drogą podążać. Jeśli wybrałeś ślepy zaułek, powróć z powrotem do skrzyżowania i wybierz inną trasę. Jeśli wypróbowałeś je wszystkie, wróć do poprzedniego skrzyżowania. Algorytm ten jest niedeterministyczny, nie z powodu cofania, ale z powodu rzutu monetą.
Teraz zmień algorytm: kiedy dojdziesz do skrzyżowania, zawsze spróbuj najpierw lewostronnej trasy, której jeszcze nie próbowałeś. Jeśli to prowadzi do ślepego zaułku, wróć do skrzyżowania i ponownie spróbuj lewej lewej trasy, której jeszcze nie próbowałeś. Algorytm ten jest deterministyczny. Nie ma żadnej szansy, jest przewidywalna: zawsze będziesz podążał tą samą trasą w tym samym labiryncie.
Podoba mi się analogia labiryntu. Poszukajmy labiryntu, dla uproszczenia, jako drzewa binarnego, w którym istnieje tylko jedna ścieżka.
Teraz chcesz spróbować głębokości pierwszego wyszukiwania, aby znaleźć właściwą drogę z labiryntu.
Komputer, który nie jest deterministyczny, mógłby w każdym punkcie rozgałęzienia duplikować/klonować się i równolegle wykonywać kolejne obliczenia.To tak, jakby osoba w labiryncie kopiowała/klonowała (jak w filmie Prestige) w każdym punkcie rozgałęzienia i wysyłała jedną kopię siebie w lewą podgałęzię drzewa, a drugą kopię siebie w prawy podgłówek drzewo.
Komputery/osoby, które kończą w martwym punkcie umierają (kończą bez odpowiedzi).
Tylko jeden komputer przetrwa (kończy się z odpowiedzią), ten, który wydostanie się z labiryntu.
Różnica między wstecznym a niedeterministycznym jest następująca.
W przypadku cofnięcia jest tylko jeden komputer, który żyje w danym momencie, robi tradycyjny labirynt rozwiązując lewę, po prostu zaznaczając swoją ścieżkę kredą, a kiedy osiąga ślepy zaułek, po prostu wraca do rozgałęzienia punkt, którego podrzędne gałęzie jeszcze nie zbadał całkowicie, tak jak w pierwszym poszukiwaniu głębi.
w przeciwieństwie:
Non komputer deteministic można sklonować siebie w każdym punkcie rozgałęzienia i sprawdzić na drodze poprzez uruchomienie wyszukiwania w gałęziach równoległych względem sub.
Algorytm cofania symuluje/emuluje zdolność klonowania niedeterministycznego komputera na komputerze sekwencyjnym/nierównoległym/deterministycznym.
Powtórzenie nie powoduje, że algorytm jest niedeterministyczny; zmień swoje pytanie. – ShreevatsaR
Dobre pytanie, zadałem sobie to samo pytanie podczas oglądania tego wykładu wideo: http://youtu.be/UBVcV3LIBeU – jhegedus