取り組み内容

BHH定理という巡回セールスマン問題に関する定理について、プログラミングを使った実験と近似解法の精度について

結果

巡回する地点の数が少ないとき、BHH定理は成り立たないが、地点の数が大きくなるほどBHH定理に従う。

貪欲法という、今いる地点から最も近い地点に向かうという近似解法では、地点数が少ないとき最短巡回路の約1.1倍の経路を示すことがわかった。

感想

自分の興味があることなので、やっていて楽しかったが、自分の思い通りにいかないことも多く、嫌になることもあった。
失敗を経て成功につながったときはとても嬉しかった。