2021-枝がり-解説
- 考案国：ウズベキスタン
- 正解
- この図の赤色の枝を切り落とす 20 が正解です。
- この図の赤色の枝を切り落とす 20 が正解です。
- 説明
- 具体的に考えてみましょう。
- 左側の枝を考えると、葉が付いている細い枝を切ると「3+1」と「3+1」になります。「3+1」の代わりに5の枝を切ることもできますが、「3+1」のほうが4の時間で切れるので、5の枝を切るより短い時間で済むことがわかります。また、いちばん太い9の枝を切ることもできますが、細い枝を4本切ると「3+1+3+1」で8になるので、9の枝を切るより短い時間で済むことがわかります。
- 次に、上側の枝を考えると、左の2本を「3+5」で切るよりも、根本の4を切ったほうが短い時間で済むことがわかります。右の2本は「2+1」で3になりますので、根本の5を切るより短い時間で済むことがわかります。
- 最後に右側の枝を考えると、3本を「3+2+1」で切るよりも、根本の5を切ったほうが短い時間で済むことがわかります。
- 実際のコンピュータでは
- 木構造はコンピュータ科学で重要なデータ構造です。
- 庭の木を木構造として考えることで、この問題は、根からすべての葉を分離するための、枝の最小の重みを求める問題として考えることができます。
- これはミニマルカット（略してmin-cut）と呼ばれるグラフ理論の標準的な問題で、様々な標準的なアルゴリズム（例えばFord-Fulkesronアルゴリズム）で解くことができます。
注があるものを除き, このサイトの内容物は
