samp_a_to_b.cpp

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

//======================================================================
//  samp_a_to_b.cpp - sample program: shortest path from A to B
//
//  This is a tiny sample program to show how aiParts problem-solving
//  classes can be used.  These classes will be improved over time.
//
//  Note: You can uncomment a line in the main() function so that
//        the program does not list each try.  Or, you can uncomment
//        another line and see each option in each decision.
//
//  The problem:
//    Given a number of nodes,
//      each of which is connected to one or more other nodes,
//    find the shortest path from one specified node to another.
//
//    Each node-to-node option has a 'distance', which might
//    be in miles, or it could be dollars or travel-time-minutes - 
//    something that is to be minimized.
//
//    No geometrical or spatial information is used.
//
//  The problem is constructed using classes from samp_a_to_b.h:
//      a2bProblem     a2bNode         a2bOption
//  which are subclasses of:
//      aipHHProblem   aipHHDecision   aipHHOption
//  so the problem knows how to solve itself 
//  using the High-Hope technique.  (See aipHighHope.h)
//
//  Developers/Contributers:
//    [BRM] Brian Marshall - Calgary - [e-mail]
//
//  07/11/29  [BRM] Removed class aipLog.
//  05/11/15  [BRM] Removed version number from final output.
//  05/11/01  [BRM] Parameters now specified on command line.
//                  Logs the number of tries to get best solution.
//                  Try-logging improved.
//  05/10/19  [BRM] Sample A-to-B problem made bigger and harder.
//                  Improved error-handling assembling the problem.
//                  Simplified specifying 2-way links.
//  05/09/29  [BRM] development begins
//
//----------------------------------------------------------------------
//  Building and running the executable
//
//  On Linux, you can call the compiler gcc or g++ (although on
//  Fedora, use g++ because gcc finds the wrong libraries)...
//
//    gcc -o samp_a_to_b samp_a_to_b.cpp samp_a2b.cpp
//                         aipHighHope.cpp \ 
//                         aipProblem.cpp  aipDecision.cpp \ 
//                         aipEmotion.cpp  aipPandemonium.cpp \ 
//                         aipBase.cpp     aipGood.cpp
//
//  In the example, above, spaces have been added after the 
//  backshlashs - the Borland compiler does not like them at the ends 
//  of lines, even in comments.
//
//  The executable, samp_a_to_b, can be run on the command line.
//
//  To direct the results into a file...
//    samp_a_to_b  >samp_a_to_b_test_out.txt
//
//----------------------------------------------------------------------
//  The sample problem (as of 0.8.4)
//
//                            [A]__
//                            /    |
//                      ___(R)_____[S]
//                    /    /      / |
//                 (V)__(U)_     / (T)
//                   \    |  \  /  / 
//                    \  /    [Q]_/       __(O)
//                     (C)___/   \       /   |
//                     /  \      [D]--(N)    |
//                     |   |    / | \    \__(P)
//                     |   |_(I)  |  \ 
//                     |  ___/    |  _(F)--(K)
//                     | /        | /  |
//                    (E)--[J]---[H]   |
//                     |\   \       \_(G)--(L)--(M)
//                     | \___[X]_____/  \_
//                     |    /   \          \ 
//                     |__(Y)    \__[W]____(Z)
//                         |__     /      / 
//                            \_[B]______/ 
//
//  This problem is harder than it looks.  You can see the spatial
//  relationship between the nodes; the software only knows the
//  node-to-node distances (or costs or travel-time - something
//  to be minimized).
//
//  Nodes on the best path from [A] to [B] are in square brackets.
//
//  See the function  assemble_new_problem()  for the actual
//  definition of the sample problem.
//
//----------------------------------------------------------------------
//  About trying to find a minimum...
//
//  In this sample program, we want a solution with a minimum,
//  but the problem-solving software finds a maximum.
//
//  Internally, distances are made negative (subtracted from zero)
//  so that the largest one, the least negative one, is considered
//  to be the best.  
//
//  Making the distances negative internally happens automatically
//  in the a2bOption constructor.  
//
//  The distance displayed to the user is automatically made positive 
//  again by the function a2bOption::g_opt_usr().
//
//
//----------------------------------------------------------------------
//  About number of tries...
//
//  This program uses (classes that use) the High-Hope strategy, 
//  which, at the top level, tries to solve the solution a number
//  of times and remembers the best one.
//
//  The number of tries can be set in the code of the main function.
//
//  In this fairly simple problem (26-nodes), 300 tries is ample.
//  The problem of finding a path from "A" to "B" appears to be
//  the hardest for this set of nodes; other problems ("B" to "A"
//  or "Y" to "P" require fewer tries.
//
//  For harder problems, even very-hard problems, the number of tries
//  should probably be somewhere between 1000 and 5000.
//
//----------------------------------------------------------------------
//  About the status...
//
//  This is an 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.
//
//
//----------------------------------------------------------------------

#include "samp_a2b.h"
#include <stdlib.h>
#include <iostream>
using namespace std;

//----------------------------------------------------------------------
//  Forward Declarations of Functions

a2bProblem * assemble_new_problem();

void report_solution (long distance, a2bProblem *prob);

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

int add_2_links (a2bProblem *problem, 
                 const char *node1_label, const char *node2_label, 
                 long distance);

//======================================================================
//  a2bParam  -  Parameters for running this program

class a2bParam : public aipBase {

  char    m_from_label[21];
  char    m_to_label[21];
  long    m_num_try;
  int     m_should_log_tries;
  int     m_should_log_options;

public:

  a2bParam() {
    m_from_label[0] = m_to_label[0] = '\0';
    m_num_try = 0;
    m_should_log_tries = m_should_log_options = 0;
  }

  virtual ~a2bParam() {}

  void log_usage();            // write usage information to log

  int set (int argc, char *argv[]);    // return zero on failure

  const char *  from_label () const { return m_from_label;         }
  const char *    to_label () const { return m_to_label;           }
  long             num_try () const { return m_num_try;            }
  int     should_log_tries () const { return m_should_log_tries;   }
  int   should_log_options () const { return m_should_log_options; }

};

//----------------------------------------------------------------------
//  a2bParam log_usage  -  write usage information to log

void a2bParam::log_usage() {

  log("\nUsage:\n");
  log("   samp_a_to_b <from> <to> <num-tries> [<logging>]\n");
  log("      <num-tries> is optional - default is 300\n");
  log("      <num-tries> number of solution attempts (1-5000)\n");
  log("            500 or 1000 or 3000 should find the best \n");
  log("            solution (it is a chaotic system.\n");
  log("      <logging> (optional parameter) - default is 0:\n");
  log("               0=result  - best solution found\n");
  log("               1=tries   - result of each try\n");
  log("               2=options - each option considered\n");
  log("          note: 1 and 2 can produce a lot of output\n");
  log("Examples:\n");
  log("   samp_4_a_to_b  A  B  1000\n");
  log("   samp_4_a_to_b  A  B  2000  >A_to_B_out.txt\n");
  log("   samp_4_a_to_b  S  Y   500  1  >S_to_Y_out.txt\n");
  log("   samp_4_a_to_b  Q  J    20  2  >Q_to_J_out.txt\n");
  log("\n");

}


//----------------------------------------------------------------------
//  a2bParam  set  -  set parameters from command line arguments
//                    Return zero on failure.

int a2bParam::set (int argc, char *argv[]) {

  if (argc == 1) return 0;  // no args: print usage

  if (argc < 4 || argc > 5) {
    cout << "Error: bad number of command line arguments\n";
    return 0;
  }

  if (strlen(argv[1]) > 20) {
    cout << "Error: from-label is too long ( > 20 characters)\n";
    return 0;
  }
  aip_strncpy (m_from_label, argv[1], 20);

  if (strlen(argv[2]) > 20) {
    cout << "Error: to-label is too long ( > 20 characters)\n";
    return 0;
  }
  aip_strncpy (m_to_label, argv[2], 20);

  m_num_try = atol(argv[3]);
  if (m_num_try < 1 || m_num_try > 5000) {