譯自http://www.pathwayslms.com/swipltuts/clpfd/clpfd.html#_simple_constraints，SWI-Prolog官網所推薦的進階教程，目前還沒譯完，會不定期更新，
1. 關于本教程
1.1. 誰應該用這個教程
本教程適用于要用clp(fd)、有一定經驗的SWI-Prolog程式員，
此外，對于用其他版本Prolog且要用clp(fd)的Prolog程式員，本教程也是有用的，
本教程的重點不在理論，作者不是數學家，而且本文可能對那些能通過學術文獻找到材料的稱職的數學家也沒多少用處，
本教程將幫助你理解有限域上的約束系統的基礎知識，
它包涵了一定的實踐經驗，
這篇教程大多數情況下是對SWI-Prolog的clp(fd)謂詞檔案的轉述，由簡明扼要的數學檔案變為更平易近人的語言，
1.2. clp(fd)有什么用？
clp(fd)是標準SWI-Prolog發行版??中包含的庫，它解決涉及變數集的問題，其中變數之間的關系需要得到滿足，
clp(fd)還可用于替代面向物件語言中由getter和setter提供的許多保護函式，例如，如果我們尚不知道一個人的實際身高，我們仍然可以斷言其超過21英寸且不到108英寸（已知的最矮/最高）， 當我們最終找到解決方案時，不合理的值將被丟棄，
clp(fd)用于通過減少搜索空間來優化搜索問題，約束可以削減整個搜索空間的子樹，
clp(fd)對解決各種查找變數的問題非常有用，這是一些clp(fd)可以解決的問題的廣泛類別：
- 安排問題，如應該在什么時候做什么作業來生產這些產品？
- 優化問題，如應該在工廠生產哪種產品以獲得最大利潤？
- 需求滿足問題，如在醫院中找到符合條件的房間，例如在康復室旁邊的手術室，或是找到全家都贊成的度假方案，
- 順序問題，如找到我們前往目的地的路線，
- 標識問題，如數獨或密碼算術問題，
- 相信與意圖問題，比如偵探謎題和游戲中的非玩家角色，
- 分配問題，如分配飛機機組人員，使其滿足工會的要求，并最大時間離家，
- 為相關聯的變數集找可接受的解決方案，如在一群嫉妒的少女中，找出誰會去參加聚會，如果B去了，A才會去；如果C去了，B就不會去，等等，
- 為多個互相影響的變數創建可接受方案串列，如一個宴席籌備者可能希望看到宴席選單滿足宴席開銷、廚師和侍者的日程、烤箱的安排等不同需求，然后自己選擇采用哪種方案，
- 圖形的幾何約束條件，如CAD系統中，其中兩條線必須垂直，另外兩條必須平行，其他兩條線相距30英尺，依此類推，
clp(fd)的使用練習
為上面每個類別再舉一個例子，盡量擴展問題的范圍，例如，給定一組火車車廂，將它們按合理的順序排列，使其遵守一些規則（例如，沒有油罐車靠近引擎，守車必須在后面）就是個順序問題，
1.3. 前提
掌握SWI-Prolog的基礎知識，
數學水平與計算機科學本科課程的高等水平相當，
SWI-Prolog已安裝并運行正常，
本教程沒有附帶代碼檔案，你可以剪貼示例，
1.4.你可以從本教程中學到什么
如果你讀完此教程，并完成所有練習，你可以期待：
- 了解約束編程的基本概念
- 能撰寫查找未知值解決方案的程式
- 能用clp(fd)庫闡述現實世界的問題
- 能對約束系統問題選用適當的解決方案
- 了解如何在真正的SWI-Prolog的程式中使用clp(fd)
1.5. 完成時間
6－8小時，因人的數學水平而異，
2. clp(fd)庫
SWI-Prolog的clp(fd)庫是由Markus Triska為他的博士論文撰寫的，clp(fd)代表有限域上的約束邏輯式編程，
clp(fd)是SWI-Prolog中可用的幾種約束求解器之一，其他的有：clp(b)，clp(qr)， clp(b)處理布林值；clp(qr)處理有理數和實數， CHR是用于創建自己的約束系統的工具（其他型別），
clp(fd)庫可以輕易地激活：
1 :- use_module(library(clpfd)).
這將安裝個編譯時的掛鉤，可以優化一些clp(fd)約束，并加載運行時的庫，
3. 變數
在計算機科學中，我們很寬松地使用“變數”這個術語，
3.1 替代變數
在命令式編程語言中，比如Java，變數是可變的，其值會隨時間而改變，
在C語言中，像變數x：
int x; ... what about here? ... x = 5;
3.2 邏輯變數
在邏輯式語言中，變數是不同的，它們更像高中代數中的變數或未知數，
在Prolog中，變數可以是系結或非系結的，非系結的變數將與任何值結合，系結的變數僅與一個模板統一，
實際上，我們要么知道，要么不知道變數的值，
當我們試圖結合時，我們實際上是在問：“我們對左邊和右邊答案的理解是一致的嗎？”鮑勃聲稱自己是主城市長的好友，如果鮑勃是《主城日報》的編輯，這很可能是可信的，如果鮑勃聲稱從未涉足主城，這就有些矛盾了， 在Prolog中，對于原子結果只有兩種可能，完全不知道，或確切知道，顯然，在串列或項中可能有非系結的變數，但對于每個變數，只有這兩種狀態，
3.3. 約束變數
但在現實世界，我們可以講出更多關于變數的內容， 我們可能不知道確切的值，但我們知道它是一組可能的值中之一，我們稱之為域，
我們可能不知道具體值是什么，但可以說它其他一些我們同樣不知道值的變數要大，我們說這個變數是受約束的，
隨著我們開始積累約束條件，我們開始能對約束進行推理，假設我們有兩個整數變數，X和Y，
現在我告訴你，X在0到10的范圍內，
接著，Y在4到8的范圍內，
最后，X大于Y，
你可以推斷出，X在5到10這個更窄的范圍內，因為Y可以具有的最小值是4，并且X必須比Y至少大1，
這便是clp(fd)的樣子，如果你沒完全理解這些，也不要擔心，
:- use_module(library(clpfd)). 1 test(X, Y) :- X in 0..10, 2 Y in 4..8, 3 X #> Y. 4 14 ?- test(X, Y). X in 5..10, 5 Y#=<X+ -1, 6 Y in 4..8.
1 匯入clp(fd)庫
2 使用“in”運算子，約束X在0到10之間
3 使用“in”運算子，約束Y在4到8之間
4 使用“#>”運算子，約束X比Y大
5 現在X被約束為5到10之間
6 現在Y被約束為=< X - 1（同樣是X>Y），且范圍為4到8，
當我們將一個變數限制為單一值時，會發生一些神奇的事——我們現在已經知道了變數，因此可以系結變數，在clp(fd)中，確實發生了這種情況！假設我將X約束在0到5的范圍內，并且將Y約束在4到8的范圍內，并且X> Y，那么突然X現在系結到5了，ground（X）成功了，并且X是一個非常普通的系結變數，
:- use_module(library(clpfd)). test2(X, Y) :- X in 0..5, Y in 4..8, X #> Y. 16 ?- test2(X,Y). X = 5, 1 Y = 4. 2
1 X被系結，就像在普通的Prolog中那樣
2 注意，Y也被系結了，此外，它失去了原先的約束，
編輯、運行練習
輸入并嘗試以上兩個例子，使用除錯器進入它們，以查看列出的約束，
回溯練習
:- use_module(library(clpfd)). foo(X) :- X in 1..3 . foo(X) :- X in 5..7 . foo(X) :- X in 8..12 .
如果查詢foo(X)，并通過回溯得到所有解決方案，將會發生什么？預測會發生什么，并嘗試它，你的預測正確嗎？
3.4. 實作
SWI-Prolog能將屬性添加到變數，這是附加到變數的附加元資料，如果你有興趣，可以在SWI-Prolog網站上閱讀有關屬性變數的更多內容，
clp(fd)使用此屬性資料修飾約束變數，然后clp(fd)實作了約束編程，并作為常規Prolog統一的擴展，
本教程結尾將對此作更多介紹，
屬性練習
Extra credit -
考慮除了用于約束，變數屬性的另一種用法，
3.5. 域
clp(fd)中的(fd)表示有限域，該域可以具有數百萬個值，但它必須是一個有限串列，
我們只關心有限域的變數，就我們的目的而言，這意味我們要對整數集的域進行推理，
clp（fd）可用于[air, land, sea]這樣的域，但優化效果不佳，映射air = 0，land = 1，sea = 2，然后說域是0..2，會更好，任何可能的有限串列都可以映射到整數的有限子集，任何有限的可能性串列，都可以映射到有限的整數子集中，
乍一看，這可能顯得有些笨拙，但實際上與使用陣列索引沒什么不同，更大的問題可能是除錯——整數串列可能毫無意義，撰寫一些除錯代碼以提取并輸出資料，可能會有幫助，
4. 示例
我總是被那些毫無根據的討論畝訓，這是一個典型的約束程式，并包含各部分的簡要說明，你可能還不了解所有部分， “SEND + MORE = MONEY”密碼算術問題是約束編程中的經典“hello world”，題目是將0到9數字分配給字母，使它們拼出SEND MORE MONEY，當以10為底地讀取數字時，將形成真正的算式，數字不允許有前導0，
:- use_module(library(clpfd)). 1 puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :- 2 Vars = [S,E,N,D,M,O,R,Y], 3 Vars ins 0..9, 4 all_different(Vars), 5 S*1000 + E*100 + N*10 + D + 6 M*1000 + O*100 + R*10 + E #= M*10000 + O*1000 + N*100 + E*10 + Y, M #\= 0, S #\= 0, 7 label(Vars). 8 9 ?- puzzle(X). X = ([9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2]) ; 9 false.
1 匯入clp(fd)庫
2 注意，clp(fd)不像pce或準參考那樣的嵌入式DSL，clp(fd)與Prolog一起使用，增加了主義，
3 為了方便起見，列出了我們要約束的所有變數
4 將Vars中的每個變數限制為0..9的范圍（含）
5 添加約束條件，它們必須是不同的
6 添加定義問題的算術約束
7 單詞以M和S打頭，因此不能為0
8 嘗試盡可能多地確定變數
9 注意，外面沒有有趣的屬性，只回傳了解決方案
FortyTenTen練習
1）通過修改程式來解決密碼算術FORTY + TEN + TEN = SIXTY 2）如果允許前導0，是否還有SEND+MORE=MONEY的解決方案？修改程式以找出答案，
5. 標簽
附加約束很好，但在我們最侄訓到簡單地系結變數之前，它用處不大，有著所有固定變數的解稱為固定解，
有一些次要的機制可以做到這一點，
如果將定義域縮減至單個值，則變數會被固定，
一般，你可以輕易地為變數賦值，通常，X = 3將變數限制為單個值，
謂詞indomain/1會在回溯時，連續地將變數綁定到其可能的值，
通常，我們將找單個固定的解決方案稱為label/1或labeling/2，label/1和labeling/2是不確定的，在每次回溯時，都系結了一組不同的值，
當然，我們的約束系統可能不足以表達每個約束，如果是這樣，我們必須依賴生成和測驗搜索策略來熟悉所有Prolog程式員了，有了約束系統，生成和測驗系統成為
1.約束
2.生成（通過labeling）
3.測驗
實際上，大多數clp(fd)程式遵循約束后接標簽的一般模式，
提示：設定模型，并在單獨的謂詞中執行標簽和剩余的搜索是良好的做法，這使得在應用標簽之前檢查模型變得更加容易，
labeling/2有大量選項能影響變數選擇策略，由于 clp(fd)程式花費的大部分時間通常是在labeling上，我們會在后面詳細介紹這些內容，現在我們使用label/1，它有合理的默認值，
labeling/2的選項也用于最優化的問題，
6. 簡單約束
clp(fd)提供一組基本、簡單的約束，
請記住，clp(fd)與整數一起使用，
X #>= Y X #=< Y X #= Y X #\= Y X #> Y X #< Y
提示
你可以使用#=作為is的宣告性版本，否則不是clp(fd)，X is 3+Y使Y被固定，而X #= 3+Y，在X被固定、而Y不是的情況下起作用，
提示
X #< Y可以消除不必要的對稱，比如，如果玩家1和3在錦標賽中已配對，再考慮3和1的配對是沒意義的，請考慮以下取自SWI-Prolog檔案的示例，它找出了使四個配對的所有方法：
示例1 消除對稱
?- Vs = [A,B,C,D], Vs ins 1..4, all_different(Vs), A #< B, C #< D, A #< C, findall(pair(A,B)-pair(C,D), label(Vs), Ms). Ms = [ pair(1, 2)-pair(3, 4), pair(1, 3)-pair(2, 4), pair(1, 4)-pair(2, 3)].
嚴格遞增練習
撰寫謂詞increase/1，它接收一個串列，約束它嚴格遞增，
首先記錄你預計每個查詢的結果，然后測驗你的謂詞是否符合你的預期，
7. 約束域
變數的域是它可以取的一組值，
在clp(fd)中，每個變數必須被限制到有限域，以進行推理，在嘗試標記它們之前，你需要給變數賦予域，如果不是，你將得到令人困惑的例外，錯誤：引數未被充分實體化，
X in 5..10, 1 Y in 1..10, 2 Y #> X 3
7.1. In和Ins
你可以使用in和ins運算子來限制變數的域，
in和ins都設定右邊的域，域是一個簡單范圍或幾個簡單范圍用\/運算子形成的并集，
一個簡單的域可以是單個數字或由雙點相連的一對邊界，邊界可以是數字，或用于最小的inf，用于最大的sup，其中任何一個都可以是被固定的變數，比如N=3, X in 1..N .，
7.2. \/運算子
域可以和\/運算子并在一起，
并集
1..3 \/ 5..7
示例2 復雜域
V in inf.. -2 \/ 0 \/ 2..16 \/ 18..sup
in約束單個變數，
ins將一個變數串列約束為同樣范圍的值，相當于用in映射整個串列，
7.3. 來自資料的域
如果域來自輸入資料呢？假設我們從某處得到一個資料結構，需要以某種方式對其約束，
將你的域匯集為項MyDomain，并在MyDomain中使用X，這有個例子
示例3 來自資料的域
% Bases is a list of ints. Constrain Var to be within B..B+2 for B % a member of Bases two_domains(Bases, Var) :- make_two_domains(Bases, Term), Var in Term. make_two_domains([H], H..HT) :- HT is H + 2. make_two_domains([H | T], '\\/'(H .. HT, TDomain)) :- HT is H + 2, make_two_domains(T, TDomain). 25 ?- two_domains([1, 8, 16], V). V in 1..3\/8..10\/16..18 ;
8. 算術運算子
你可以用算術約束來進行很多約束作業，
約束可以采用中綴算術運算式，
X + 2 #= Y * 3
可用的運算子有
unary -,
+,
-,
*,
/ (truncated integer division),
^ (exponentiation),
min,
max,
mod,
rem,
abs
9. 邏輯運算子
9.1 #\ 否定
一元運算子，反轉所包含的約束，
9.2 #/\ 與
同時約束兩邊，
9.3 #\/ 或
至少約束一邊，
10. 具體化
具體化是通過約束來控制其他約束的程序，clp(fd)包括兩個用于具體化的運算子，
10.1. #<==> 等價
每邊是個布爾型變數或是個約束，調節約束，使它們都成立或都不成立，
10.2. #==> 蘊含
如果左邊成立，則右邊必須成立，如果左邊不成立，則右邊被忽略，
示例 一些具體化的約束
在化工廠有個反應容器，容器中的溫度被限定為必須低于某個特定的值，并在不是啟動模式的情況下，還要高于另一個值，
chem_tank(Temp, Startup) :- Temp #< 800, #\ Startup #==> Temp #> 300. 我們可以將啟動模式定義在某個起始時間后的10分鐘， chem_demo(Temp, TimeNow, StartTime) :- chem_tank(Temp, TimeNow - StartTime #< 10).
注意，StartTime是作為一個約束傳入的，你可以構建一個謂詞來應用約束和應用約束所適用的條件，
作業練習
撰寫一個人與作業相匹配的小系統，這些作業對教育水平、能舉起的重量、年齡、離家距離都有要求，能夠在個人記錄中記錄特殊約束條件，比如，鮑勃在假釋期間，離家不能超過20英里，莎莉需要幫手，但她不喜歡那些不作業時到處閑逛的工人，她想找一個住在10英里以外的人幫忙，
人們都有些有趣的狀況，所以盡量把它們一般化，
對于這個練習，你可以假設（不現實地）用戶知道Prolog，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/159852.html
標籤：其他