Coded 中的备用分支策略

Question

我post这里想问问有没有办法交替不同的分支策略。让我解释一下，我有一个有效的分支策略，我们称之为策略 A。最大的问题是策略 A 不能经常使用。所以当我不能使用策略 A 时，我使用另一种策略，我将其称为策略 B，它的效率较低。

文档说：

Brancher order. Creating a brancher registers it with its home space. A space maintains a queue of its branchers in that the brancher that is registered first is also used first for branching. The first brancher in the queue of branchers is referred to as the current brancher.

所以，我假设如果我 post 分支器 A 那么分支器 B，分支器 A 将有优先级，每次 A 的 status 表示没有分支可做，分支器 B 将被使用。好像我错了，因为当分支器 return false 的 status 时，它再也不会被调用。这是一个“最小示例”：

#include <gecode/minimodel.hh>
#include <iostream>

using namespace Gecode;
using namespace std;

class MyChoice : public Choice {
  public:
    int pos; // Position of the variable
    int val; // Value of to assign

    MyChoice(const Brancher& b, int pos0, int val0)
      : Choice(b,2), pos(pos0), val(val0) {}

    // Report size occupied
    virtual size_t size(void) const {
      return sizeof(*this);
    }

    // Archive into e
    virtual void archive(Archive& e) const {
      Choice::archive(e);
      e << pos << val;
    }
};

class BranchA : public Brancher {
  protected:
    ViewArray<Int::IntView> x;
  public:
    BranchA(Home home, ViewArray<Int::IntView>& x0)
      : Brancher(home), x(x0) {}

    static void post(Home home, ViewArray<Int::IntView>& x) {
      (void) new (home) BranchA(home,x);
    }

    virtual size_t dispose(Space& home) {
      (void) Brancher::dispose(home);
      return sizeof(*this);
    }
    BranchA(Space& home, bool share, BranchA& b)
      : Brancher(home,share,b) {
      x.update(home,share,b.x);
    }
    virtual Brancher* copy(Space& home, bool share) {
      return new (home) BranchA(home,share,*this);
    }
    // status
    virtual bool status(const Space& home) const {
      for (int i=0; i<x.size(); i++)
        if (!x[i].assigned())
          return !i%2 && x[i].in(1);
      return false;
    }
    // choice
    virtual Choice* choice(Space& home) {
      for (int i=0; true; i++)
        if (!x[i].assigned())
          return new MyChoice(*this,i,1);
      GECODE_NEVER;
      return NULL;
    }
    virtual Choice* choice(const Space&, Archive& e) {
      int pos, val;
      e >> pos >> val;
      return new MyChoice(*this, pos, val);
    }
    // commit
    virtual ExecStatus commit(Space& home, 
                              const Choice& c,
                              unsigned int a) {
      const MyChoice& pv = static_cast<const MyChoice&>(c);
      int pos=pv.pos, val=pv.val;
      if (a == 0)
        return me_failed(x[pos].eq(home,val)) ? ES_FAILED : ES_OK;
      else
        return me_failed(x[pos].nq(home,val)) ? ES_FAILED : ES_OK;
    }
};
void branchA(Home home, const IntVarArgs& x) {
  if (home.failed()) return;
  ViewArray<Int::IntView> y(home,x);
  BranchA::post(home,y);
}
// BranchB //////////////////////////////////////////////////////

class BranchB : public Brancher {
  protected:
    ViewArray<Int::IntView> x;
  public:
    BranchB(Home home, ViewArray<Int::IntView>& x0)
      : Brancher(home), x(x0) {}
    static void post(Home home, ViewArray<Int::IntView>& x) {
      (void) new (home) BranchB(home,x);
    }
    virtual size_t dispose(Space& home) {
      (void) Brancher::dispose(home);
      return sizeof(*this);
    }
    BranchB(Space& home, bool share, BranchB& b)
      : Brancher(home,share,b) {
      x.update(home,share,b.x);
    }
    virtual Brancher* copy(Space& home, bool share) {
      return new (home) BranchB(home,share,*this);
    }
    // status
    virtual bool status(const Space& home) const {
      for (int i=0; i<x.size(); i++)
        if (!x[i].assigned())
          return i%2 && x[i].in(2);
      return false;
    }
    // choice
    virtual Choice* choice(Space& home) {
      for (int i=0; true; i++)
        if (!x[i].assigned())
          return new MyChoice(*this,i,2);
      GECODE_NEVER;
      return NULL;
    }
    virtual Choice* choice(const Space&, Archive& e) {
      int pos, val;
      e >> pos >> val;
      return new MyChoice(*this, pos, val);
    }
    // commit
    virtual ExecStatus commit(Space& home, 
                              const Choice& c,
                              unsigned int a) {
      const MyChoice& pv = static_cast<const MyChoice&>(c);
      int pos=pv.pos, val=pv.val;
      if (a == 0)
        return me_failed(x[pos].eq(home,val)) ? ES_FAILED : ES_OK;
      else
        return me_failed(x[pos].nq(home,val)) ? ES_FAILED : ES_OK;
    }
};
void branchB(Home home, const IntVarArgs& x) {
  if (home.failed()) return;
  ViewArray<Int::IntView> y(home,x);
  BranchB::post(home,y);
}

// Minimal Space ///////////////////////////////////////


class TestSpace : public Space {
  protected:
    IntVarArray x;
  public:
    TestSpace(int size)
      : x(*this, size, 0, 10) {
      branchA(*this, x);
      branchB(*this, x);
    }

    TestSpace (bool share, TestSpace& s)
      : Space(share, s) {
      x.update(*this, share, s.x);
    }

    virtual Space* copy (bool share) {
      return new TestSpace(share, *this);
    }
    void print(std::ostream& os) {
      os << "x= " << x << endl;
    }
};

// Minimal Main //////////////////////:

int main (int, char**) {
  // create model and search engine
  TestSpace* m = new TestSpace(10);
  DFS<TestSpace> e(m);
  delete m;
  // search and print all solutions
  while (TestSpace* s = e.next()) {
    s->print(cout); delete s;
  }
  return 0;
}

在此示例中，分支器的 status A return true 如果要分配的下一个变量位于 even index and if 变量可以取值 1 (false else)。如果要分配的下一个变量在 odd 索引上，则分支器 B status return true并且变量是否可以取 2 的值（否则为 false）。使用该代码，我希望获得解决方案 [1, 2, 1, 2, ...] 和 [!1, !2, !1, !2, ...]（以及其他组合，如 [!1, 2, 1, !2, ...]），但是由于分支在 status return false，只赋值了前两个变量。

有没有什么好方法可以让分支器在 status return false 之后不被处理（或者交替使用两种不同的分支策略），或者我应该合并这两个分支器成一个？

Answer 1

如果它可以帮助某人，这是我使用的解决方案。正如 Patrick Trentin 所建议的那样，我通过制作第三个分支器来统一控制，该分支器是分支器的向量。这是我使用的实现：

headerbranchAllInOne.h:

#include <gecode/minimodel.hh>

using namespace Gecode;
using namespace std;

class BranchAllInOne : public Brancher {
 protected:
  // Queue of brancher (may be better with ActorLink)
  vector<Actor *> queue;

  // Every brancher are in the brancher
  BrancherGroup group;

  mutable int toChoose;

  class ChoiceAndID : public Choice {
  public:
    // Choice of the brancher used
    Choice* c;
    /// ID of brancher used
    unsigned int id;

    ChoiceAndID(const Brancher& b, Choice * c, unsigned int id);
    virtual ~ChoiceAndID();
    virtual size_t size(void) const ;
    virtual void archive(Archive& e) const ;
  };

 public:
  BranchAllInOne(Home home);
  virtual size_t dispose(Space& home);
  BranchAllInOne(Home home, bool share, BranchAllInOne& b);
  virtual ~BranchAllInOne();
  /**
   * Check status of brancher, set toChoose value to the ID of the first 
   * brancher with alternative left
   **/
  virtual bool status(const Space&) const ;

  /**
   * Let the brancher of ID toChoose make the choice
   */
  virtual Choice* choice(Space&);
  virtual Choice* choice(const Space&, Archive& e);

  /**
   * Let the brancher of ID toChoose commit his choice
   */
  virtual ExecStatus commit(Space& home, const Choice& _c, unsigned int a);

  /// Copy brancher
  virtual Actor* copy(Space& home, bool share);

  /// Post brancher
  static BranchAllInOne * post(Home home);

  virtual void print(const Space& home,
             const Choice& c,
             unsigned int a,
             ostream& o) const ;
  void pushBrancher(Space& home, Brancher *b);
};

BranchAllInOne * branchAllInOne(Home home);

执行branchAllInOne.cpp:

#include "branchAllInOne.h"

static Brancher * ActorToBrancher(Actor *a);
// Choice implementation
BranchAllInOne::ChoiceAndID::ChoiceAndID(const Brancher& b, Choice * c0, unsigned int id0)
  : Choice(b, c0->alternatives()),
    c(c0),
    id(id0){}

BranchAllInOne::ChoiceAndID::~ChoiceAndID() {
  delete c;
}

size_t BranchAllInOne::ChoiceAndID::size(void) const {
  return sizeof(*this) + c->size();
}

void BranchAllInOne::ChoiceAndID::archive(Archive& e) const {
  Choice::archive(e);
  c->archive(e);
}

BranchAllInOne::BranchAllInOne(Home home)
  : Brancher(home),
    toChoose(-1) {
  home.notice(*this,AP_DISPOSE);
}

// brancher
BranchAllInOne * BranchAllInOne::post(Home home) {
  return new (home) BranchAllInOne(home);
}


size_t BranchAllInOne::dispose(Space& home) {
  home.ignore(*this, AP_DISPOSE);
  size_t size = queue.size() * sizeof(Actor*);
  for (unsigned int i = queue.size() ; i--;) {
    size += ActorToBrancher(queue[i])->dispose(home);
  }
  queue.~vector();

  // Making sure to kill each brancher inserted in the queue (may be useless)
  group.kill(home);

  (void) Brancher::dispose(home);
  return sizeof(*this) + size;
}

BranchAllInOne::BranchAllInOne(Home home, bool share, BranchAllInOne& b)
  : Brancher(home, share, b),
    queue(b.queue.size()),
    toChoose(b.toChoose){
  for (unsigned int i = 0 ; i < queue.size() ; i++)
    queue[i] = b.queue[i]->copy(home, share);  
}

BranchAllInOne::~BranchAllInOne() {
  for (unsigned int i = 0 ; i < queue.size() ; i++) {
    delete queue[i];
  }
  queue.~vector();
}

Actor* BranchAllInOne::copy(Space& home, bool share){
  return new (home) BranchAllInOne(home, share, *this);
}

// status
bool BranchAllInOne::status(const Space& s) const {
  for (unsigned int i = 0 ; i < queue.size() ; i++) {
    if (ActorToBrancher(queue[i])->status(s)) {
      toChoose = i;
      return true;
    }
  }  
  std::cout << std::endl;
  return false;
}

// choice
Choice* BranchAllInOne::choice(Space& s) {
  ChoiceAndID* res = new ChoiceAndID(*this,
                                     const_cast<Choice *>(ActorToBrancher(queue[toChoose])->choice(s)),
                                     toChoose);
  toChoose = -1;
  return res;
}

Choice* BranchAllInOne::choice(const Space& s, Archive& e) {
  return new ChoiceAndID(*this,
                         const_cast<Choice *>(ActorToBrancher(queue[toChoose])->choice(s, e)),
                         toChoose);
}

// Perform commit for choice \a _c and alternative \a a
ExecStatus BranchAllInOne::commit(Space& home, const Choice& c, unsigned int a) {
  const BranchAllInOne::ChoiceAndID& ch =  static_cast<const BranchAllInOne::ChoiceAndID&>(c);
  return ActorToBrancher(queue[ch.id])->commit(home, const_cast<Choice&>(*ch.c), a);

}



void BranchAllInOne::print(const Space& home,
                           const Choice& c,
                           unsigned int a,
                           ostream& o) const {
  const BranchAllInOne::ChoiceAndID& ch =  static_cast<const BranchAllInOne::ChoiceAndID&>(c);
  o << ch.id << ": ";
  ActorToBrancher(queue[ch.id])->print(home, *(ch.c), a, o);
}

void BranchAllInOne::pushBrancher(Space &home, Brancher *b) {
  queue.push_back(b);
  group.move(home, *b); 
}

static Brancher * ActorToBrancher(Actor *a) {
  return dynamic_cast<Brancher *>(a);
}

// end of BranchAllInOne implementation

BranchAllInOne* branchAllInOne(Home home) {
  if (home.failed()) return NULL;
  return BranchAllInOne::post(home);
}

我做了一些修改以获得指向我想放入向量中的分支的指针（包括每个分支的 post 函数）： brancherA例子：

BranchA * BranchA::post(Home home, ViewArray<Int::IntView>& x) {
    return new (home) BranchA(home,x);
}


BranchA * branchA(Home home, const IntVarArgs& x) {
  if (home.failed()) return NULL;
  ViewArray<Int::IntView> y(home,x);
  return BranchA::post(home,y);
}

space也修改了：

  TestSpace::TestSpace(int size)
    : x(*this, size, 0, 10) {
    BranchAllInOne * b = branchAllInOne(*this);
    b->pushBrancher(*this, branchA(*this, x));
    b->pushBrancher(*this, branchB(*this, x));
  }

我在使用和不使用 Gist 的情况下对其进行了测试，并且对于放置在向量中的每个分支（这里只有两个），只有一个指针的内存泄漏。一个小问题是，在第三个分支停止后，向量中的分支也会被调度（但它们的状态 return 为假）。

Coded 中的备用分支策略

Alternate branching strategies in Gecode

c++

constraint-programming

branching-strategy

gecode