3

与えられた n と mに対して、エントリが 0 または 1の n × m の部分巡回行列すべてを反復処理します。同じ合計を持つ列のサブセットが 2 つ存在しないような行列があるかどうかを調べたいと思います。ここで列を追加するときは、要素ごとに行います。私の現在のコードはortools による制約プログラミングを使用しています。これが私のコードです。

from scipy.linalg import circulant
import numpy as np
import itertools
from ortools.constraint_solver import pywrapcp as cs

n = 4
m = 6

def isdetecting(matrix):
    solver = cs.Solver("scip")
    X = np.array([solver.IntVar(values) for i in range(matrix.shape[1])])
    X1 = X.tolist()
    for row in matrix:
        x = X[row].tolist()
        solver.Add(solver.Sum(x) == 0)
    db = solver.Phase(X1, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_CENTER_VALUE)
    solver.NewSearch(db)
    count = 0
#Find just one non-zero solution if there is one
    while (solver.NextSolution() and count < 2):
        solution = [x.Value() for x in X1]
        count += 1
    solver.EndSearch()
    if (count == 1):
        return True

values = [-1,0,1]
nosols = 0
for row in itertools.product([0,1],repeat = m):
    M = np.array(circulant(row)[0:n], dtype=bool)
    if isdetecting(M):
        nosols += 1
        print M.astype(int)

この行values = [-1,0,1]では、解に任意の数のゼロを使用できます。代わりに、ソリューションで許可されるゼロの正確な数を指定するにはどうすればよいですか?

4

1 に答える 1

3

or-tools/Python には、使用できるグローバルな制約 solver.Count() があります。例：

 the_count = 1 # number of 0's allowed
 solver.Add(solver.Count(X1, 0,the_count))

ここで、「the_count」は、(フラット) 配列「X1」で許可される 0 の数です。the_count は、定数または決定変数のいずれかにすることができます (そのため、さらに制約を加えてその値を制約するか、単にドメインにカウントを制約する作業を行わせることができます。たとえば、ドメイン 1..4 はカウントを 1 から 4 回の出現に制約します)。 ）。

「X1」は、チェックされる決定変数の配列です。2 番目のパラメーター「0」は、X でカウントする値です。

solver.Count() の使用例: http://hakank.org/or-tools/young_tableaux.py。

また、solver.Count() の一般化、すなわち solver.Distribute (別名 Global Cardinality Count、GCC) もあり、複数の値を同時にカウント/制約できます。使用方法の例については、私の deBruijn シーケンス モデルを参照してください: http://hakank.org/or-tools/debruijn_binary.py。

于 2014-03-10T17:05:15.307 に答える