P、NP、NP完全、NP困難…似て非なる階層構造 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? コンピューターに問題を解かせるときに、それがどの程度の時間を消費するのかも大きな問題です。この観点から、問題はいくつかのパターンに区分されています。ただし、ややこしいです。 #おことわり なお、分かりやすさを優先して、厳密でない説明となっている部分があります。たとえば、チューリング完全性を前提に、チューリング機械で計算するものを、通常のコンピューターで計算するものとしています。 P ある判定問題（yes/noで答えられる問題）があって、それを解くことのできる多項式時間アルゴリズム（問題の規模に対して、計算時間が規模の多項式で表現される上
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
