研究の紹介
はじめに 項書き換えシステムの例 項書き換えシステムの完備性 グラス置き換えパズル グラス置き換えパズルの完備化 完備化手続き 群の完備化 両方向ペトリネットの完備化 組みひも問題の完備化 失敗無し完備化 おわりに はじめに 項書き換えシステム(term rewriting system)は等式にもとづく柔軟な計算法 と効率的な証明法を提供できるため，定理自動証明，関数型あるいは論理型言 語，代数的仕様記述，記号処理など，計算機科学のさまざまな分野で広くもち いられています． 項書き換えシステムは方向付けられた等式（書き換え規則）の集合として 定義されます．ところで，等式そのものにはもともと計算という意味はありま せん．たとえば，等式 1+2 = 3 は右辺と左辺が等価であるという論理的な意 味をもつだけです．したがって，論理の世界では，1+2 から 3 を得るだけ ではなく，逆に
No Free Lunch Theorem—理想の＊＊の探し方—
すべての評価関数に適用できる効率のよいアルゴリズムは存在しない。 “すべての評価関数”というのは上の例で言えば“すべての”ということである。 この定理を証明する前に、まずよく知られた探索アルゴリズム[5]を挙げて、探索とはそもそもどのようなものなのかを説明しよう。 探索アルゴリズム “探索”というのは問題の解の候補の中からよいものを探し出すことである（同語反復という感じだが）。ここでは次のように、評価関数が定義された問題を解く過程のことを探索と呼ぶことにする。 解の候補の有限集合を、その要素のひとつをとする。 評価関数はから有限集合への写像である（の要素のひとつをで表す）。 の最大値を与えるようなが問題の解で、それを見つけたいのである。 このような探索問題を解くためのアルゴリズムには大きく分けて次の2つがある。 アルゴリズムのように知識を用いて解を構成するもの（適切なヒューリスティックスが
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
