忍者ブログ
MASTER →  ADMIN / NEW ENTRY / COMMENT
現代魔法(nearly equal 情報技術)を勉強中な人のメモ(チラシの裏)
/ 2017/06/28 (Wed) / 編集
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

/ 2008/08/16 (Sat) / 編集

探索木

二分木

  • 二分木:子はたかだか2つ
  • 二分探索木:子はたかだか2つ、左子<親<右子
  • 完全二分木:子はたかだか2つ、かつ偏りがない
  • ヒープ木:完全二分木、かつ頂点は最小値

クラスの話

  • P:決定性(deterministic)アルゴリズムを使って多項式(Polynomial)時間で解ける問題
  • NP:非決定性(Nondeterministic)アルゴリズムでうまくいくと多項式(Polynomial)時間で解ける問題
  • 判定問題
  • NP困難:多項式時間で解けない
  • 巡回セールスマン問題(TSP)とか、いわゆる最適化問題
  • NP完全(難しいかどうかわからない問題):NP困難でNPに属しているもの
  • 論理式の充足可能性問題(SAT)とか
Algolithm noteてゆうサイトがいい感じだった

拍手[0回]

PR
忍者ブログ [PR]