Minizinc中迴文的有效謂詞

-1

爲了幫助我學習Minizinc，我試圖解決一個簡單的問題。我的代碼找到了答案，但我很驚訝，大約需要10秒才能運行這樣一個簡單的問題。Minizinc中迴文的有效謂詞

問題是「什麼是最小的迴文整數> 10，所以它的數字總和> 10，迴文也是？」。我希望代碼只做大的假設：答案最多隻有8位數字。

我的代碼（在toNum謂語來自hakank網站）：

predicate toNum(array[int] of var int: a, var int: n, int: base) = 
      let { int: len = length(a) } 
      in 
      n = sum(i in 1..len) (
      ceil(pow(int2float(base), int2float(len-i))) * a[i] 
     ) 
      /\ forall(i in 1..len) (a[i] >= 0 /\ a[i] < base) 
; 

predicate toNum10(array[int] of var 0..9: a, var int: n) = toNum(a, n, 10); 

predicate palindrome_array(array[int] of var int: t) = 
    let { int: l = length(t), var 1..l: d } in (
    forall(j in 1..d-1) (t[j] = 0) /\ 
    t[d] != 0 /\ 
    forall(j in d..(l+d-1) div 2) (t[j] = t[l+d-j]) 
    ) 
; 
predicate palindrome_int(var int: n) = 
    let { int: size = ceil(log10(int2float(ub(n))))+1, 
     array[1..size] of var 0..9: digits } in (
    toNum10(digits, n) /\ 
    palindrome_array(digits) 
    ) 
; 

var int: n; 
array[1..8] of var 0..9: t; 
constraint toNum10(t, n); 
constraint palindrome_int(n); 
constraint n>10; 
var int: s = sum(t); 
constraint palindrome_int(s); 
constraint s>10; 
constraint alldifferent([n, s]); 
solve minimize n;

完整版本具有以下附加限制：

var int: s2 = sum(i in 1..8) (t[i]*t[i]); 
constraint palindrome_int(s2); 
constraint s2 > 10; 

var int: s3 = sum(i in 1..8) (t[i]*t[i]*t[i]); 
constraint palindrome_int(s3); 
constraint s3 > 10; 

constraint alldifferent([n, s, s2, s3]);

什麼問題/慢我的代碼？

來源

2015-08-21 cestpasfaux

您是否可以添加「m」的定義？ – hakank

糟糕，米代表t的長度。但爲了簡單起見，我現在用一個固定值取代。 – cestpasfaux

這是另外兩個約束/變量的難題。您可以測試移出在「palindrome_int」中創建的臨時數組並將其添加到搜索策略中。注意：一個求解器（Opturion CPX）可以在<1s內解決這個問題，但是Gecode和默認的G12 fd求解器等需要更長的時間（儘管如此，我還沒有等待它們完成）。由於整數溢出，還有幾個解算器給UNSAT。 – hakank

嘗試替換「solve minim n;」採用以下標籤策略：

solve :: int_search(t, first_fail, indomain_min, complete) minimize n;

在我的機器上，它需要< 0.1s。

來源

2015-08-21 18:04:07 hakank

謝謝@hakank，現在真的很快！我現在嘗試全面練習：位數的總和和位數的總和也必須是迴文，所有數字都應該不同。它現在在合理的時間內完成（5分鐘），但我希望它會更快。 – cestpasfaux

您爲此添加了哪些約束條件？ – hakank

我用完整的代碼更新了問題。當然，我使用了你寫的同樣的策略。 – cestpasfaux

Minizinc中迴文的有效謂詞

回答

相關問題