3
$\begingroup$

I have three equations that relates five variables {a, b, c, r, s} with a sum and two ratios.

Eq. 1: a = b + c;
Eq. 2: s = b / a;
Eq. 3: r = b / c.

Given two values for any of the five variables I get a solution. But, this is not the automation problem I want to solve.

I can have the solution of variable r by simply knowing s. This is solved by a "human algorithm" as follows.

  1. Substitute a of Eq. 1 in Eq. 2.
  2. Divide the second term of the new Eq. 2 by the variable c.
  3. Replace b/c by the expression of Eq. 3.

That means s = r / (r+1).

The questions is -How can an AI algorithm solve this?, i.e. the machine should recognize that given the variable r she can obtain directly the variable s and do no require another variable.

$\endgroup$
2
$\begingroup$

What you're asking here is actually not reasoning but rather symbolic computation. Sympy is an example of a library which does it.

Explaining computer algebra systems could be a series of lectures and this is too broad for a single question. To give you an idea: (1) represent equations symbolically (2) bring them in a normal form (3) substitute.

Although it is not elegant, you can simplify the problem by brute Force: try all combinations of solving for a variable and substituting it in the other equations.

Related:

$\endgroup$
1
$\begingroup$

I would turn this problem into graph search in which vertices are "equivalent sets of equations" and edges are "valid operations" such as such as substitution, division and so on, which always ensure that all states are mathematically equivalent. A very simple example of a few states and edges (to requote from your question):

State 0:
  Eq. 1: a = b + c;
  Eq. 2: s = b / a;
  Eq. 3: r = b / c.

Operation 0-->1:
  Multiply Eq. 3 by c

State 1:
  Eq. 1: a = b + c;
  Eq. 2: s = b / a;
  Eq. 3: rc = b.

Operation 0-->2:
  Substitute Eq 1 into 2

State 2:
  Eq. 1: a = b + c;
  Eq. 2: s = b / (b+c);
  Eq. 3: r = b / c.

Operation 2-->3:
  Rearrange Eq 3 so B is on right hand side.   

etc etc

Depending on how many operations you have, this does mean that the graph could be quite large, so you may not want to generate the entire graph (actually, the graph will be infinite if the number of operations allowed is unlimited). It's also possible that the graph will contain cycles, since there may be multiple ways to reach the same state.

You will have to think about how to develop data structures for representing the states and operations. Since this is a search problem, it will help to define what your "goal" states look like (e.g. states where s is defined in terms of r).

To search the graph, I recommend one of these approaches:

  • Breadth-first search: this will find the shortest number of operations needed to reach any goal states
  • Best-first search: if the graph is too large for breadth first, you may need to guide the search to the goal states using a heuristic, e.g. you could rate states by how few variables are needed on the LHS of equations or something like that -- some experimentation will be needed here.

The exact choice of search algorithm will depend on how big the graph is, which in turns depends on how many operations/edges you want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.