Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

# Method for a process and data structure for a rule-state solution matrix

IP.com Disclosure Number: IPCOM000005604D
Publication Date: 2001-Oct-18
Document File: 5 page(s) / 103K

## Publishing Venue

The IP.com Prior Art Database

## Abstract

Disclosed is a method for a process and data structure for a rule-state solution matrix. Benefits include improved reliability and performance.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 43% of the total text.

Method for a process and data structure for a rule-state solution matrix

Disclosed is a method for a process and data structure for a rule-state solution matrix. Benefits include improved reliability and performance.

Description

The disclosed method  is a matrix that contains the solutions for a state problem. The matrix works for most type of state problems that use rules to get from a state to other solutions.

Conventionally, state problems are solved by building a tree. However, it does not often contain the most optimal solution for all situations.

The matrix can best be described by example using a water jug problem. The premise is a person has two jugs of different sizes (see Figure 1). Jug 1 holds 3 units of water. Jug 2 holds 4 units of water. The person can fill either jug, empty either jug, or transfer the contents of one jug into the other until the receiving jug is full or the source jug is empty. That is, the following actions (called rules) may be performed:

1.      Fill jug 1.

2.      Fill jug 2.

3.      Empty jug 1.

4.      Empty jug 2.

5.      Transfer the contents of jug 1 into jug 2 until either jug 1 is empty or jug 2 is full.

6.      Transfer the contents of jug 2 into jug 1 until either jug 2 is empty or jug 1 is full.

The beginning state for the example is that both jugs are empty.

The actions are entered into the matrix until all possible solutions are reached. The matrix is initialized with 000 in each location. The rows and columns relate to possible states. Each jug is an axis. The first number in each box relates to which action taken to get to that state. The second and third number relate to the other box in the matrix that represented the previous state across and then down (see Figure 2).

Filling in the matrix results in all possible ways to get from state 00 to any other state. Any state can be mapped to any spot in the matrix. The water jug problem happens to have a logical connection between state and matrix location.  For example, to get to state 32 (jug 1 full, jug 2 at 2 units), look at box 32 in the matrix. Pull off rule 1 from 32 and go to 02, by following this through, the rules are in this order: 1,5,4,5,1,5,1. Then, reverse the order to output the rules.

The steps for the most complex solution, state 32, are:

1.      Fill jug 1

2.      Transfer jug 1 into jug 2

3.      Fill jug 1

4.      Transfer jug 1 into jug 2

5.      Empty jug 2

6.      Transfer jug 1 into jug 2

7.      Fill jug 1.

This logic can be coded in Visual C++ (see Figure 3).

The matrix always contains the most optimal solution for all situations.

The matrix is faster to build than the conventional tree solution.

Jug 1                         Jug 2

|             |

|             |                           |              |

|             |                           |              |

|             |                           |              |

Fig. 1

0          1           2   3
0              |300|601|424|100|

1              |331|000|000|604|

2              |520|000|000|102|

3              |530|000|000|103|

4              |200|210|533|230|

Fig. 2

bool bSolving;

int JugOrder[5][4];

int JugArray[5][4];

int iBigJug;

int iSmallJug;

bSolving=true;

UpdateData(true);

int iBigTest=iBigJug;           int iSmallTest=iSmallJug;

int iBigOld=iBigJug;           int iSmallOld=iSmallJug;

int x=0;int y=...