ユークリッド距離 (paizaランク D 相当)

この問題集では、巡回セールスマン問題を扱います。

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。
英語では Traveling Salesman Problem と呼ばれており、この頭文字を取ってTSPと表記することもあります。
TSPはNP困難という複雑性クラスに属しており、効率よく(= 問題サイズの多項式時間で)解くことがほとんどできない問題だろうとされています。
この問題集では、巡回セールスマン問題に対する厳密解法、近似解法、発見的解法(ヒューリスティクス)を学んでいきます。

この問題集では、各都市は二次元平面上の点とします。都市間の距離にはユークリッド距離を用いることにします。点 (x_1, y_1) と点 (x_2, y_2) のユークリッド距離は、√((x_1-x_2)^2 + (y_1-y_2)^2)です。
まずは手始めに、2 点間のユークリッド距離を計算してみましょう。