5

私はまだ解決策を持っていないこの特定の問題を抱えています。関連するアルゴリズムが存在することを知っていれば役立つと思います。

私が探しているアルゴリズムは、関数によって返される目標を満たす引数を見つけるのに役立つアルゴリズムです。

たとえばa works for b、(a,b)

Given: [ (a,b); (b,c) ]

関数worksはブール値との関係を保証します

let works a b -> true
let works b c -> true

今、私は与えられています

[ (a, "x"); ("x", c) ]

これら 2 つのバインディングを true にしたい場合、この関数は true でなければなりません

let works a "x" -> true
let works "x" c -> true

今、私はそのようなことを達成するのに役立つ関数/アルゴリズムを書こうとしています"x" = b

バックトラックを考えていましたが、まだ実装方法がわかりません。誰かが私にヒントを提供していただければ幸いです。

補足として、関数型プログラミング パラダイムを使用して F# でアルゴリズムを実装しています。

4

2 に答える 2

4

後方連鎖が必要であることは正しいですし、統合が必要であることはジャックも正しいですが、具体的には後方連鎖による構文の統一が必要です。

あなたの質問は新しいものではありませんが、純粋に機能的な言語でプロローグ インタープリターを実装する方法として、 CS:StackExchangeでより完全に回答されていますか?

これで正しい道を歩むことができますが、解決したい問題によっては、これが思ったほど簡単ではないことに気付くかもしれません。

編集

私が持っているいくつかの動作中の F# コードであなたの例をテストしましたが、動作しますが、コードを公開することはできません。申し訳ありません。

与えられた例では、後方連鎖なしで単一化だけで実行できます。

ファクトを作成する必要があります。

works(a,b).
works(b,c).

とクエリ

works(a,X),works(X,c).

答えは

X = b

これを途中の複数の人に拡張したい場合は、再帰的な従属ルールを作成する必要があるため、後方連鎖を使用する必要があります。

ファクトを作成する必要があります。

works(a,b).
works(b,c).
works(c,d).

とルール

subordinate(X,Z) :- works(X,Z).
subordinate(X,Z) :- works(X,Y), subordinate(Y,Z).

とクエリ

subordinate(a,X),subordinate(X,d).

答えは

X = b,c

タイプ、統合、後方連鎖アルゴリズムを作成する必要があります。REPL にパーサーとプリティ プリンターとレイヤーを作成することもできますが、必須ではありません。

ファクト、ルール、およびクエリは人間の言葉で示されますが、パーサーとプリティ プリンターをスキップすると、AST としてコーディングする必要があります。すなわち

("works", [Const "a", Const "b"])

大文字は Prolog 変数を表します。すなわち XYZ
小文字は Prolog 定数を表します。つまりabc

あなたの作品の問題は、古典的な祖先の例の単なるバリエーションです。参照:プロローグ/再帰ルール

于 2013-10-09T20:05:59.687 に答える
3

あなたが説明しているアルゴリズムは統合です。これは Prolog の基礎であり、F# で実装するのはそれほど難しくありません。

John HarrisonによるHandbook of Practical Logic and Automated Reasoning ( Amazon、Safari Books )を読むことをお勧めします。セクション 3.9 では、統合アルゴリズムについて説明します。他の 2 人の F# 担当者と私は、昨年、この本からコードを F# に移植しました: fsharp-logic-examples。

問題の説明を考えると、単純な Constraint Logic Programming (CLP) でおそらく解決できますが、F# 用の CLP ライブラリを実装した人はまだ誰もいません。miniKanrenとcKanrenは、そのようなシステムの 2 つの一般的で単純な例であり、F# への移植に興味がある場合でも、移植に時間がかかるとは思えません。

于 2013-10-09T18:47:55.893 に答える