Witam,
Ostatnio miałem pewne zadanie, a mianowicie:
"Która z klas algorytmów będzie najodpowiedniejsza a która najgorsza do rozwiązania problemu konika szachowego oraz która dla problemu kasjera?."
Do wyboru mam następujące klasy:
-algorytm siłowy
-zachłanny
-dziel i zwyciężaj
-z powrotami
Jak według was będzie wyglądało rozwiązanie? Dzięki.
Knight's tour - dziel i zwyciężaj - najlepsza, siłowa - najgorsza
polecam Google, to nie boli ;)
Ja to ręcznie robiłem i wystarczyło się ustawić na dowolnym zewnętrznym polu i po każdym całym okrążeniu schodzi w głąb do środka taką spiralą do wnętrza.
alexaa napisał(a):
dziękuję, a co w przypadku problemu kasjera?
Ja ten problem rozwiązałem jak robiłem na kasie xd
Najpierw wydajesz największe nominały, bo z mniejszych zawsze zrobisz większy aż ci się skończą monety.
tak rozumiem zasadę działania, ale która klasa będzie najlepsza / najgorsza?
alexaa napisał(a):
a co w przypadku problemu kasjera?
jedynym problemem kasjera jest to, aby nie było manka ;>
czy gdy mamy w problemie kasjera system monetarny 10 5 2 1 i reszty całkowite coś to zmienia? (rodzaj klasy algorytmu)
No zmienia, jak mamy system monetarny taki jak w Polsce na przykład to algorytm zachłanny jest okej, ale w ogólnym przypadku wydawanie reszty jest NP-hard.
ok, zachłanny sobie poradzi z problemem kasjera, a który algorytm jest w tym przypadku najgorszy?
alexaa napisał(a):
ok, zachłanny sobie poradzi z problemem kasjera, a który algorytm jest w tym przypadku najgorszy?
Nie oczekuj gotowych odpowiedzi, poza tym chyba średnio rozumiesz odpowiedź - problem kasjera dla wybranych nominałów da się rozwiązać metodą zachłanną, ale w ogólności to siłowa.
Rozważanie co jest najgorszym algorytmem jest bez sensu, to tak jakby pytać się co jest najgorszym algorytmem sortowania - jeden rzuci, że przez permutacje jest słabe, ale istnieją przecież gorsze. Poza tym jestem jednak ciekaw jak zaimplementować rozwiązanie kasjera np. poprzez nawroty.
Jak jest pytanie ktory algorytm jest najlepszy dla monet 10 5 2 i reszt całkowitych to rowniez zachlanny?
o_O algorytm wydawania reszty można rozwiązać zachłannie czasami, a jeśli nie to dynamicznie. brute-force nigdy nie jest potrzebny.
Dużo mądrych rzeczy powiedziano o algorytmie najlepszym, ale w tym zadaniu ważne jest też wskazanie najgorszego. Najgorsza klasa algorytmów to taka, która w ogóle nie nadaje się do rozwiązania danego problemu. Dla konika jest to zachłanny, a dla kasjera - dziel i zwyciężaj.
Przeczytałem link @ekhart -a, ale tam pisze, że dziel i zwyciężaj nie zawsze zadziała. Czyli podobnie jak z kasjerem.
jarekczek napisał(a):
Dużo mądrych rzeczy powiedziano o algorytmie najlepszym, ale w tym zadaniu ważne jest też wskazanie najgorszego. Najgorsza klasa algorytmów to taka, która w ogóle nie nadaje się do rozwiązania danego problemu. Dla konika jest to zachłanny, a dla kasjera - dziel i zwyciężaj.
Przecież liniowy algorytm dla konika jest od dawna znany.
Tam wystarczy skakać po 'minimalnej ścieżce',
znaczy następne pole wybieramy zawsze to, do którego jest najmniej wejść z innych pól.