Home Page Downloads Contact Us

Free Open Source Artificial Intelligence C++ Parts

aiParts Open Source Project  

Home Page
Open Source
Contact
Free Downloads
Releases and Credits
Software Status
License
v0.9.3 README File
About rrproj
assigning people and/or equipment to projects
High-Hope Technique
History of the AI
View Source Files
and how they are organized
Making Programs
Development Notes
Using aiParts
Your Application
Support and Services

aiParts Source File

//======================================================================
//  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 - bmarshal@agt.net
//
//  14/07/13  [BRM] Changed node_label from char* to const char*.
//  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    []\n");
  log("       is optional - default is 300\n");
  log("       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("       (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) {
    cout << "Error: num-try must be between 1 and 5000\n";
    return 0;
  }

  m_should_log_tries = m_should_log_options = 0;  // default

  if (argc >= 5) {
    if (argv[4][0] == '0' && argv[4][1] == '\0') {
      m_should_log_tries = m_should_log_options = 0;
    } else if (argv[4][0] == '1' && argv[4][1] == '\0') {
      m_should_log_tries = 1;
      m_should_log_options = 0;
    } else if (argv[4][0] == '2' && argv[4][1] == '\0') {
      m_should_log_tries = m_should_log_options = 1;
    } else {
      cout << "Error: logging must be 0 or 1 or 2\n";
      return 0;
    }
  }

  return 1;

}


//======================================================================
//  Program main

int main (int argc, char *argv[]) {

  a2bParam param;
  if ( ! param.set(argc,argv) ) {
    param.log_usage();
    return 1;
  }

  a2bProblem *problem = assemble_new_problem();
  if (!problem) {
     cout << "ABORT - Could not create problem\n\n";
     return 1;
  }

  problem->set_num_try(param.num_try());

  if ( param.should_log_tries() ) {
    problem->enable_log_tries();
  } else {
    problem->disable_log_tries();
  }

  if ( param.should_log_options() ) {
    problem->enable_log_options();
  } else {
    problem->disable_log_options();
  }

  long distance = problem->solve_a_to_b (param.from_label(), 
                                         param.to_label());
  if (distance == -1) {
    cout << "\nSolution could not be found.\n\n";
  } else if (distance == -2) {
    cout << "\nStarting-node not found\n\n";
  } else if (distance == -3) {
    cout << "\nEnding-node not found\n\n";
  }

  int status = 0;
  if (distance > 0) {
    report_solution (distance, problem);
  } else {
    cout << "Solve-Failure: No solution was found.\n";
    status = -1;
  }

  delete problem;

  return status;

}

//----------------------------------------------------------------------
//  Report the solution to the problem

void report_solution (long distance, a2bProblem *problem) {

  if (!distance) return;

  cout << "\n" <<  problem->num_try() << " tries done.\n";

  cout << "\nBest solution found (in try "
       << problem->solve_stat()->num_tries_to_best() 
       << ") was:\n";

  a2bSolutionItr itr = problem->solution_iterator();
  for ( a2bNode *n = itr.first(); n; n = itr.next() ) {
    cout << n->label() << "  ";
  }
  cout << " (distance = " << distance << ")\n\n";


  cout << "The best path from  A  to  B  is:\n"
       << "A  S  Q  D  H  J  X  W  B   (distance = 1850)\n\n";

}


//----------------------------------------------------------------------
//  assemble_new_problem

a2bProblem * assemble_new_problem() {

  a2bProblem *problem = new a2bProblem;
  if (!problem) { 
         cout << "ABORT - no new problem\n\n"; return 0; }

  const long num_node = 26;
  const char *node_label[num_node] = {
          "A", "B", "C", "D", "E", "F", "G", "H", "I", 
          "J", "K", "L", "M", "N", "O", "P", "Q", "R",
          "S", "T", "U", "V", "W", "X", "Y", "Z" };

  int problem_ok  = 1;

  int ok1 = 1;  // adding nodes starts ok
  
  for (long inode = 0; inodeset_owner(problem);
    problem->add_node(node);
  }    // end of loop creating and attaching nodes

  if (problem_ok && !ok1) problem_ok = ok1;

  int ok2 = problem_ok;

               // Links are added in both directions
  if (ok2) ok2 = add_2_links (problem, "A", "R", 150);
  if (ok2) ok2 = add_2_links (problem, "A", "S", 200);
  if (ok2) ok2 = add_2_links (problem, "B", "W", 150);
  if (ok2) ok2 = add_2_links (problem, "B", "Y", 400);
  if (ok2) ok2 = add_2_links (problem, "B", "Z", 400);
  if (ok2) ok2 = add_2_links (problem, "C", "E", 550);
  if (ok2) ok2 = add_2_links (problem, "C", "I", 300);
  if (ok2) ok2 = add_2_links (problem, "C", "Q", 300);
  if (ok2) ok2 = add_2_links (problem, "C", "U", 300);
  if (ok2) ok2 = add_2_links (problem, "C", "V", 300);
  if (ok2) ok2 = add_2_links (problem, "D", "F", 250);
  if (ok2) ok2 = add_2_links (problem, "D", "H", 400);
  if (ok2) ok2 = add_2_links (problem, "D", "I", 150);
  if (ok2) ok2 = add_2_links (problem, "D", "N", 150);
  if (ok2) ok2 = add_2_links (problem, "D", "Q", 200);
  if (ok2) ok2 = add_2_links (problem, "E", "I", 500);
  if (ok2) ok2 = add_2_links (problem, "E", "J", 350);
  if (ok2) ok2 = add_2_links (problem, "E", "X", 400);
  if (ok2) ok2 = add_2_links (problem, "E", "Y", 450);
  if (ok2) ok2 = add_2_links (problem, "F", "G", 250);
  if (ok2) ok2 = add_2_links (problem, "F", "H", 300);
  if (ok2) ok2 = add_2_links (problem, "F", "K", 100);
  if (ok2) ok2 = add_2_links (problem, "G", "H", 150);
  if (ok2) ok2 = add_2_links (problem, "G", "L", 100);
  if (ok2) ok2 = add_2_links (problem, "G", "X", 300);
  if (ok2) ok2 = add_2_links (problem, "G", "Z", 350);
  if (ok2) ok2 = add_2_links (problem, "H", "J", 200);
  if (ok2) ok2 = add_2_links (problem, "J", "X", 150);
  if (ok2) ok2 = add_2_links (problem, "L", "M", 100);
  if (ok2) ok2 = add_2_links (problem, "N", "O", 150);
  if (ok2) ok2 = add_2_links (problem, "N", "P", 150);
  if (ok2) ok2 = add_2_links (problem, "O", "P", 150);
  if (ok2) ok2 = add_2_links (problem, "Q", "S", 300);
  if (ok2) ok2 = add_2_links (problem, "Q", "T", 200);
  if (ok2) ok2 = add_2_links (problem, "Q", "U", 250);
  if (ok2) ok2 = add_2_links (problem, "R", "S", 300);
  if (ok2) ok2 = add_2_links (problem, "R", "U", 150);
  if (ok2) ok2 = add_2_links (problem, "R", "V", 250);
  if (ok2) ok2 = add_2_links (problem, "S", "T", 200);
  if (ok2) ok2 = add_2_links (problem, "U", "V", 150);
  if (ok2) ok2 = add_2_links (problem, "W", "X", 250);
  if (ok2) ok2 = add_2_links (problem, "W", "Z", 300);
  if (ok2) ok2 = add_2_links (problem, "X", "Y", 100);

  if (problem_ok && !ok2) {
    cout << "ABORT - error adding link \n\n";
    problem_ok = ok2;
  }

  if ( ! problem_ok ) {
    delete problem;
    return 0;
  }

  return problem;

}

//----------------------------------------------------------------------
//  add_link  -  add option to a node, linking to another node.
//               Return 1 on success, 0 on failure.

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

  int status = problem->add_link(from_label, to_label, distance);
  if (status == -1) {
    cout << "ERROR: add_link: no new a2bOption\n";
  } else if (status == -2) {
    cout << "ERROR: add_link could not find from-node "
         << from_label << aip_Endl;
  } else if (status == -3) {
    cout << "ERROR: add_link could not find to-node "
         << to_label << aip_Endl;
  } else if (status != 0) {
    cout << "ERROR: add_link unknown status code: "
         << status << aip_Endl;
  }

  return ( status ? 0 : 1 );

}

//----------------------------------------------------------------------
//  add_2_links  -  add 2 links, from node1 to node2 and
//                               from node2 to node1,
//                  both with the same distance.
//               Return 1 on success, 0 on failure.

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

  int ok = 1;

  if (ok) ok = add_link (problem, node1_label, node2_label, distance);
  if (ok) ok = add_link (problem, node2_label, node1_label, distance);

  return ok;

}

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