いくつかの入力データの低コストの順列を見つけることによって、何かの「コスト」を最小限に抑えたいMiniZincアプリがあります。ので、私は持っています:
array[1 .. n] of var 1 .. n: Seq;
...
constraint alldifferent( [ Seq[i] | i in 1 .. n ]);
そして、Seqに基づいてコストを計算します。アプリは動作し始めていますが、実行時間が長すぎて、非常に少ない数を超えています。どうやらソルバーはすべてのnを試みます!可能性。これをスケーリングするにはどうすればよいですか?
alldifferent(Seq)が唯一の制約である場合、ソルバーはすべての順列を試行します。
ただし、多くの場合、順列には、最初の要素が1である、最初の要素が常に2番目の要素よりも小さいなど、破損する可能性のある対称性があります。これらの種類の対称性は、多くの場合、非常に問題に固有です。
モデルに他の制約がある場合、これらは、おそらく対称性を壊すことなどによって、検索スペースを削減するのに役立ちます。
通常の場合、nはどのくらいの大きさですか?いつものように、モデルの詳細は、より具体的なヘルプを提供するのに役立ちます。また、さまざまなソルバーと検索ヒューリスティックを試すことで、処理を高速化できます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加