Scheme 入門 18. 非決定性

1. 初めに 非決定性は問題を記述するだけで答えが得られるようにするアルゴリズムです。 プログラムは選択肢の中から条件に合うものを自動的に選び出します。 この手法を使うと論理プログラムを容易に書くことができます。 例えば、 > (let ((i (amb 4 6 7)) (j (amb 5 8 11))) (if (prime? (+ i j)) (list i j) (amb))) (6 5) のようにすると '(4 6 7) と '(5 8 11) のうちから二つの数の和が素数になる組の１つを返します。 (amb 4 6 7) は、式が値を返すように 4, 6, 7 の中から適切に値を選び、同様に、 (amb 5 8 11) は、式が値を返すように 5, 8, 11 の中から適切に値を選びます。 (amb) は選ぶべき値が無いので失敗を表します。 実際は、amb は深さ優先の探索をして

[kekera]

へー、これ面白い＞amb は深さ優先の探索をしており、(amb c1 c2 c3 ...) は c1, c2, c3, ... を順番に試す探索経路を生成し

[sidestepism]

ambすごい

[smocchan]

amb

[rsakamot]

amb

[cho45]

「非決定性は問題を記述するだけで答えが得られるようにするアルゴリズムです」