Algorytmika
Wersja (*.DOC)Praca napisana na lekcje informatyki. Kiepska, ale może komuś się przyda.
md5sum: 860d58ae406d40e3aa6ae0c1009ed7d6 algorytmy.zip
Problem komiwojażera
Zadanie komiwojażera jest koncepcyjnie bardzo proste: komiwojażer musi odwiedzić każde miasto na swoim terytorium dokładnie raz i wrócić do punktu startowego. Przestrzeń rozwiązań w zadaniu komiwojażera jest zbiorem permutacji n miast. Każda permutacja n miast jest rozwiązaniem (które jest pełnym objazdem n miast). Optymalnym rozwiązaniem jest permutacja, dla której koszt objazdu jest najmniejszy. Rozmiar przestrzeni rozwiązań wynosi n.
Zadanie komiwojażera sformułowano dosyć dawno. Było ono zapisane już w 1759 r. przez Eulera (chociaż nie pod tą nazwą), który zajmował się rozwiązywaniem zadania ruchu konika po szachownicy. Prawidłowe rozwiązanie wymagało, aby konik odwiedził każde z 64 pól na szachownicy dokładnie raz w czasie całego ruchu.
Termin "komiwojażer" był po raz pierwszy użyty w 1932 r. w książce niemieckiej Komiwojażer, jak i co powinien on robić, aby wykonane zlecenia i mieć powodzenie w interesach, napisanej przez byłego komiwojażera. Chociaż nie było to głównym tematem książki, zadanie komiwojażera i szeregowanie są omawiane w ostatnim jej rozdziale.
Zadanie komiwojażera w obecnym sformułowaniu wprowadziła RAND Corporation w 1948 r. Jej reputacja pomogła w tym, że stało się ono zadaniem znanym i popularnym. Zadanie komiwojażera także stało się popularne w tym czasie z powodu opracowania nowej metody programowania liniowego i prób rozwiązywania zadań kombinatorycznych.
Ponadto 5 godzin liczenia na komputerze za wiele milionów dolarów, aby znaleźć optymalne rozwiązanie, może nie być najlepsze pod względem kosztu, jeżeli można uzyskać gorsze od niego o kilka procent w sekundy na PC. Z tego powodu wynika potrzeba metod heurystycznych.
W ciągu ostatnich kilku dziesięcioleci powstało kilka algorytmów wyznaczania rozwiązania bliskiego optymalnemu: algorytm najbliższego sąsiada, algorytm zachłanny, algorytm najbliższego wstawiania, najdalszego wstawiania, podwajanego najkrótszego drzewa rozpinającego, oddzielania powłoki wypukłej, krzywej wypełniającej przestrzeń, algorytmy Karpa, Litkego, Christofidesa itp. (w niektórych z tych algorytmów zakłada się, że miasta odpowiadają punktom na płaszczyźnie przy pewnej standardowej metryce). Dana grupa algorytmów (2-opt, 3-opt, Lina-Kernighana) szuka lokalnych minimów - poprawy trasy przez lokalne przestawienia.
Zadanie komiwojażera stało się także celem do rozwiązania w dziedzinie algorytmów genetycznych. Mają one na celu wyszukanie rozwiązania bliskiego optymalnemu za pomocą populacji potencjalnych rozwiązań, które, podlegają pewnym jednoargumentowym i binarnym przekształceniom ("mutacjom" i "krzyżowaniom") za pomocą schematów selekcji biorących pod uwagę dopasowanie osobników.Heurystyka
Wśród algorytmów heurystycznych dużą role odgrywają algorytmy sukcesywnego dołączania węzłów. Algorytmy takie polegają na przedłużaniu trasy częściowej, przebiegającej przez zbiór miast będących podzbiorem zbioru wszystkich n miast. W każdym kroku do trasy dodawane jest nowe miasto, proces ten trwa do chwili aż trasa złożona będzie ze wszystkich miast. Istnieje wiele możliwych strategii dołączania miast np. dołączanie najdalszego miasta, dołączanie najbliższego miasta itp. Dołączenie miasta polega na wstawieniu go do trasy w taki sposób, aby wzrost długości ścieżki wynikający z dodania miasta był jak najmniejszy. Zaletą takiego postępowania jest jego niska złożoność obliczeniowa.
Algorytm dołączania najdalszego miasta od cyklu
O dołączeniu kolejnego miasta do ścieżki decyduje tu jego odległość od najbliższego miasta w cyklu. Dołączamy to miasto, dla którego ta odległość jest największa. Raz dołączone do ścieżki częściowej miasto pozostaje w niej w kolejnych iteracjach aż do końca postępowania. Rozwiązanie uzyskane za pomocą tej metody jest zbliżone do optymalnego.
Najbliższe miasto
Dołączanie najbliżej znajdującego się miasta. Duża szybkość i prostota, ale wyniki marne.Problem ucztujących filozofów
Problem ucztujących filozofów jest klasycznym problemem w dziedzinie programowania współbieżnego. Polega na zsynchronizowaniu działań pięciu filozofów, którzy siedzą przy okrągłym stole, posilają się i rozmyślają. Jest to abstrakcja kilku procesów, wątków które starają się o przydział wspólnie dzielonych zasobów. Problem ten, przedstawiony przez E. Dijkstrę, polega na zsynchronizowaniu czynności życiowych pięciu filozofów, na które składają się myślenie i jedzenie.
Chcąc jeść, każdy filozof musi podejść do swojego miejsca przy okrągłym stole, na którym znajduje się rozłożonych po pięć talerzy i widelców. Ponieważ jednak jedyną potrawą jest spaghetti, do jedzenia którego są wymagane po dwa widelce, każdy filozof chcąc rozpocząć jedzenie musi sięgnąć po prawy i lewy widelec. Z tego wynika, że może dochodzić tu do sytuacji konfliktowych, jednocześnie nie może jeść nigdy dwóch sąsiadów przy stole, a synchronizacji musi podlegać dostęp do zasobów, jakimi są widelce. Podnosząc leżące przy nim widelce filozof uniemożliwia jedzenie swoim sąsiadom.
Założenia: filozof, musi mieć w danej chwili dwa widelce, żaden z 5 filozofów nie będzie czekał w nieskończoność, jeśli filozof podniósł już oba widelce, to w skończonym czasie naje się i odłoży je na stół, rozwiązanie nie może wyróżniać żadnego z filozofów (algorytmy wszystkich pięciu filozofów dotyczące podnoszenia i odkładania muszą być takie same).
Rozwiązanie z możliwością zakleszczenia
Jest to najprostsze rozwiązanie tego problemu. Polega ono na sekwencyjnym podnoszeniu widelców przez zgłodniałego filozofa. Po najedzeniu odkłada oba widelce na stół. Z punktu widzenia jednego filozofa jest to rozsądne postępowanie. Jednak ponieważ wszyscy oni postępują tak samo, łatwo wyobrazić sobie można sytuację, choć bardzo mało prawdopodobną, w której każdy chwyci za swój prawy widelec i będzie czekać na to, aż jego lewy sąsiad skończy jeść i odłoży widelec, może to nigdy nie nastąpić, gdyż lewy sąsiad czeka na to samo zdarzenie. Jest to typowy przykład zjawiska zakleszczenia, w którym uczestniczą wszystkie współdziałające procesy.
Rozwiązanie asymetryczne
Rozwiązanie to jest podobne do pierwszego rozwiązania. Różnica polega na kolejności podnoszenia widelców. Filozof o parzystym numerze podnosi najpierw widelec prawy a potem lewy, nieparzysty odwrotnie. Algorytm ten zapewnia niewystępowanie zakleszczeń, ale nie chroni przed głodzeniem. np.: Jeśli filozof A czeka na widelec. Właściciel widelca B może go odłożyć, ale nie jest zagwarantowane, czy filozof A go weźmie jeśli filozof B będzie chciał znowu jeść. Drugim problemem jest brak równości filozofów. Ponieważ filozof czwarty nie ma z kim konkurować o pierwszy widelec jest on najkrócej blokowany.
Rozwiązanie z lokajem
Okazuje się że sami filozofowie nie są w stanie rozwiązać problemu odżywiania się. Potrzebny jest jakiś zewnętrzny arbiter, rozstrzygający wedle ustalonego warunku w określonych sytuacjach. Arbitrem takim może być np. lokaj, który będzie dbał o to, aby w każdej chwili co najwyżej czterech filozofów konkurowało o widelce. Można łatwo wykazać, że wówczas przynajmniej jeden z nich mógł podnieść oba widelce i jeść.
Rozwiązanie z monitorem
Rozwiązanie to polega na tym że głodny filozof podnosi widelce gdy obydwa są wolne. Jeśli któryś z widelców jest zajęty to czeka. Rozwiązanie to nie jest całkowicie poprawne ponieważ może dojść do zagłodzenia któregoś z filozofów.
Problem prysznica hotelowego
Założenia: w hotelu są pokoje a w pokojach prysznice. Każdy gość hotelu musi wziąć prysznic, ale tylko jeden może się myć w danej chwili. Umycie się zajmuje skończoną ilość czasu. Zadanie da się rozwiązać za pomocą dwóch pracujących współbieżnie procesów. Problem polega na takim napisaniu algorytmu aby każdy z procesów mógł wykonać kod z sekcji krytycznej, ale żaden nie mógł tego robić kiedy drugi wykonuje te instrukcje. Należy uwzględnić problem zagłodzenia, który pojawia się, gdy jeden proces chce wejść do sekcji krytycznej, ale drugi stale się mu to uniemożliwia, oraz problem zastoju występujący wtedy, gdy żaden z procesów nie może dalej działać.
Konieczne jest wprowadzenie zmiennej która będzie przechowywać informacje, czy sekcja krytyczna jest wykonywana. Jeżeli jej stan wskazuje na możliwość wykonania, proces zapisuje do zmiennej informacje na temat wykonywania sekcji krytycznej a pod jej koniec znów ustawia ją na poprzednią wartość.
"We have a system that increasingly taxes work and subsidizes nonwork." - Milton Friedman
Last update: Wednesday, 11th October, 2023 Copyright © 2001-2024 by Lukasz Tomicki |