Do tej pory na blogu miałem okazję pokazać dwa ciekawe problemy obliczeniowe: problem skoczka szachowego oraz zliczania unikalnych elementów. Omawiając je (i nie tylko), wspominałem o innym, może i najbardziej znanym — problemie komiwojażera. Czytaj dalej, aby dowiedzieć się, o co w nim chodzi, jak możemy go rozwiązać, dlaczego na okładce jest listonosz, a także co ma wspólnego z grafami. Tak, niemal równo po dwóch latach wracam na blogu do tematyki grafów.

W świecie informatyki mamy wiele znanych problemów obliczeniowych, takich jak problem komiwojażera, które z jednej strony mają praktyczne zastosowania, a z drugiej stanowią idealny przykład do nauki algorytmów heurystycznych. Dzisiaj chciałem pokazać mniej znany z problemów, który, nawet mogłoby się wydawać na pierwszy rzut oka, problemem nie jest — zliczanie unikalnych elementów. Opowiem, dlaczego jest to problem, gdzie ma zastosowania i pokażę do niego przykładowe podejście algorytmiczne.

Problem skoczka szachowego to jeden z popularniejszych problemów algorytmicznych. Często możemy go spotkać pośród zadań z algorytmiki dla adeptów programowania. Zobaczmy, na czym ten problem polega oraz jak go rozwiązać, i przede wszystkim... co ma to wspólnego z szeroko opisywanym przeze mnie ostatnio tematem grafów.