2019-ビーバー宅配便-解説
- 考案国：カナダ
- 正解
- 「25」
- 説明
- Aからスタートして、同じ道を通らずにすべての街を通る移動ルートは以下の4種類しかありません。
それぞれの移動ルートで得られる賃金です。2+1+3+2+8+4+3 = 23 2+1+5+3+4+8+2 = 25 2+1+5+3+1+2+8 = 22 3+3+4+8+2+3+1 = 24
計算結果を見ると、これらの賃金の最大値は25であることがわかります。
- Aからスタートして、同じ道を通らずにすべての街を通る移動ルートは以下の4種類しかありません。
- 実際のコンピュータでは
- コンピュータ科学では、このような図は「グラフ」と呼ばれます。街に相当する点は「頂点」、道に相当する線は「辺」です。
- グラフの最適な経路を探索するために複数のアルゴリズムが使われます。すべての頂点を1回だけ通る経路はハミルトン路です。今回の問題ではハミルトン路であることに加え、収益が最も高くなる経路を探索しました。
注があるものを除き, このサイトの内容物は
