[ Puerto Cero Uno ]: febrero 2018

This example tries to solve the following problem: We have a NxN checker. Every (i,j) case contains k points (in this example k=4). One entry point that is a point located into the case's boundary. Two points are inside the case and the last point is an exit point, also at the boundary (different from entry). The algorithm uses Branch & Bound technique to: given an initial case and an end case, compute the minimal cost path from init to end. It also uses visitor pattern to get results. Implementation needs to be finished in some points.

Main library: "pathfinder.h"

#ifndef PATHFINDER_H_INCLUDED
#define PATHFINDER_H_INCLUDED

#include "visitor.h"

#include 
#include 
#include 
#include 
#include 

typedef struct {
B = 0, // boundary point
M = 1  // middle point
} PointType;

class Point2D {
public:
Point2D(double x, double y, PointType t){ this->_x = x; this->_y= y; this->_type = t;}
Point2D(double x, double y){ this->_x = x; this->_y= y; this->_type = PointType::I;}
~Point2D();
static double segment(Point2D * from, Point2D * to);
virtual Point2D* closest(Point2D * pa, Point2D* pb);
double getX() { return this->_x; }
double getY() { return this->_y; }
PointType getType() { return this->_type;}
bool equals (Point2D* other){
this->_type = other->_type;
this->_x = other->_x;
this->_y = other->_y;
}
private:
    double _x;
    double _y;
    PointType _type;
};

static double Point2D::segment(Point2D * a, Point2D * b) {
    return  (double)(abs(b->getX()-a->getX()) + abs(b->getY()-a->getY()));
}
/* returns the closest distance value pair  from an input points vector */
map * Point2D::closest(vector * points){
map * clst = NULL;
double da = 0, db = 0, m = 0;
Point2D* mp = NULL;
int i,j;

for(i=0;isize()-1;i++){
 da = Point2D::segment(this, points[i]);
 for(j=i+1;jsize();j++){
        db = Point2D::segment(this,points[j]);
        if(da<=db){
            m = da;
            mp = points[i];
        }else{
            m = db;
            mp = points[j];
        }
 }
}
 if(mp!=NULL){
    clst = new map();
    clst->insert(make_pair(m,mp));
 }
 return ( clst );
}

class Node {
public:
    Node(string name, double cost, int x, int y, long position, vector & values);
    ~Node();
    virtual double segment(Node* n, int atPointIdx);
    void setPosition(long pos) { this->_position = pos;}
    void setCost(double c) { this->_cost = c; }
    long getPosition() { return this->_position;}
    double getCost() { return this->_cost;}
    string getName() { return this->_name; }
    int getX() { return this->_x;}
    int getY() { return this->_y; }
    int getNextPointIdx();
    int getCurrentPointIdx() { return this->_currentPointIdx; }
    void setCurrentPointIdx(int v) { this->_currentPointIdx = v;}
    Point2D* getBPoint2D();
    Point2D * getPoint2D(int idx);
    void setUpMoveIdx(int v) { this->_currentUpMoveIdx = v; }
    void setBackMoveIdx(int v) { this->_currentBackMoveIdx = v; }
    void setFwdMoveIdx(int v){ this->_currentFwdMoveIdx = v; }
    int getUpMoveIdx(){ return this->_currentUpMoveIdx; }
    int getBackMoveIdx() { return this->_currentBackMoveIdx; }
    int getFwdMoveIdx(){ return this->_currentFwdMoveIdx; }
    vector & getValues() { return this->_values;}
    void setValues(vector & values) { this->_values = values;}
    static Node* copyNode(Node* fromNode);
    Point2D* getIntersection(Node* target);
    void computeMinPath(Node* toNode); /* this  and toNode have to have at least one boundary Point2D in common else returns NULL*/
    vector & getMinPath() { return this->_lastMinPath; }
    vector getMinCost() { return this->_lastMinCost; }
private:
    string _name;
    double _cost;
    vector _lastMinPath;
    vector _lastMinCost;
    int _x;
    int _y;
    long _position;
    int _currentPointIdx = 0;
    int _currentUpMoveIdx = 0;
    int _currentBackMoveIdx = 0;
    int _currentFwdMoveIdx = 0;
    vector _values;
};

Node::Node(string name, double cost, int x, int y, long position, vector & values) {
    this->_name = name; this->_cost = cost; this->_x= x; this->_y = y;
    this->_position = position;
    this->_values =  values;
}

static Node* Node::copyNode(Node* fromNode) {

Node * cpy = new Node(fromNode->getName(), fromNode->getCost(), fromNode->getX(), fromNode->getY(), fromNode->getPosition(), fromNode->getValues());

    cpy->setCurrentPointIdx(fromNode->getCurrentPointIdx());
    cpy->setCurrentUpMoveIdx(fromNode->getCurrentUpMoveIdx());
    cpy->setCurrentBackMoveIdx(fromNode->getCurrentBackMoveIdx());
    cpy->setCurrentFwdMoveIdx(fromNode->getCurrentFwdMoveIdx());

  return cpy;
}

int Node::getNextPointIdx() {

int next = this->_currentPointIdx +1;

if(next>=this->_values.size())
    next = -1;

 this->_currentPointIdx = next;

return this->_currentPointIdx;

}
Point2D * Node::getPoint2D(int idx){
Point2D * n =  NULL;
if(idx>=0 && idx_values.size())
    n = (Point2D *)this->values.at(idx);

    return n;
}
/* returns current indexed point if it is boundary or next boundary point */
Point2D* Node::getBPoint2D() {

    Point2D* bdry = NULL;
    int i = this->getCurrentPointIdx();
    int j = 0;
    while(i_values.size()){
        j = i % this->_values.size();
        Point2D* c = (Point2D*)(this->_values[j])->getType();
        if( c == PointType.B){
            bdry = c;
            break;
        }
        i++;
    }
   // this->setCurrentPointIdx(j);

    return bdry;
}
double Node::segment(int fromAtPointIdx, Node* to, int toAtPointIdx){
Point2D * from = this->getPoint2D(fromAtPointIdx);
Point2D * to = n->getPoint2D(toAtPointIdx);

    return Point2D::segment(from, to);

}

Point2D* Node::getIntersection(Node* from){

Point2D* intersec = NULL;
Point2D* cv = NULL;
Point2D* cf = NULL;
vector fv = from->getValues();

for(int i=0;i_values.size();i++){
    cv = this->_values[i];
    for(int j=0;jgetType() == PointType.B && cv->equals(cf)){
            intersec = cv;
            break;
        }
    }
}

 return intersec;

}
/* verifies if nodes are adjacent if true computes minimum path in current node to reach that boundary point */
void  Node::computeMinPath(Node* toNode){

vector * middles = new vector();
vector * segments = new vector();
map currentMinv = NULL;
mapgetBPoint2D();
Point2D* itsec = this->getIntersection(toNode);
if(startp!=NULL && itsec!=NULL &&
    !startp->equals(itsec)){

    middles = this->getMiddles();


}


}

class Maze {
public:
    Maze();
    Maze(int height, int legth, double scale);
    ~Maze();
    map*> * getData();
    vector* getRow(int rowNum);
    double getScale() { return this->_scale;}
    void setScale(double s) { this->_scale = s;}
    virtual int addNode(int x, int y, Node * node);
    virtual Node* getNode(int x, int y);
    virtual int getCurrentX();
    virtual int getCurrentY();
    virtual int getLevel();
    virtual int deleteNode(int x, int y);
    virtual void setNodeNumber(int x, int y, long nn);
    virtual long incNodeNumber(int delta);
    virtual long decNodeNumber(int delta);
    virtual Node* moveUp(Node* fromNode);
    virtual Node* moveFwd(Node* fromNode);
    virtual Node* moveBack(Node* fromNode);
    virtual Node* traverse(Node* innode, Node* tonode); /* returns a solution node from innode that contains optimized path to tonode*/
    virtual double computeMaxCost(Node* from, Node* to);
    virtual double computeMinCost(Node* from, Node* to);

private:
    map *> * _data;
    double _scale;
    int _level;
    int _currentX;
    int _currentY;
    long _nodeNumber;
    int _height;
    int _legth;
    const static vector * _fwdMoves = {new Point2D(0,1), new Point2D(1,0)};
    const static vector * _upMoves = {new Point2D(-1,0)};
    const static vector * _backMoves = { new Point2D(0,-1)};
};

Maze::Maze() {
    this->Maze(4,4,1);
}

Maze::Maze(int h, int l, double scale){
this->_scale = scale;
this->_level = 0;
this->_currentX = 0;
this->_currentY = 0;
this->_nodeNumber = 0;

 this->_height = h; this->length= l;

 map*>* d = new map*>(this->_height);
 vector * v;

 for(int i = 0;i_height;i++){
        v = new vector(NULL,this->_legth)
        d[i] = v;
 }

 this->_data = d;

}

Maze::~Maze(){
    delete this->_data;
}

map*> * Maze::getData() {
    return this->_data;
}

vector* Maze::getRow(int rownum) {
    return this->_data[rownum];
}
Node* Maze::getNode(int x, int y) {
    return this->_data[x][y];
}
int Maze::addNode(int x, int y , Node* n){
    this->_data[x][y] = n;
    return 0;
}

int Maze::deleteNode(int x, int y) {
    this->_data[x][y] = NULL;
    return 0;
}

int Maze::setNodeNumber(int x, int y, log nn) {
 Node * n  = this->getNode(x,y);
 if(n!=NULL){
    n->setPosition(nn);
    return 0;
 }
 return -1;
}

double Maze::computeMaxCost(Node* f, Node* t) {
Point2D * maxIntersecPoint = NULL;
Point2D * from = new Point2D(f->getX(),f->getY());
Point2D * to = new Point2D(t->getX(), t->getY());
/* intersection right to left and bottom to up */
maxIntersecPoint = new Point2D(to->getX(), from->getY());


return ( Point2D::segment(from, maxIntersecPoint) + Point2D::segment(maxIntersecPoint, to) +2 ) / this->_scale;


}

double Maze::computeMinCost(Node* f, Node* t){

Point2D * from = new Point2D(f->getX(),f->getY());
Point2D * to = new Point2D(t->getX(), t->getY());


return ( Point2D::segment(from, to)  + sqrt(2) / this->_scale;


}
class Solution:public Maze {
public:
    Solution();
    ~Solution();
    virtual vector* getOptSol();
    double getOptimalCost();
    vector* getCosts();
    void setCosts(vector * costs);
    void setOptSolIndex(int idx);
    double getOptCost();
private:
    vector * _costs
    int _optSolIndex;


};


class Backtracking {
public:
    Backtracking(Maze * maze);
    ~Backtracking();
    virtual int compute();
    virtual void accept(Visitor * v);
    virtual Solution * getSolution();
    virtual bool isSolution(int level);
    virtual bool criteria(int level, Node* n);
    virtual Node* computeNext(int level);
    virtual bool hasSibbling(int level);
    virtual int computeBack(int fromLevel);
    virtual bool isFinished(int level);
    virtual void setCurrentPoint(int x, int y);
    virtual setTargetPoint(int x, int y);
    virtual computeMaxTCost();
    virtual computeMinTCost();
private:
    long _totalNodes;
    long _numberOfNodes = 10000;
    double _minTotalCost = 100000;
    double _maxTotalCost = 0;
    int _currentLevel;
    Point2D _currentPoint = new Point2D(0,0);
    Point2D _targetPoint = NULL;
    bool isEnd = false;
    int _globalIterations = 0;
    Maze * _maze;
    Solution * _solution;
    Node* _tempNode;
    cons static _MAXITERATIONS = 10 * _numberOfNodes;
    Visitor * _visitor;
};



class PathFinder: public Backtracking {
public:
    PathFinder(Maze * maze):Backtracking(maze) {}
    void accept(Visitor * v);

private:

};

PathFinder::~PathFinder() { delete this->_maze; delete this->_solution;}

int PathFinder::compute(){
Node* solNode = NULL;
int status =  0;
this->_currentLevel = 0;

this->_tempNode = this->_maze->getNode(0,0);
if(this->_tempNode!=NULL){

 this->_solution->addNode(_tempNode->getCurrentX(),_tempNode->getCurrentY(),_tempNode);
    solNode = this->computeNext(this->_currentLevel);

    this->_totalNodes = 1;

    while(!isEnd && !isFinished(this->_currentLevel)){

        if(isSolution(this->_currentLevel)){
            isEnd = true;
        }else if(criteria(this->_currentLevel, solNode)){
            this->_solution->addNode(solNode->getCurrentX(),solNode->getCurrentY(),solNode);
            this->_tempNode = solNode;
            this->_currentLevel++;
            solNode = this->computeNext(this->_currentLevel);

        }else if(hasSibbling(this->_currentLevel)){

            solNode = this->computeNext(this->_currentLevel);
        }else {

            while(!hasSibbling(this->_currentLevel && !isFinished(this->_currentLevel))){
                this->_currentLevel = this->computeBack(_this->currentLevel);
            }
            if(!isFinished(this->_currentLevel)){
                solNode = this->computeNext(this->_currentLevel);
            }else   status = -100; /* no solution found */
        }


    }


}


return status;

}
void PathFinder::accept(Visitor * v){
        this->_visitor = v;
        this->_visitor->visit(this);
}

Solution * PathFinder::getSolution() {}
bool PathFinder::criteria(int level){}
Node* PathFinder::computeNext(int level){}
bool PathFinder::hasSibbling(int level){}
int PathFinder::computeBack(int fromLevel){}
bool PathFinder::isFinished(int level){}



#endif // PATHFINDER_H_INCLUDED

Getting results (visitor pattern): "visitor.h"

#ifndef VISITOR_H_INCLUDED
#define VISITOR_H_INCLUDED
#include "pathfinder.h"
#include 


class SolutionDisplay {
public:
    SolutionDisplay(Solution * sol);
    ~SolutionDisplay();
    virtual void print();
private:
    Solution * _solution;
};



class Visitor {
public:
    Visitor();
    ~Visitor();
    virtual void visit(Backtracking * b)
    virtual void printSolution();
    virtual vector* getSolution();
    virtual double getCost();
private:
    Solution * _solution;
    SolutionDisplay * _solutionDis;
};

void Visitor::printSolution(){
    this->_solutionDis = new SolutionDisplay(this->_solution);
    this->_solutionDis->print();
}


class PathFinderVisitor: public Visitor {
public:
        PathFinderVisitor();
        ~PathFinderVisitor();

private:

};

void PathFinderVisitor::visit(Backtracking * backtracking) {

    if(!backtracking->compute())
        this->_solution = backtracking->getSolution();

}

#endif // VISITOR_H_INCLUDED

miércoles, 21 de febrero de 2018

Branch & Bound + visitor pattern, path finder example (C++)

Entradas populares