その他・雑記2019/12/30目次やること計算量オーダーとは(1)田中は男の子ですか?(2)転校生の小林さんが来ました。小林さんを背の順に加えたとき、男の子の後ろですか?(3)クラスに伊藤はいますか?(4)背の順に並んでください。男の子が5人連続する部分はありますか?(5)クラスに誕生日が同じペアはいますか?(6)2年生のクラス分けを行います。1年A組のすべての友達関係が崩れないクラス分けのパターンはありますか?(7)家庭訪問のルートを決めます。ガソリンを一度も給油しないで済むルートはありますか?計算量オーダーまとめNP完全とは補足NP完全であると何が嬉しいのか?テント・アンド・ツリーパズルがNP完全であるかどうか遺伝的アルゴリズム(GA)はvcoptにおまかせ編集後記やること「日本一わかりやすい」は流石に盛りました。最適化をやっているとどうしても「NP完全」を理解しなければなりません。NP完全を検索しても「NP困難のうちNPであるもの」といった定義ばかりでさっぱりです。今日は日本一わかりやすいNP完全の説明を目指します。一度諦めた方もぜひ挑戦してみてください。計算量オーダーとはビネクラ中学校1年A組には男女合わせて40人います。しておきます(N=40)。次の問題の答えを求めるにはどれくらいの計算量が必要かを考えます。(オーダーイチ)と呼びます。(2)転校生の小林さんが来ました。小林さんを背の順に加えたとき、男の子の後ろですか?ただし40人の背の順は完成しており、身長を測る機械はないものとします。担任の先生はこう考えました。列の真ん中の人と背比べをして、小林さんが低ければ低い側のグループ、高ければ高い側のグループに入れる。これを繰り返せば小林さんの位置がわかる!このような探索方法を二分探索と呼びます。二分探索は半分にして半分にして...というアルゴリズムなので、Nが2の何乗なのかが重要になります。あることが知られています。