これは、友人が最近私に尋ねた興味深い問題/なぞなぞです:
あなたはテニスコートのラインを描いています。直線を描く機械がありますが、一度スイッチを入れると、仕事が終わるまで止めることはできません。明らかに、いくつかの行を 2 回繰り返す必要があります。追加で使用する塗料の最小量は何フィートですか?
コートの寸法:
すべての行の合計は 480 フィートです。たまたま答えが 63 フィート余分 (合計 543 フィート) であることはわかっていますが、これを解決するための最適なアルゴリズムは何かと考えずにはいられません。
これは巡回セールスマンの問題に似ているように見えます。コートの各線はグラフの頂点で表され、コート ラインの接合点はエッジに変換されます。（そうでなければ、線がエッジでコーナーが頂点である場合、すべてのエッジを通過するパスが必要になります。そのためのアルゴリズムはわかりません）。線の接合点を表現する方法についてもっと賢くする必要があるかもしれません.
ただし、問題は十分に小さく、折れ線グラフを通るすべてのパスで総当たりチェックできると思います。それをどのようにコーディングしますか？