prolog - Prolog - PCP ソルバー

Question

プロローグ述語を使用してポスト対応の問題を力ずくで解決する (理解できる) 方法があるかどうか疑問に思っていますか?

例えば：

?- pcp(["1","11"),("10111","101")], S).
S = [2,1,1]

Answer 1

OK、幅優先検索を使用して、問題に対するますます大きな解決策を見つける可能なプログラムを次に示します。

1 ?- [user].

サイズ 1 の解から検索を開始

|: pcp(Ts,S) :- pcp(Ts,S,1).

現在のサイズで解決策を見つけてみてください。解決策が見つからない場合は、次のサイズを試してください

|: pcp(Ts,S,N) :- pcp_solve(Ts,("",""),S,N).
|: pcp(Ts,S,N) :- N2 is N+1, pcp(Ts,S,N2).

正しいサイズのソリューションの最後に、文字列が完全に一致する場合、問題は解決されます

|: pcp_solve(_,("",""),[],0).

ソリューションをチェックするための大きなステップ: 文字列タプルのリストからソリューションでインデックス付けされたタプル要素を取得し、このタプルの文字列を最後のステップの文字列に追加し、同じものすべてを照合し、文字列の少なくとも 1 つを空のままにします、ソリューションの次の部分に進みます。(明らかに、ある時点で文字列が一致しない場合、matchreduce は失敗します。)

|: pcp_solve(Ts,A,[I|S],N) :- N>0, N2 is N-1, nth1(I,Ts,T),
|:    bothappend(A,T,AT), matchreduce(AT,ATr), pcp_solve(Ts,ATr,S,N2).

残りの述語は次のとおりです。

|: bothappend((A1,B1),(A2,B2),(A3,B3)) :- append(A1,A2,A3), append(B1,B2,B3).
|: matchreduce(([],B),([],B)) :- !.
|: matchreduce((A,[]),(A,[])).
|: matchreduce(([X|A],[X|B]),(Ao,Bo)) :- matchreduce((A,B),(Ao,Bo)).

append 述語と nth1 述語はリスト ライブラリ (SWI-Prolog) にありますが、簡単に実装できます。

|: :- use_module(library(lists)).
%   library(error) compiled into error 0.01 sec, 9,640 bytes
%  library(lists) compiled into lists 0.03 sec, 22,996 bytes
|: 
% user://1 compiled 0.12 sec, 25,600 bytes
true.

テストケースは次のとおりです。

2 ?- pcp([("1","11"),("10111","101")], S).
S = [2, 1, 1] ;
S = [2, 1, 1, 2, 1, 1] ;
S = [2, 1, 1, 2, 1, 1, 2, 1, 1] ;
S = [2, 1, 1, 2, 1, 1, 2, 1, 1|...] .

そしてウィキペディアからのカップル：

3 ?- pcp([("a","baa"),("ab","aa"),("bba","bb")], S).
S = [3, 2, 3, 1] ;
S = [3, 2, 3, 1, 3, 2, 3, 1] ;
S = [3, 2, 3, 1, 3, 2, 3, 1, 3|...] .

4 ?- pcp([("bb","b"),("ab","ba"),("c","bc")], S).
S = [1, 3] ;
S = [1, 2, 3] ;
S = [1, 2, 2, 3] ;
S = [1, 3, 1, 3] ;
S = [1, 2, 2, 2, 3] ;
S = [1, 2, 3, 1, 3] ;
S = [1, 3, 1, 2, 3] ;
S = [1, 2, 2, 2, 2, 3] ;
S = [1, 2, 2, 3, 1, 3] ;
S = [1, 2, 3, 1, 2, 3] ;
S = [1, 3, 1, 2, 2, 3] ;
S = [1, 3, 1, 3, 1, 3] ;
S = [1, 2, 2, 2, 2, 2, 3] ;
S = [1, 2, 2, 2, 3, 1, 3] ;
S = [1, 2, 2, 3, 1, 2, 3] ;
S = [1, 2, 3, 1, 2, 2, 3] ;
S = [1, 2, 3, 1, 3, 1, 3] ;
S = [1, 3, 1, 2, 2, 2, 3] ;
S = [1, 3, 1, 2, 3, 1, 3] ;
S = [1, 3, 1, 3, 1, 2, 3] ;
S = [1, 2, 2, 2, 2, 2, 2, 3] ;
S = [1, 2, 2, 2, 2, 3, 1, 3] ;
S = [1, 2, 2, 2, 3, 1, 2, 3] ;
S = [1, 2, 2, 3, 1, 2, 2, 3] ;
S = [1, 2, 2, 3, 1, 3, 1, 3] ;
S = [1, 2, 3, 1, 2, 2, 2, 3] ;
S = [1, 2, 3, 1, 2, 3, 1, 3] ;
S = [1, 2, 3, 1, 3, 1, 2, 3] ;
S = [1, 3, 1, 2, 2, 2, 2, 3] ;
S = [1, 3, 1, 2, 2, 3, 1, 3] ;
S = [1, 3, 1, 2, 3, 1, 2, 3] ;
S = [1, 3, 1, 3, 1, 2, 2, 3] ;
S = [1, 3, 1, 3, 1, 3, 1, 3] ;