samp_a2b.h

aiParts is a set of C++ classes that can be used to develop artificial intelligence for multi-decisi

//**********************************************************************
//  samp_a2b.h  -   Find the shortest path from A to B.
//
//  Provides: a2bProblem  a2bNode  a2bOption  a2bSolutionItr
//
//  An a2bProblem is a subclass of aipHHProblem.
//  a2bProblem::solve_a_to_b()  uses the High-Hope technique.  
//  See aipHighHope.h
//
//  An a2bProblem is setup with 
//    a set of a2bNode nodes, 
//      each of which have between 1 and 5 a2bOption options,
//        each of which refer to a node reachable from this node.
//  (ie. nodes have options that refer to a node)
//
//  Copyright (c)  2005  Brian Marshall
//
//  See the license at end of this file.
//
//  Developers/Contributers:
//    [BRM] Brian Marshall - Calgary - [e-mail]
//
//  05/11/10  [BRM] comments at top of file improved
//                  modified to log tries using aipSolveStat
//  05/10/23  [BRM] added option logging
//  05/10/20  [BRM] Fixed bug in a2bProblem::too_bad_to_go_on()
//  05/09/20  [BRM] Development begins.
//
//----------------------------------------------------------------------
//  About the status...
//
//  This is a very early version.  The existing techniques can be
//  improved - mostly by improving how different messages affect
//  the hope of decisions and options.  This should be done before
//  the High-Hope technique is made more sophisticated.
//
//  Ways of making the High-Hope technique more sophisticated include:
//    - early in problem-solving, curiosity encourages exploration
//    - later in problem-solving, greed encourages refinement
//    - if try is duplicating previous try, favor alternate options
//
//  The program will frequently find the same solution a number of
//  times, one after another.  To a certain extent, this is a normal
//  aspect of how the software works.  
//
//----------------------------------------------------------------------

#ifndef samp_a2b_h_guard
#define samp_a2b_h_guard

#include "aipHighHope.h"

//----------------------------------------------------------------------
//  Classes.  Sub-classing is shown by indentation.

//  class  aipG  is a typedef for  aipGoodness

//  Hope is a compound emotion composed of Fear, Greed and Curiosity

// class aipBase;                        ( in aipBase.h )
//   class aipProblem;                   ( in aipProblem.h )
//     class aipHHProblem;               ( in aipHighHope.h )
         class a2bProblem;         // a-to-b problem
//   class aipDemon;                     ( in aipPandemonium.h )
//     class aipDecision;                ( in aipDecision.h )
//       class aipHHDecision;            ( in aipHighHope.h )
           class a2bNode;          // decision: which node next
//     class aipOption;                  ( in aipDecision.h )
//       class aipHHOption;              ( in aipHighHope.h )
           class a2bOption;        // option: a node to go to next
// class aipDemonItr;                    ( in aipPandemonium.h )
     class a2bNodeItr;             // node iterator
   class a2bSolItrBase;            // solution iterator base class
     class a2bSolutionItr;         // best solution node iterator
     class a2bCurSolutionItr;      // current solution node iterator


//======================================================================
//  a2bProblem  -  Find the shortest path from A to B
//
//  solve_a_to_b returns the distance of the best solution found, or,
//     -1 = no solution found   
//     -2 = starting node not found
//     -3 = ending node not found
//
//  Once nodes (ie. decisions) have been added to a problem,
//  links (ie. options) can be added 2 ways:
//    - add_a2b_option() for nodes
//    - calling add_link() for the problem (returns 1 on success)
//  If add_link() is used, applications do not explicitly create
//  or deal with the options.

class a2bProblem : public aipHHProblem {

  a2bNode   * m_node_start;
  a2bNode   * m_node_end;

  a2bNode   * m_node_current;

  int  m_should_log_options;  // 0 = do not log option goodnesses

protected:

  virtual aipHHDecision * next_decision();

  virtual aipG too_bad_to_go_on() const;

  virtual int solution_is_complete () const;

  virtual void log_this_try ();

public:

  a2bProblem ();
  virtual ~a2bProblem ();

  void set_num_try (long x) { aipHHProblem::set_num_try(x); }

  void add_node  (a2bNode *x);

  int add_link (const char *from_label, 
                const char *to_label, long distance);

  void set_start_node (a2bNode *x) { m_node_start = x; }
  void set_end_node   (a2bNode *x) { m_node_end   = x; }

  void enable_log_options  () { m_should_log_options = 1; }
  void disable_log_options () { m_should_log_options = 0; }

  int should_log_options () const { return m_should_log_options; }

  a2bNode * start_node () const { return m_node_start; }
  a2bNode * end_node   () const { return m_node_end; }

  a2bNodeItr        node_iterator() const;
  a2bSolutionItr    solution_iterator() const;
  a2bCurSolutionItr cur_solution_iterator() const;

  virtual void take_msg (aipMsg *m);

  virtual long solve_a_to_b (const char *from_label,
                             const char *to_label);

  a2bNode * find_node (const char *label);

};


//======================================================================
//  a2bNode  -  a decision - a node that can reach other nodes

class a2bNode : public aipHHDecision {

  char    m_label[21];

public:

  a2bNode (const char *label);
  virtual ~a2bNode();

  void add_a2b_option (a2bOption *x);

  aipG g_hope () const;

  a2bProblem * a2b_prob () const { return (a2bProblem*)owner(); }

  a2bOption * a2b_opt_cur  () const { return (a2bOption*)opt_cur();  }
  a2bOption * a2b_opt_bsf  () const { return (a2bOption*)opt_bsf();  }

  const char * label () const { return m_label; }

};

//======================================================================
//  a2bOption 
//
//  An option, at a node, specifies another reachable node.

class a2bOption : public aipHHOption {

  a2bNode   * m_reachable_node;
  long        m_distance;

public:

  a2bOption(a2bNode *n, long distance);
  virtual ~a2bOption ();

     // the following function only works because we know
     // that each option belongs to only one decision. 
  a2bNode * a2b_dcsn () const { return (a2bNode*)owner(); }

  a2bNode  * reachable_node () const { return m_reachable_node; }
  long       distance       () const { return  m_distance;      }

  virtual aipG g_opt();
  virtual aipG g_opt_cmp();
  virtual aipG g_opt_usr();

};

//======================================================================
//  a2bNodeItr  -  Node Iterator

class a2bNodeItr : public aipDemonItr {

public:

  a2bNodeItr (aipPandemonium *p) {
    set_demon_itr(p,0);
  }

  a2bNodeItr (const a2bNodeItr& x) {
    set_demon_itr (x.pandemonium(), x.current());
  }

  virtual ~a2bNodeItr () {}

  a2bNodeItr& operator = (const a2bNodeItr& x) {
    set_demon_itr(x.pandemonium(), x.current());
    return *this;
  }

  a2bNode * first () {
    return (a2bNode*)aipDemonItr::first();
  }

  a2bNode * next () {
    return (a2bNode*)aipDemonItr::next();
  }

};

//======================================================================
//  a2bSolItrBase  -  base class for Solution Iterators
//
//  This is a parent class for Iterators that iterate through the
//  the nodes in a solution, in solution order.

class a2bSolItrBase {

  a2bNode  * m_first;
  a2bNode  * m_current;

protected:

  void set_itr (const a2bProblem *p);
  void set_itr (const a2bSolItrBase& i);

  void set_cur (a2bNode *n) { m_current = n; }

  a2bNode * const_first   () const { return m_first;   }
  a2bNode * const_current () const { return m_current; }

public:

  a2bSolItrBase ()                       { set_itr(0); }
  a2bSolItrBase (const a2bProblem *p)    { set_itr(p); }
  a2bSolItrBase (const a2bSolItrBase& x) { set_itr(x); }
  virtual ~a2bSolItrBase () {}

  a2bNode * first();
  a2bNode * next() { return 0; }                  // override this

};


//======================================================================
//  a2bSolutionItr  -  Iterator for nodes in the Best Solution

class a2bSolutionItr : public a2bSolItrBase {

public:

  a2bSolutionItr ()                        : a2bSolItrBase()  {}
  a2bSolutionItr (const a2bProblem *p)     : a2bSolItrBase(p) {}
  a2bSolutionItr (const a2bSolutionItr& x) : a2bSolItrBase(x) {}
  virtual ~a2bSolutionItr () {}

  a2bSolutionItr& operator = (const a2bSolutionItr& x) {
    set_itr (x);
    return *this;
  }

  a2bNode * first() { return a2bSolItrBase::first(); }
  a2bNode * next();

};

//======================================================================
//  a2bCurSolutionItr  -  Iterator for nodes in the current solution

class a2bCurSolutionItr : public a2bSolItrBase {

public:

  a2bCurSolutionItr ()                           : a2bSolItrBase()  {}
  a2bCurSolutionItr (const a2bProblem *p)        : a2bSolItrBase(p) {}
  a2bCurSolutionItr (const a2bCurSolutionItr& x) : a2bSolItrBase(x) {}
  virtual ~a2bCurSolutionItr () {}

  a2bCurSolutionItr& operator = (const a2bCurSolutionItr& x) {
    set_itr (x);
    return *this;
  }

  a2bNode * first() { return a2bSolItrBase::first(); }
  a2bNode * next();

};


//======================================================================

#endif

//======================================================================
//                           License
//
//   Permission is hereby granted, free of charge, to any 
//   person obtaining a copy of this software and associated 
//   documentation files (the "Software"), to deal in the Software 
//   without restriction, including without limitation the rights 
//   to use, copy, modify, merge, publish, distribute, sublicense, 
//   and/or sell copies of the Software, and to permit persons to 
//   whom the Software is furnished to do so, subject to the 
//   following conditions:
//
//   The copyright notice and this license shall be included in all 
//   copies or substantial portions of the Software.
//
//   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
//   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
//   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
//   NON-INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
//   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
//   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
//   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
//   OTHER DEALINGS IN THE SOFTWARE.
//
//**********************************************************************