New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

7回目 #9

Open

risacan opened this issue Aug 25, 2017 · 3 comments

Member

risacan commented Aug 25, 2017

範囲！

第8章問題は続くよどこまでも：貪欲法
- p 167 ~ p189

すすめかた！

読み終わったら、このIssueのコメント欄で、[読み終わった宣言]をする！ 🎉
気になったキーワードとかは、ここのIssueのコメントにメモ！:memo:
疑問点を解決したらCloseする

Member

katorie commented Sep 1, 2017

読んだ！

NP完全問題だったら近似アルゴリズムを使って問題を解く
NP完全かどうかを見分けるのが難しい
NP完全かどうか見分けるポイント
- アイテムの数が増えるとかなり低速になるとき
- 「Xのすべての組み合わせ」みたいなやつ
- 問題を小さな単位に分割できなくて「考えられる限りのバージョン」を計算する必要があるとき
- 巡回セールスマンみたいに問題がシーケンスに関連していて解くのが難しいとき
- 問題が集合に関係していて解くのが難しいとき
- 集合カバー問題や巡回セールスマン問題に言い換えることができるとき

Member

katorie commented Sep 1, 2017

そもそもNPってなんなのって思ったけど
https://www.wikiwand.com/ja/NP

😕

Member

katorie commented Sep 8, 2017

なんか難しいし全体的にふわっとしているからどこまで理解すべきか悩ましいけど、
頭の片隅に置いておくということで、次に進むのが良さそうかなと思いました！

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment