Na wykładzie pojawił się „Problem komiwojażera”. Proszę przeczytać w Wikipedii opis
problemu. Brutalne (siłowe) rozwiązanie polega na sprawdzeniu wszystkich
możliwości. Jeśli komiwojażer ma odwiedzić N miast to jest N! możliwych tras jego
podróży. Szukamy oczywiście najkrótszej. Załóżmy, że komputer w czasie 1 sekundy
analizuje milion (1e6) możliwych tras komiwojażera. Dla ilu miast (czyli jak dużego N)
możemy rozwiązać problem w ciągu godziny, dnia, roku albo w czasie całego
istnienia wszechświata


Odpowiedź :

Czas - zamiana jednostek, silnia - przybliżenie, optymalizacja.

  1. Zacznijmy od zamiany długości okresów czasowych na sekundy:
    - godzina [tex]60\cdot 60 s =3600s = 3,6 \cdot 10^3 s[/tex]
    - dzień [tex]24 \cdot 3600 s = 86400s = 8,64 \cdot 10^4 s[/tex]
    - rok [tex]365 \cdot 86400s = 31536000s \approx 3,15 \cdot 10^7 s[/tex]
    - istnienie wszechświata [tex]1,4 \cdot 10^{10} \cdot 3,15 \cdot 10^7 s \approx 4,41 \cdot 10^{17}s[/tex]
  2. Co daje nam w tych okresach możliwość analizy odpowiednio:
    - godzina: [tex]3,6 \cdot 10^9[/tex] przypadków
    - dzień: [tex]8,64 \cdot 10^{10}[/tex] przypadków
    - rok: [tex]3,15\cdot 10^{13}[/tex] przypadków
    - istnienie wszechświata: [tex]4,41 \cdot 10^{23}[/tex] przypadków
  3. Porównując wartości silni kolejnych liczb naturalnych z powyższymi dostajemy, że:
    - godzina: [tex]N=12[/tex]
    - dzień: [tex]N=13[/tex]
    - rok: [tex]N=16[/tex]
    - istnienie wszechświata: [tex]N=23[/tex]

Korzystając ze wzoru Stirlinga można dodatkowo wygodnie przybliżyć silnie dla dużych wartości [tex]n[/tex]:
[tex]n! \approx \left( \frac{n}{e} \right)^n \sqrt{2 \pi n[/tex]
lub w postaci logarytmicznej:
[tex]\ln n! \approx n \ln n -n[/tex]