@@ -0,0 +1,1931 @@
+// Copyright 2019 Pierre Talbot%0A%0A// Licensed under the Apache License, Version 2.0 (the %22License%22);%0A// you may not use this file except in compliance with the License.%0A// You may obtain a copy of the License at%0A%0A//     http://www.apache.org/licenses/LICENSE-2.0%0A%0A// Unless required by applicable law or agreed to in writing, software%0A// distributed under the License is distributed on an %22AS IS%22 BASIS,%0A// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A// See the License for the specific language governing permissions and%0A// limitations under the License.%0A%0Apackage bonsai.strategies;%0A%0Aimport bonsai.runtime.lattices.*;%0Aimport bonsai.statistics.Depth;%0Aimport bonsai.statistics.Discrepancy;%0A%0Aimport java.lang.System;%0A%0A// Depth-bounded discrepancy search (DDS) improves ILDS by not requiring an upper bound on the depth of the search tree.%0A// It is available here:%0A//   T. Walsh, %E2%80%9CDepth-bounded discrepancy search,%E2%80%9D in IJCAI, 1997, vol. 97, pp. 1388%E2%80%931393.%0Apublic class DDS%0A%7B%0A  // This variable represents the depth until which we can take discrepancies.%0A  ref single_space LMax max_dis_at_depth;%0A%0A  public DDS(LMax max_dis_at_depth) %7B%0A    this.max_dis_at_depth = max_dis_at_depth;%0A  %7D%0A%0A  public proc bound() =%0A    module Depth depth = new Depth();%0A    single_space LMin zero = new LMin(0);%0A    single_space LMin one = new LMin(1);%0A    par%0A    %3C%3E run depth.count();%0A    %3C%3E flow%0A         single_time LMin remaining_depth = minus(max_dis_at_depth, depth.value);%0A         par%0A           when remaining_depth %7C= zero then%0A             space nothing end;%0A             prune%0A           else%0A             when remaining_depth %7C= one then%0A               prune;%0A               space nothing end;%0A             else%0A               space nothing end;%0A             end%0A           end%0A         end%0A       end%0A    end%0A  end%0A%0A  public static LMin minus(LMax a, LMax b) %7B%0A    return new LMin(a.unwrap() - b.unwrap());%0A  %7D%0A%7D%0A

Add the depth-bounded discrepancy search (DDS) strategy.