### Human: 歴代の巡回セールスマン問題の歴史を簡潔に箇条書きにすると？### Assistant: * 19世紀、アイルランドの数学者ウィリアム・ローワン・ハミルトンとイギリスの数学者トーマス・カークマンによって初めて数学的に定式化されるでござる。
* 1930年代 - ウィーンの数学者とハーバード大学で初めて研究され、特にカール・メンガーとメリル・M・フラッドがスクールバスの経路問題を解決するために研究したでござる。
* 1959年 - ジリアン・ビアードウッド、J.H.ハルトン、ジョン・ハマースリーが、ケンブリッジ哲学協会誌に「The Shortest Path Through Many Points」と題する論文を発表し、最初の実用的な解決策を提供するでござる。
* 1960年代 - 新しいアプローチで、長さが最適長さの倍数で証明可能な解を生成でござる。
* 1972年 - リチャード・M・カープがハミルトンサイクル問題がNP完全であることを示し、巡回セールスマン問題がNP困難であることを示唆するでござる。
* 1976年 - ChristofidesとSerdyukovがそれぞれ新しいアルゴリズムを考案し、最悪の場合、最適解の1.5倍以上の長さの解を得るでござる。
* 1990年代 - Applegate, Bixby, Chvátal, and Cookは、最近の多くの記録解に使用されているプログラムConcordeを開発しましたでござる。
* 1991年 - Gerhard ReineltがTSPLIBを発表、様々な難易度のベンチマークインスタンス集で、多くの研究グループによって結果比較に利用されている
* 2006年 - マイクロチップレイアウト問題で与えられる85,900都市のインスタンスで、現在TSPLIBで最大の解を持つインスタンスで最適なツアーを計算したでござる。
* 2011年 - グラフィカルな巡回セールスマン問題の部分集合に対して、わずかに改良された近似アルゴリズムが開発されるでござる。
* 2020年 - 「グラフィカル」巡回セールスマン問題のサブセットで開発された近似アルゴリズムが、完全な巡回セールスマン問題をカバーするように拡張されるでござる。