アルゴリズムの名前

貪欲法, greedy

貪欲法 - Wikipedia

山登り法, hill climbing, HC

山登り法 - Wikipedia

焼きなまし, simulated annealing, SA

山登り法の拡張。 問題の文脈が弱いときはたいていこれを使えばよい。

hakomo/Simulated-Annealing-Techniques: 焼きなまし法

ビームサーチ

貪欲法の拡張。 問題の文脈が強いときはたいていこれを使えばよい。

ビームサーチは DP - びったんびったん

その他

名前だけ列挙しておく:

  • chokudai search
  • random walk
  • tabu search
  • guided local search
  • Monte Carlo tree search

問題やアルゴリズムの分析に関する用語

大域最適解, global minimum

すべての解の中で最も良いもの。 厳密解とも。

局所最適解, local minimum

解であって、その周囲の解の中で最も良いもの。

局所最適解に到達してしまうと、局所的な改善を繰り返すことではさらに良い解への到達は難しい。 これを「局所最適解に囚われる」などと言う。 邪魔なものという気持ちを込めて探索空間中の「穴」や「谷」という表現がされることが多い。 そのような気持ちを含まずに大域最適解の一般化という気持ちの場合は「峰」とも表現される。

その対策は大きく分けると以下の \(3\) 種になる:

  • 脱出: 状態を適切に遷移させ、局所最適解に到達したとしても囚われることのないようにする
  • 多様性: 多数の状態を用意して、いくつかの状態が囚われても問題にならないようにする
  • 埋立: 評価関数を適切に選んで探索空間を滑らかにし、そもそも局所最適解が存在しないあるいは気にならないようにする

文脈, context

問題の解のそれぞれの要素の、他の要素への依存のこと。 たとえば巡回セールスマン問題は、ある点はその前後の点としか相互作用をしないので文脈が弱い。 たとえばぷよぷよのようなゲームを考えると、ある操作はそれ以前の操作すべての影響を受けてしまうため文脈が強い。

「文脈」という用語は「環境 + 出現位置」のような意味でいくつかの分野で使われる語である。

解空間

問題に対する解の全体の集合のこと。

探索空間, 状態空間

探索を行う過程の状態の全体の集合のこと。 あるいはその上の近傍の定義や評価関数の定義を含めたもの。

評価関数, evaluation function

状態の良さを評価するための関数。

近傍, neighbourhood

解の改善を繰り返してより良い解を得るとき、ある解をちょうど \(1\) 回だけ改善して得られる解を元の解の近傍と呼ぶ。 あるいはそのような解の集合を近傍と呼ぶ。

おそらくは位相空間論の近傍を意識した呼称である。

近傍の外径

ある解の近傍に (素朴な意味で) どれくらい違いの大きい解が含まれているか。 単に近傍の大きさというとこれ。

近傍の内径

ある解の近傍に (素朴な意味で) どれくらい違いの小さい解が含まれているか。 これが大きいと変化どうしが打ち消し合って改善のない解ばかりが見付かってしまう。

ただしここで言う「違いの小さい」とは素朴な意味での近さである。 近傍が導入されることによって定義される「近さ」とは別の近さであることには注意が必要である。

解空間の大きさ, 探索空間の大きさ

すべてのありえる解の個数のこと。

これが大きいときには、山登り法や焼き鈍しでは時間内に局所最適解に辿り着けないことがある。 これは「山を登り切れない」と表現されることが多い。 このような場合は貪欲法やビームサーチが適切であることが多い。

探索空間の滑らかさ, 単峰性, 凹凸

局所最適解の少なさや、その脱出のしやすさのこと。 近傍の選び方と評価関数の両方に依存する概念である。

語によってそれぞれニュアンスは異なるが、どれもほぼ同じ概念を指示している。 なお滑らかさという表現は微分積分論の語を意識したものである。

探索空間の連結性

すべての状態の対が相互に到達可能であるかどうか。 非連結なものの例としては15パズルがある。

解の多様性

探索空間中の点の集合に対し、その含まれる点の散らばり具合のこと。

探索空間中に適切に散らばった多数の点を見れば、いくつかが局所最適解に囚われても残りのいくつかは大域最適解に近付くことが期待できる。 いくら多数の点を見てもそれらの点が近くにあればまとめてすべて同じ局所最適解に囚われてしまいうるが、多様性が高ければそのような事態を回避できる。

解集合からの重複除去

多様性を高めるため、類似した状態を無視すること。 このような対策がないと、探索が進むにつれて点がどれもほとんど同一のものになっていくことがある。

制約の緩和, relaxation

問題の制約を緩めること。 たとえば整数計画問題をその整数制約に関して緩和すると線形計画問題になる。 緩和をすると解が得られない可能性や無理矢理解にするための損が発生するが、状態空間に新たな点が増えて局所最適解が局所最適解でなくなることがある。

緩和した結果の解を緩和解、そのような解と比較しての元々の解を実行可能解と呼ぶ。

アルゴリズムの収束速度

探索が局所最適解に到達するまでの速度のこと。

アルゴリズムの初期解, 初期状態

焼きなましなどにおいて、探索の始点となる解のこと。

収束が遅い場合などは貪欲法などで得られた比較的よい解を設定するとよい場合がある。 これはディープラーニングにおいては事前学習という形で類似のものが見られる。

多点スタート

焼きなましなどにおいて、初期解を変えながら複数回の実行をすること。 探索空間が連結でない場合や局所最適解からの脱出性が低いときに有効であるが、これが有効である場合は他の部分で何かを間違えている場合であることが多い。 多様性を上げるための方策のひとつ。

構築

探索でなく直接に解を得ること。 貪欲法やビームサーチは構築的な色が強く、山登り法や焼きなましは探索的な色が強い。

手動解

人間が手で作った解のこと。あるいはその解の生成方法のこと。 問題の規模が小さいときはかなり良い解であることが多く、機械での探索の方針を見付けることに役立つことがある。

有名な問題

巡回セールスマン問題, traveling salesman problem, TSP

巡回セールスマン問題 - Wikipedia

線型計画問題, linear programming problem, LP

線型計画問題 - Wikipedia

充足可能性問題, satisfiability problem, SAT

充足可能性問題 - Wikipedia

その他

確実に前進

有名な標語。 Topcoderマラソンマッチの探索問題で重要なこと - Qiita を参照のこと。

基準値, 目標値

貪欲解での点数や緩和解での点数など、比較対象や達成目標になる値のこと。 多少の改善では目標値に届かないようならその解法は方向が間違っている、などのような判断に利用できる。

計算量

計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜 - Qiita

algo

algorithm の略。 MM と対比して通常の競プロを指す語。

定数倍最適化

アルゴリズムや特に計算量を変えずにプログラムを高速化すること。 収束速度が遅い場合は有効だが、それ以外の場合はあまりするべきでない。

パラメタ調整

アルゴリズムは変えずにその定数を調整すること。 しばしば自動化される。

クラウド

計算機資源をネットワーク越しに借りることのできるサービスのこと。 手元でのテストを高速化するために使える。

Git

有名なバージョン管理システムのこと。

https://git-scm.com/


マラソンマッチにおける用語の一覧

  • 2019年 3月 8日 金曜日 20:30:00 JST
    • kosakkun さんに読んでもらい、文章の分かりにくかった点を修正
  • 2019年 3月 9日 土曜日 01:15:00 JST
    • %20 さんに指摘してもらった誤字を修正