Z Wikipedii

[edytuj] Backtracking

Fragment usnięty

"..., które nie są jednocześnie silnie NP-trudne. Z reguły jest łączona z metodą backtrackingu, służącą do selekcji elementów, które tworzą rozwiązanie problemu. Backtracking polega na wstecznym przeglądaniu tablicy wygenerowanej przez algorytm programowania dynamicznego w celu wskazania podproblemów, które były brane pod uwagę, przy tworzeniu rozwiązania końcowego, dzięki czemu można stwierdzić, czy rozpatrywany element był uwzględniany w rozwiązaniu optymalnym, czy nie."

Mam co do niego różnorakie zastrzeżenia, zwłaszcze moje rozumienie backtrackingu zupełnie nie przystaje do tego jak znajduje się rozwiązanie optymalne (wstecz) w programowaniu dynamicznym. Wazow 23:49, 17 mar 2006 (CET)

Mógłbyś przybliżyć o co dokładnie chodzi? Bo fragment wydaje mi się OK VindicatoR ۞ 01:09, 18 mar 2006 (CET)

Zaznaczam, że mogę się mylić i nie szukałem jeszcze w źródłach. Moim zdaniem backtracking to zasada stosowana w algorytmach typu "Search" (np. Branch-and-Bound, Min-Max, A*). W momencie gdy poszukiwanie stwierdza, ze nie da sie uzyskac wartosci optymalnej, lub spelniajacej wymagania zadania, to wycofuje sie wstecz i szuka w innym miejscu. Programowanie dynamiczne dokladnie wlasnie tego nie robi. Nie ma zadnego wyszukiwania wstecz. Wręcz nie ma wyszukiwania. Jest rozwiązywanie podproblemów bottom-up. Nawet, zeby odtworzyc wartosc, ktora optymalizuje funkcje celu niczego się szuka. Wprost przeciwnie zostawia sie informacje o sladzie podczas optymalizacji i odczytuje sie ten ślad wstecz. To jest proste odczytanie listy wstecz po zakonczeniu optymalizacji, a nie wycofywanie sie, zeby szukac dalej od innego miejsca (backtracking). Istnieje minimalna szansa, że backtracking oznacza więcej niż myślę i wówczas akapit jest poprawny, ale trudno mi w to na razie uwierzyć że przez tyle lat znajomości tematu umknęło to mojej uwadze. Zamierzałem poczekać na opinie i poszukać bardziej ścisłych definicji backtrackingu. Wazow 11:18, 18 mar 2006 (CET)

Backtracking jest na 100% używany w programowaniu dynamicznym, to mogę powiedzieć z całą odpowiedzialnością (przynajmniej na podstawie tego, co się naumiałem na politechnice :)). W B&B, M-M i A* mamy również backtracking, ale poza nazwą nie ma on związku z artykułem, nad którym dyskutujemy. VindicatoR ۞ 11:34, 18 mar 2006 (CET)

Czyli sugerujesz, że backtracking ma dwa znaczenia? Angielska wikipedia zna tylko to, które ja znam (en:backtracking). Wazow 15:32, 18 mar 2006 (CET)

A oto dowody na to, że backtracing może pozostać w artykule - na początek : folie z wykładów z algorytmiki na Politechnice Wrocławskiej (strona 148) VindicatoR ۞ 11:41, 18 mar 2006 (CET)

Czy Ty chcesz żebym czytał 230 slajdów? Może chociaż określ w przybliżeniu gdzie. (Na marginesie: Obawiam się jednak, że będziemy potrzebowali silniejszych argumentów niż slajdy, coś jak klasyczny podręcznik algorytmów, albo jakieś poważane prace naukowe. Sam jestem nauczycielem i wiem, że na moich slajdach było wiele nieścisłości. Jeśli masz Cormena, to zobacz. Ja będę miał dostęp do książek dopiero w środę i wtedy moge sprawdzić czy w rozdziale Dynamic Programming wspominany jest backtracking.)

Ale i tak mi powiedz gdzie mam szukać w tych slajdach, bo jestem ciekawy :) Wazow 15:32, 18 mar 2006 (CET)

No przecież napisałem, strona 148 ;) VindicatoR ۞ 15:41, 18 mar 2006 (CET)

Sorry, już nie te oczy :( Wazow 15:53, 18 mar 2006 (CET)

Rzeczywiście stoi jak wół "backtracking" na tych slajdach. Poszukałem po sieci, czy to nie jest przypadkiem jakaś lokalna nazwa wśród studiujących knapsack, ale nic nie znalazłem. Wprost przeciwnie, backtracking jest stawiany w opozycji do programowania dynamicznego (np. [1], szukaj backtracking). Mam obecnie dostęp tylko do drugiego garnituru podręczników do algorytmów. Przejrzałem pokrótce indeksy i przekartkowałem rozdziały o programowaniu dynamicznym. Nigdzie nie znalazłem (na szybko) podobnych stwierdzeń:

• Goodrich. Tamassia. Data structures and Algorithms in Java, wprowadza programowanie dynamiczne, a w indeksie nie ma słowa backtracking.
• Levitin. Introduction to The Design and Analysis of Algorithms, wprowadza backtracking do rozwiązywania problemów trudnych, kilka rozdziałów po zakończeniu prezentacji programowania dynamicznego.
• Rabhi. Lapalme. Algorithms. A Functional Programming approach wprowadzają backtracking kilka rozdziałów przed programowaniem dynamicznym w kontekście searchow i nie wspominają o żadnym związku między tymi dwoma tematami.
• Harel. Algorithmics: The Spirit of Computing, również nie wspomina backtracking w kontekście programowania dynamicznego (ale tutaj może to wynikać z bardzo pobieżnej prezentacji tego ostatniego).
• Z polskiego podwórka mam Banachowski. Diks. Rytter. Algorytmy i struktury danych. Również nie ma śladu backtrackingu (ale również bardzo krótka prezentacja - jedna strona).
• Z poważnych pozycji mam obecnie dostęp tylko do Hromkovic'a "Algorithmics for Hard Problems" i nie widzę tam backtrackingu, choć używa knapsacka do wprowadzenia programowania dynamicznego tak jak te slajdy. Backtracking jest wspomniany wielokrotnie w innych rozdziałach. Hromkovic zajmuje sie jednak w swojej ksiazce problemami dla ktorych programowanie dynamiczne i tak jest za wolne lub sie nie nadaje. Definitywnie moze miec wiec skrzywienie w rozumieniu czym backtracking jest a czym nie jest.

Może wykładowca się pomylił? A może to jest literówka? "Backtracing" byłoby w porządku, choć to termin niezbyt kanoniczny. Może trzeba go/jej po prostu spytać? (jeśli masz jeszcze kontakt) Wazow 16:36, 18 mar 2006 (CET)

Wykładowca się na pewno nie pomylił tym bardziej, że nie był pierwszym, od którego słyszeliśmy o backtrackingu (a na Politechnice Wrocławskiej raczej totalnych bzdur nie uczą...). Być może jest to po prostu identyczne określenie dwóch zupełnie różnych rzeczy (PD i B&B/A*)? VindicatoR ۞ 21:05, 20 mar 2006 (CET)

Nie sugeruję wcale, że Was bzdur uczą. Jednak pomyłki wykładowców zdarzają się wszędzie. Nie należy ich (wykładowców) demonizować. To, że słyszałeś o backtrackingu również, gdzie indziej to raczej wspiera moje rozumowanie niż Twoje. Przecież backtracking jest niezmiernie ważną techniką, tylko jakoś nie pasuje mi do programowanie dynamicznego. Jestem chętny dać się przekonać, że powinien się tu znaleźć, ale potrzebuję twardych argumentów. W nauce liczy się coś co można zacytować, i najlepiej nie jakaś podrzędna publikacja. Artykuł, podręcznik, konferencja. Coś takiego zamknęłoby mi usta. Wówczas nawet jeśli byłbym nadal wątpiący to moglibyśmy napisać "wg [referencja] technika ta nazywa się backtracking", zrzucając z nas odpowiedzialność. Slajdów raczej się nie cytuje. Najlepiej coś, co jest w bibliotekach. Jak widzisz szukałem, ale na razie bez sukcesów. Wazow 21:22, 20 mar 2006 (CET)

[edytuj] Kategoria

Mój (delikatny i niepewny) sprzeciw budzi też umieszczenie programowania dynamicznego w kategorii Algorytmy. Programowanie dynamiczne nie jest algorytmem per se. Zauważyłem jednak, że w kategorii algorytmu jest dużo śmieci (czyt. niealgorytmów). Są pojęcia matematyczne jak rekursja, albo problemy jak Problem najkrótszej ścieżki, kurioza jak iteracja, artykuły o teorii złożoności, etc. Zatem pewnie nie programowanie dynamiczne ma problem, ale kategoria Algorytmy powinna zostać przemyślana (co najmniej nazwa). Wazow 21:32, 20 mar 2006 (CET)