[mk321]

#programowanie #algorytmika

Problem komiwojażera (ang. travelling salesman problem, TSP).
Dla zwykłego algorytmu brute-force złożoność obliczeniowa to: O(n!).

Ale to jest dla symetrycznego (STSP) czy asymetrycznego (ATSP)? Załóżmy, że O(n!) jest dla symetrycznego. To jeśli w asymetrycznym jest dwa razy tyle do policzenia, to złożoność obliczeniowa asymetrycznego to będzie (O(2*n!)?

I nie rozumiem czemu n!? Przecież jak robię permutacje, to biorę tylko te wyniki, które zaczynają się od punktu startowego, czyli jest ich mniej. Czyli wychodziłoby, że:
- dla symetrycznego: O((n-1)!),
- dla asymetrycznego: O(2*(n-1)!).

Dobrze myślę? Nigdzie nie mogę znaleźć potwierdzenia tego ;/

[tell_me_more]

@mk321: O(2*n!)=O(n!)=O(100*(n+100)!)

[edgar_k]

Przecież jak robię permutacje, to biorę tylko te wyniki, które zaczynają się od punktu startowego, czyli jest ich mniej.

@mk321: przy zalozeniu, ze polowa nie wychodzi z punktu startowego. W ogolnym zalozeniu - tak nie jest.

[mrowkojad04]

@mk321: O(n!) to nie jest złożoność, tylko rząd złożoności

[luki-p]

@mk321: O(n!) = O(2*n!) = O((n-1)!) = O(2*(n-1)!)

[mk321]

@tell_me_more: @luki-p: @mrowkojad04: aha, czyli to jest po prostu "rząd" złożoności. Jak jest silnia, to jest już O(n!) i nie podaje się dokładnie, bo to prawie bez różnicy. Dlatego wszędzie jest O(n!), mimo że w rzeczywistości troszkę się różnią. Dzięki!

@edgar_k: nie rozumiem. Zakładam, że jest połączenie każdy z każdym.

Dla 3 punktów jest permutacji 6 (czyli 3!). Ale biorę tylko

[tell_me_more]

@mk321: nom. Dla odpowiednio dużego n zawsze algorytm n! będzie wolniejszy niż algorytm n^2, nieważne, jakie stałe stoją obok.

Jeśli Ci to na studia potrzebne to jeszcze ogarnij dokładny zapis, bo tak naprawdę to tam jest kilka oznaczeń - mała omega, duża omega, mała theta i duża theta i znaczą coś trochę innego. W praktyce używa się O(..n..) i tyle, ale na studiach trza być precyzyjnym.