ウィキによると、（N-1）かかります！N都市のツアーを計算します。それを行うためのより良い方法を見つけましたが、それをどれだけ改善したかを計算するための計算を行うことはできません. 私の自宅の PC では、20 都市の地図を 1 時間以内に解くことができました。20！= 2.43290200e+18. これが私がしたことです：
N 個の都市 (名前を付けましょう: City(1)、City(2)、City(3)... City(N)) のルートを braut アルゴリズムで検索する場合、最初に次のテストを実行します: City( 1)、City(2)、City(3)、City(4)... City(N)、そしてしばらくしてから、City(1)、City(3)、City(2)、City(4) )...都市(N). 2番目の計算は不要だと主張しています。City(4) ... City(N) の最短ルートを 1 回だけ計算した場合、それを 2 回目の計算に使用して、どのルートがより適切かを判断できます。
このトリックを使用して、K 都市に対して行っている計算の数を次のように減らすことができます: (N - k) これは、誰が最初の都市になるかを示すことができるオプションの数であり、(N - K - 1) を掛けます。 ! これは、残りの都市を選択するために必要なオプションの数であり、完全な計算を実行するために必要な最初の時間を差し引いたものです。なので(N-K)!となります。そして、k = 3 から k = N - 2 までのすべての K について合計する必要があります。
これは私が行った限りです（それほど遠くありません）...これを計算するのを手伝ってくれることを願っています.