Prolog - PCP 求解器

发布于 2024-08-14 22:00:35 字数 134 浏览 1 评论 0原文

我想知道是否有一种（可以理解的）方法可以使用序言谓词强力解决邮政通信问题？

例如：

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

原文

I'm wondering if there's an (understandable) way to brute force solve Post correspondence problem using prolog predicates?

for example:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

苏佲洛 2024-08-21 22:00:35

好的，这是一个可能的程序，它使用广度优先搜索来找到问题的越来越大的解决方案。

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).

方案的一大步：从字符串元组列表中获取解决方案中索引的元组元素，将该元组中的字符串附加到上一步的字符串中，匹配所有相同的内容，至少留下一个字符串清空，然后继续解决方案的下一部分。（显然，如果字符串在某个时刻不匹配，则 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] ;

Ok, here's a possible program, which uses breadth first search, to find increasingly bigger solution to the problem.

1 ?- [user].

Start the search at solutions of size 1

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

Try finding a solution at the current size, and if you don't find one try the next size

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

If at the end of your solution of the correct size, the strings are matched completely then the problem is solved

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

Big step for checking the solution: get the tuple element indexed in the solution from the list of string tuples, append the strings in this tuple to the strings from the last step, match everything that's the same, leaving at least one of the strings empty, then go onto the next part of the solution. (Obviously, if the strings don't match at some point matchreduce will fail.)

|: 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).

Here are the rest of the predicates:

|: 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)).

The append and nth1 predicates are in the lists library (SWI-Prolog) but can be implemented easily!

|: :- 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.

Here's your test case:

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|...] .

And a couple from wikipedia:

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] ;

回复收藏 0 原文

~没有更多了~