Odpowiedni algorytm dla konika szachowego.

0

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.

0

Knight's tour - dziel i zwyciężaj - najlepsza, siłowa - najgorsza
polecam Google, to nie boli ;)

0

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.

0

dziękuję, a co w przypadku problemu kasjera?

0
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.

0

tak rozumiem zasadę działania, ale która klasa będzie najlepsza / najgorsza?

0
alexaa napisał(a):

a co w przypadku problemu kasjera?

jedynym problemem kasjera jest to, aby nie było manka ;>

0

czy gdy mamy w problemie kasjera system monetarny 10 5 2 1 i reszty całkowite coś to zmienia? (rodzaj klasy algorytmu)

0

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.

0

ok, zachłanny sobie poradzi z problemem kasjera, a który algorytm jest w tym przypadku najgorszy?

0
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.

0

Jak jest pytanie ktory algorytm jest najlepszy dla monet 10 5 2 i reszt całkowitych to rowniez zachlanny?

0

Nie, wtedy najlepszy to siłowy

0

Dziekuje.

1

o_O algorytm wydawania reszty można rozwiązać zachłannie czasami, a jeśli nie to dynamicznie. brute-force nigdy nie jest potrzebny.

0

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.

1
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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1