标签: clpfd

球员数量有限,网球场数量有限.在每轮比赛中,最多可以有比赛更多的比赛.没有休息,没有人打2轮.每个人都与其他人比赛.制定尽可能少轮次的计划.(由于每个人的轮次之间必须休息的规则,可以有一轮没有比赛.)5名球员和2个球场的输出可以是:

 |  1   2   3   4   5
-|------------------- 
2|  1   - 
3|  5   3   - 
4|  7   9   1   - 
5|  3   7   9   5   -

在此输出中,列和行是播放器编号,矩阵内的数字是这两个玩家竞争的圆形数字.

问题是找到一种算法,可以在可行的时间内为更大的实例执行此操作.我们被要求在Prolog中这样做,但任何语言的(伪)代码都是有用的.

我的第一次尝试是一种贪婪的算法,但这会产生太多轮次的结果.然后我建议迭代加深深度优先搜索,我的一个朋友实现了,但是仍然花了太多时间在小到7个玩家的实例上.

(这是一个旧的考试问题.我接触过的任何人都没有任何解决方案.)

我正在尝试解决prolog中的约束处理问题.

我需要在10x10的网格中打包4个5x5,4x4,3x3和2x2的正方形.它们可能不重叠.

我的变量看起来像这样:

Name: SqX(i), i=1..10, domain: 1..10

其中X是5,4,3或2.索引i表示行,域表示网格中的列.

我的第一个约束试图定义正方形的宽度和高度.我这样制定它:

Constraint: SqX(i) > SqX(j)-X /\ i>j-X, range: i>0 /\ j>0

这样可能的点被约束在彼此的X行和列之内.然而,Prolog会停止这些约束并给出以下结果:

Adding constraint "(Sq5_I > Sq5_J-5) /\ (I>J-5)" for values:
        I=1, J=1, 
        I=1, J=2, 
        I=1, J=3, 
        I=1, J=4, 
        I=1, J=5, 
        I=1, J=6, 
=======================[ End Solutions ]=======================

所以它停在那里,甚至没有检查其他方块.我的约束很可能太紧张,但我不明白为什么或如何.有什么建议？

N-Queens问题:

这个问题表明,给定一个大小为N乘N的国际象棋棋盘,找到不同的排列,其中N个皇后可以放在棋盘上而没有任何一个相互威胁.

我的问题是:
程序可以在合理的时间内计算出答案的N的最大值是多少？或者到目前为止我们看到的最大N是多少？

这是我在CLPFD(Prolog)中的程序:

generate([],_).
generate([H|T],N) :-
   H in 1..N ,
   generate(T,N).

lenlist(L,N) :-
   lenlist(L,0,N).

lenlist([],N,N).
lenlist([_|T],P,N) :-
   P1 is P+1,
   lenlist(T,P1,N).

queens(N,L) :-
   generate(L,N),lenlist(L,N),
   safe(L),
   !,
   labeling([ffc],L).

notattack(X,Xs) :-
   notattack(X,Xs,1).

notattack(X,[],N).
notattack(X,[Y|Ys],N) :-
   X #\= Y,
   X #\= Y - N,
   X #\= Y + N,
   N1 is N + 1,
   notattack(X,Ys,N1).

safe([]).
safe([F|T]) :-
   notattack(F,T),
   safe(T).

这个程序运行得很好,但是它花费的时间不断增加N.这是一个示例执行:

?- queens(4,L).

L = [2, 4, 1, 3] ;

L = [3, 1, 4, 2] ;

No

这意味着您将4个皇后放置在第1列的第2行,第2列的第4行,第3行的第1行和第4行的第3行(在4乘4的棋盘中)

现在让我们看看这个程序是如何执行的(计算第一个排列所花费的时间):
对于N …

在CLP(FD)中,我们经常需要声明:"这是整数和有限域变量的列表(有时:严格地)升序/降序."

是否有任何CLP(FD)系统为此任务提供通用(参数化)内置约束？

SWI-Prolog提供了一个名为的约束chain/2,类似于我正在寻找的约束.但是,名称稍微过于具体,不能包含约束可以描述的所有关系(例如:#<不是部分顺序,但是可以接受chain/2,导致序列 - 作为一组整数 - 不再计算为链中定义的链数学顺序理论).因此,该名称并未完全描述约束实际实现的内容.

请给所述最一般相对于通常的二进制CLP(FD)约束定义-或包含至少一个合适的子集#<,#>,#=<和#>=- 包括根据代数结构的约束定义适当的名称.强加的条件是约束描述了在文献中具有正确名称的实际数学结构.

首先,请考虑使用SICStus Prolog或SWI:

:- use_module(library(clpfd)).

connex(Relation_2, List) :-
    connex_relation(Relation_2),
    connex_(List, Relation_2).

connex_relation(#=).
connex_relation(#<).
connex_relation(#=<).
connex_relation(#>).
connex_relation(#>=).

connex_([], _).
connex_([L|Ls], Relation_2) :-
    foldl(adjacent(Relation_2), Ls, L, _).

adjacent(Relation_2, X, Prev, X) :- call(Relation_2, Prev, X).

示例案例:

?- connex(#<, [A,B,C]).
A#=<B+-1,
B#=<C+-1.

?- connex(#=, [A,B,C]).
A = B, B = C,
C in inf..sup. …

我正在写一个小程序,它计算列表中有多少元素不是数字.这是我的代码:

not_number([],0).
not_number([X|T],R):- 
    not(number(X)),
    R1 is R+1,  
    not_number(T,R1). 

not_number([_|Tail],Result):-
    not_number(Tail,Result).  

如果我执行这样的代码:

?- not_number([1,2,3,5], R).

我得到R = 0(应该是)

R = 0.

但是,如果我在列表中放置一个字符:

?- not_number([1,2,3,5,a], R).

然后我收到这个错误:

ERROR: not_number/2: Arguments are not sufficiently instantiated
   Exception: (10) not_number([a], _G247) ? 

有人能解释代码有什么问题吗？我是prolog的新手.

一个奇怪的问题是:
我在学校解决竞争问题,他们允许我们使用电脑.由于我是竞赛中唯一知道如何编码的人,我使用C和Pascal程序来更快地解决问题.我已经完成了伪代码到代码练习,算法,Collat​​z猜想验证等.
现在,昨天我正在接受下一次挑战训练(4月18日),我看到了一场关于Young tableaux的练习.它的措辞是这样的(我将尽力从意大利语翻译):
"Ferrers图表是N个盒子的配置,分布在一个或多个水平行中,左对齐并配置为每行包含相等或更低的数量这些配置也可以用方框的编号列表来描述,如下图所示:
ferrers diagram http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_m_07a_400.jpg
一个年轻的画面是一个Ferrers N个框的图表填充了从1到N的整数.示例:
young tableaux http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_s_03b_400.jpg
如果框中的数字被排序,以便它们按行和逐列递增,表格是"标准"(例如:第一,第三和第五画面).在标准表格中,第一行的第一个框始终包含1.N始终位于图表的其中一行的最左侧框中.


问题

考虑一个[6,3,2,1,1,1] Ferrers图:
1)如果第一行的第6个框中固定了6,第一列的最后一个框中固定了11,那么有多少种方法可以您是否以标准方式完成图表？

2)如果在第1行的第6个框中固定了7,在第1列的最后一个框中固定了11,那么您可以用多少种方式以标准方式完成图表？

3)如果在第1行的第6个框中固定了8,在第1列的最后一个框中固定了11,那么您可以用多少种方式以标准方式完成图表？"

我试图编写解决方案用矩阵填充这些数字并用"-1"作为"行尾字符",但我卡住了.我怎么能编码"以各种可能的方式填写它以使画面成为标准？".

在阅读SICP时,我遇到了逻辑编程第4.4章.然后我开始研究Prolog编程语言并尝试理解Prolog中的一些简单的任务.我发现Prolog似乎在数值计算方面遇到麻烦.

这是标准Prolog中的阶乘计算:

f(0, 1).
f(A, B) :- A > 0, C is A-1, f(C, D), B is A*D.

我发现的问题是我需要引入两个辅助变量(C和D),一个新的语法(is),并且问题是不可逆的(即,f(5,X)按预期工作,但f(X,120)不能).

天真的,我希望至少C is A-1, f(C, D)可以用上面的东西代替f(A-1,D),但即使这样也行不通.

我的问题是:为什么我需要在数值计算中做这些额外的"东西",而不是在其他查询中呢？

我明白(并且SICP非常清楚),一般来说,"做什么"的信息不足以回答"如何做"的问题.因此,(至少一些)数学问题的陈述性知识不足以真正解决这些问题.但这引出了下一个问题:Prolog中这些额外的"东西"如何帮助我将制定局限于那些"做什么"足以回答"如何做"的问题？

我试图在列表中计算反转的数量.谓词inversion(+L,-N)统一N了该列表中的反转次数.甲反转被定义为X > Y与X之前出现Y在列表中(除非X或Y是0).例如:

?- inversions([1,2,3,4,0,5,6,7,8],N).
N = 0.

?- inversions([1,2,3,0,4,6,8,5,7],N).
N = 3.

对于我正在使用的内容,列表将始终包含9个元素,并且始终包含0-8唯一的数字.

我对Prolog很新,我试图尽可能简洁,优雅; 似乎DCG可能会有很大帮助.我读了官方定义和一些教程网站,但仍然没有放弃了解它是什么.任何帮助将不胜感激.

我正在研究一个小的prolog应用程序,以解决摩天大楼和栅栏难题.

一个未解决的难题:

一个解决的难题:

当我通过程序已经解决的谜题时,它很快,几乎是即时的,为我验证它.当我通过程序真正的小谜题(例如,2x2,当然有修改的规则),找到解决方案也很快.

问题在于计算具有6x6"原生"大小的谜题.我让它在中止前运行了5个小时左右.太多时间了.

我发现花费时间最长的部分是"围栏",而不是"摩天大楼".分别运行"摩天大楼"可以快速解决问题.

这是我的栅栏算法:

• 顶点用数字表示,0表示路径不通过该特定顶点,> 1表示顶点在路径中的顺序.
• 约束每个单元格以使其周围有适当数量的线条.
  • 这意味着如果它们具有连续数字,则连接两个顶点,例如,1 - > 2,2 - > 1,1 - > Max,Max- > 1(Max是路径中最后一个顶点的数字.计算通过maximum/2)
• 确保每个非零顶点至少有两个具有连续数字的相邻顶点
• 约束Max等于(BoardWidth + 1)^2 - NumberOfZeros(BoardWidth+1是沿边缘的顶点数,并NumberOfZeros通过计算count/4).
• 使用nvalue(Vertices, Max + 1)以确保不同值的数量Vertices是Max(即顶点的路径数)加1(零个值)
• 找到包含a的第一个单元格3并强制路径开始和结束,以提高效率

我该怎么做才能提高效率？代码包含在下面以供参考.

skyscrapersinfences.pro

:-use_module(library(clpfd)).
:-use_module(library(lists)).

:-ensure_loaded('utils.pro').
:-ensure_loaded('s1.pro').

print_row([]).

print_row([Head|Tail]) :-
    write(Head), write(' '),
    print_row(Tail).

print_board(Board, BoardWidth) :-
    print_board(Board, BoardWidth, …

有人可以帮助我找到一种方法来获得Prolog中的反因子...

例如inverse_factorial(6,X) ===> X = 3.

我一直在努力工作.

我目前有阶乘,但我必须让它可逆.请帮我.