巡回セールスマン問題に関する記述として、適切なものはどれか。
ア すべての都市を一度ずつ訪問して出発地に戻る最短経路を求める問題である
イ 動的計画法で必ず多項式時間で解くことができる
ウ 貪欲法で常に最適解が得られる
エ 都市数に関係なく一定時間で解くことができる
正解: ア
要点: 全都市を一度ずつ訪問して出発地に戻る最短経路を求める問題で、NP困難である。
この問題に出てくる用語
同じ回の前後の問題
- 令和3年度範囲 練習問題7: 容量10kgのナップサックがある。次の4つの品物から、ナップサックに入る品物の価値の合計を最大にする
- 令和3年度範囲 練習問題9: コンピュータのバスに関する記述のうち、適切なものはどれか。
テクノロジ系の他の問題
- 令和3年度範囲 練習問題9: コンピュータのバスに関する記述のうち、適切なものはどれか。
- 令和3年度範囲 練習問題10: PCI Expressの説明として、適切なものはどれか。
- 令和3年度範囲 練習問題11: 割込み処理に関する記述のうち、適切なものはどれか。
- 令和3年度範囲 練習問題12: コンテキストスイッチに関する記述として、適切なものはどれか。
- 令和3年度範囲 練習問題13: ディスクスケジューリングのSSTF（Shortest Seek Time First）方式の説明とし
アプリで弱点分析つきの演習ができます