Альтернативные стратегии ветвления в Gecode

Question

Альтернативные стратегии ветвления в Gecode

Я пишу здесь, чтобы спросить, есть ли способ чередовать разные стратегии ветвления. Позвольте мне объяснить, у меня есть эффективная стратегия ветвления, которую мы назовем стратегией А. Самая большая проблема заключается в том, что стратегию А нельзя использовать так часто. Поэтому, когда я не могу использовать стратегию A, я использую другую стратегию, которую я назову стратегией B, которая менее эффективна.

В документации сказано, что:

Отраслевой заказ. Создание ветки регистрирует его в своем домашнем пространстве. Пространство поддерживает очередь своих ответвлений в том смысле, что ответвитель, который зарегистрирован первым, также используется первым для ответвления. Первый филиал в очереди филиалов упоминается как текущий филиал.

Итак, я предположил, что если я отправлю ответвление A, то ответвление B, ответвитель A будет иметь приоритет, и каждый раз status А говорит, что ветвления нет, ответвление Б будет использовано. Похоже, я был неправ, потому что когда status возврата филиала false больше никогда не вызывается. Вот " минимальный пример ":

#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 ответвления возврат true если следующая переменная для присвоения находится на четном индексе и если переменная может принимать значение 1 (false еще). И ответвление B status вернуть true если следующая переменная для присвоения нечетного индекса и если переменная может принимать значение 2 (false еще). С этим кодом я ожидал получить решения [1, 2, 1, 2, ...] а также [!1, !2, !1, !2, ...] (и другие комбинации, такие как [!1, 2, 1, !2, ...]) но так как филиалы располагаются, когда их status вернуть false, только две первые переменные были назначены.

Есть ли хороший способ сделать так, чтобы ветвь не утилизировалась после status вернуть false (или чередовать две разные стратегии ветвления) или я должен объединить два ответвления в один?

2

c++ constraint-programming branching-strategy gecode

Источник

user5118690 14 фев '18 в 11:19

1 ответ

Решение

Другие вопросы по тегам c++ constraint-programming branching-strategy gecode

user5118690 24 фев '18 в 18:31 2018-02-24 18:31 · Accepted Answer · 2018-02-24 18:31

Если это может кому-то помочь, вот решение, которое я использовал. По совету Патрика Трентена, я объединил контроль, создав третий разветвитель, который является вектором разветвителей. Вот реализация, которую я использовал:

Заголовок branchAllInOne.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);
}

Пространство также было изменено:

  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 и без него и получил только утечку памяти указателя для каждого ответвителя, вставленного в вектор (здесь только два). Небольшая проблема остается в том, что ветвления, добавленные в вектор, также планируются после остановки третьего ветвления (но их статус возвращается false).