Tekintsük az alábbi Utazó ügynök problémát (TSP):

Adva van n

város, illetve az útiköltség bármely két város között.

Keressük a legolcsóbb utat egy adott városból indulva, amely minden

várost pontosan egyszer érint, majd a kiindulási városba ér vissza.

Tekintsük a legkézenfekvőbb megoldást, amikor is az összes lehetőséget végignézzük, és a legkisebb súlyú körutat választjuk ki.

10 db város esetén, hány ilyen utat kell megnéznünk?