組合せ最適化における最先端アルゴリズムと機械学習30分程度の動画なので夕食を見ながら食べるのに最適です。 ================================================ Vertex Coverと巡回セールスマン問題はどちらも非常に研究の歴史が長いNP-hard問題です。 これらの問題には多項式時間アルゴリズムが存在しないと考えられているにも関わらず、最先端のソルバは数万頂点のインスタンスにさえ、厳密解を与えることがあります。 それとは別に、近年、機械学習によってこうした離散最適化問題を解こうとする試みが生まれています。機械学習によるアプローチの難しさはどうしたところから生まれるのかを皆さんにも考えていただきたいです。
