Strona główna » Algorytmy » Artykuły » Najkrótsza droga
 

Najkrótsza droga

https://mattomatti.com/a97

Zadanie

Znajdź najkrótszą drogę pomiędzy punktem początkowym, a końcowym. Ruch odbywa się wzdłuż prostej. Prawidłowy ruch to taki, który odbywa się k kroków do przodu lub do tyłu. W i-tym kroku należy wykonać i kroków. Za punkt początkowy przyjmij a = 0. Punkt końcowy b > 0, powinien zostać wczytany od użytkowania. Wypisz komunikat na ekran czy istnieje szansa, aby osiągnąć punkt. Jeśli tak to podaj dodatkowo w ilu krokach można tego dokonać.

Przykład

Rozpatrzmy na początek trywialny przykład dla b = 3. Wtedy, aby osiągnąć cel wystarczą tylko dwa kroki. Pierwszy o 1 krok, a drugi o 2. Załóżmy teraz, że b = 4. Nie jest to trywialny przypadek, ponieważ należy najpierw wykonać krok do tyłu, aby następne dwa kroki wykonać do przodu. Wtedy -1 + 2 + 3 = 4. Ten sam punkt można też osiągnąć wykonując 4 kroki: do tyłu, do tyłu, do przodu i do przodu, matematycznie -1 + -2 + 3 + 4 = 4.

Implementacja

Założenia

Rozwiązanie będzie algorytmem rekurencyjnym. Podczas dowolnego ruchu do wyboru są zawsze dwie możliwości. Podczas wywołania rozpatrzone zostaną obie możliwości, ale zwrócona zostanie mniejsza wartość. Pozostaje teraz tylko ustalić kiedy należy przestać szukać rozwiązania. W algorytmie zostało uznane, że jeśli aktualna pozycja jest większa od celu to algorytm ma zwrócić, że aktualnie sprawdzany ciąg kroków nie będzie optymalny. Dotyczy to również ujemnej pozycji. Jej odległość od punktu 0 musi być mniejsza od punktu docelowego.

Rozwiązanie (nie zawsze optymalne)

Warto zauważyć, że maksymalna ilość kroków do wykonania to 2n, gdzie n to liczba osiągnięcia. Wynika to z faktu, że wykonując na przemian krok do tyłu, krok do przodu przybliżamy się do celu o dokładnie jeden krok. Innymi słowy zawsze istnieje możliwość osiągnięcia celu.

Funkcja pomocnicza

Ze względu na wybieranie pomiędzy najkrótszą i najdłuższą trasą to potrzebna jest funkcja, która z dwóch danych wartości zwróci krótszą. Zadanie to realizuje funkcja min().

  1. int min(int a, int b) {
  2.   return (a < b) ? a : b;
  3. }

Wyszukiwanie rozwiązania

Funkcja ileKrokow() przyjmuje trzy argumenty: cel - punkt do osiągnięcia, od - punkt z którego rozpoczynany jest ruch oraz kroki - ile kroków zostało wykonanych. Jest to również ilość kroków jaką można wykonać w tym wykonaniu. Dwa argumenty od i kroki są opcjonalne, ponieważ punkt początkowy i początkowa ilość kroków jest zawsze znana.

  1. int ileKrokow(int cel, int od = 0, int kroki = 0) {
  2.   if (abs(od) > (cel))
  3.     return INT_MAX;
  4.   if (od == cel)
  5.     return kroki;
  6.   int ruchp = ileKrokow(cel, od + kroki + 1, kroki + 1);
  7.   int ruchl = ileKrokow(cel, od - kroki - 1, kroki + 1);
  8.   return min(ruchp, ruchl);
  9. }

(2.) Sprawdź czy nie znaleźliśmy się poza maksymalnym zasięgiem ruchu. Jeśli tak to (3.) zwróć INT_MAX co będzie sygnałem, że poprzednie wywołania nie prowadzą do żadnego sensownego rozwiązania. (4.) Jeśli osiągnęliśmy cel to (5.) należy zwrócić ile kroków zostało wykonanych. W przeciwnym wypadku pozostaje (6., 7.) wywołać obydwa przypadki możliwych ruchów, a następnie (8.) zwrócić mniejszą wartość z wyliczonych.

Testowanie funkcji

Poniższa funkcja main() poprosi użytkownika o wprowadzenie punktu do osiągnięcia, a następnie wypisze na ekran czy punkt można osiągnąć i w ilu krokach.

  1. int main () {
  2.   int cel;
  3.   cout << "Podaj cel do osiagniecia: ";
  4.   cin >> cel;
  5.   int krokow = ileKrokow(cel);
  6.   if (krokow == INT_MAX) {
  7.     cout << "Nie mozna osiagnac celu";
  8.   } else {
  9.     cout << "Potrzebnych krokow " << krokow;
  10.   }
  11.   cout << endl;
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz program, który dla wprowadzonego punktu końcowego. Wypisze na ekran wszystkie możliwe układy kroków, które pozwolą na osiągnięcie celu. Program powinien na koniec wypisać ile różnych dróg. Wskazówka: skorzystaj z faktu, że potrzeba maksymalnie 2n kroków, aby osiągnąć n-ty punkt.

Przykładowo dla podania wartości 3 zostanie wypisane na ekran:

  1. 1 2
  2. 1 -2 3 -4 5
  3. -1 2 -3 4 -5 6
  4. wszystkich drog: 3

Ze względu na fakt, że dla coraz dalszej drogi jest coraz więcej możliwych dróg, dlatego nie jest zalecane testowanie dla bardzo dużych n.