Wal­king the tree

Stefannuss_Tree-after-30-stepsIma­gi­ne you have to find out the best way from your home flat to the next com­pu­ter store. You walk out of your flat and than you have to deci­de: Should you go right or left? You deci­de to go right and at the next cros­sing, you can walk left, strai­ght on or right again. You have to make your second decisi­on. Time goes by and after a long walk you final­ly have reached the store. The way back to your home is qui­te simp­le: You just walk back the same way. You could use bre­ad­crumbs like Han­sel and Gre­tel did to remem­ber the pathway.

The­re are many ways to reach the store and each way has its pros and cons: The shor­test is not always the the fas­test one becau­se of traf­fic lights or speed limi­ta­ti­ons. The way you usual­ly take is OK, but it might be boring becau­se you alrea­dy know all cobbles.

The board game Stefan­nuss might be sol­ved by a tree struc­tu­re. The Stefan­nuss Simu­la­ti­on is based on the tree algorithm.

Tree Struc­tu­re

A tree struc­tu­re is qui­te simi­lar to the way you have taken: Your flat is a kind or root whe­re all ways start. Each cros­sing or diver­si­on is a node whe­re you have to check out a new branch. Some decisi­ons may mis­lea­ding while other are strai­ght for­ward. The store is the desti­na­ti­on of your pathway. Once the store is reached, you don’t need to make fur­ther decisi­ons. It’s like a leaf at the end of a branch.

A tree con­sists of a sin­gle root and pro­bab­ly very much nodes. Each node has a link to one parent node or the root node. A node without child node is cal­led a leaf. The way from each leaf node to the root node is cal­led a path or a branch.

It’s very easy to use a SQL data­ba­se for buil­ding a tree. SQL data­ba­se engi­nes help you to read, insert and update nodes of a tree struc­tu­re. It’s important to under­stand, that the data­ba­se is like a spreads­heet with rows and colum­ns. Colum­ns are the place hol­ders and each row repres­ents a sin­gle node.

Our tree of nodes table struc­tu­re pro­vi­des five colum­ns per row or node:

- id         mediumint(8)   Node primary key
- id_parent  mediumint(8)   Pointer to parent node
- flag       enum(0,1)
- token_int  tinyint(3)     Depends on your problem
- token_str  varchar(16)    Depends on your problem

id and id_parent build the links bet­ween nodes. Each node has a poin­ter to its parent node. id starts with value 1 and only the root node has id = 0 and id_parent = 0

flag is a boolean indi­ca­tor. It repres­ents whe­ther the node war alrea­dy exami­ned or not.

The tree nodes table struc­tu­re pro­vi­des two colum­ns that depend on your pro­blem. I have deci­ded to pro­vi­de a column for an small inte­ger (0–255) and a column for a small text.

Root, Junc­tion, Leaf

Each node of the tree is can be clas­si­fied as Root, Junc­tion or Leaf:

Root Junc­tion Leaf
#childs >= 0
could root be the only node?
> 0
other nodes available
= 0
no other nodes from here
ID = 1
other nodes refe­rence here
> 1
other nodes refe­rence here
> 1
no other nodes refe­rence here
PID = 0
refe­ren­ces nowhere
> 1
refe­ren­ces to ano­t­her node
> 1
refe­ren­ces to ano­t­her node

Fini­te Sta­te Machine

Walk_the_Tree

Walk the tree example

Each node of the tree has a uni­que id whe­re id is the pri­ma­ry key. id_parent is not uni­que becau­se one sin­gle node can have many child nodes. Once a node is explo­red, exami­ned or visi­ted, flag is set to 1. This avoids unne­cessa­ry wal­king or loop conditions.

Ima­gi­ne you are wal­king the tree shown bes­i­de. You have just reached node id = 10. You may remem­ber whe­re you have been becau­se you have set flag = 1 on your way to that node.

Now think of a Fini­te Sta­te Machi­ne (FSM) and fol­low one of the fol­lowing action rules per step:

  • Root (you have just star­ted! explo­re child nodes)
  • Stay (stay, work on pro­blem, explo­re child nodes)
  • Up (go ahead to one of the child nodes)
  • Down (go back­ward to the parent node)

The actions per step depend on id, flag and num­ber of “undiscovered/raw” child nodes:

|id |flag|action  |Actions/ToDo
|---|----|--------|---------------------------------
|1  |0   |root    |Root Node Exception: Flag=1; Explore;
|>1 |0   |stay    |Get token from stock and put on board; Flag=1; Explore;
|>0 |1   |up/down |IF (undiscovered/raw child nodes) THEN walk up ELSE walk down;

Undiscovered/raw child nodes

What is that? The­se nodes are opti­ons that you have and whe­re you have not been befo­re. Think of the way from your flat to the next shop­ping cent­re: Undis­co­ve­r­ed child nodes are the direc­tions you can take from here: left, strai­ght, right

Undis­co­ve­r­ed child nodes have flag = 0 and pro­bab­ly fur­ther child nodes…

Cleanup the tree

My first ver­si­ons have stored all nodes the the tre n odes table. The table beca­me big­ger and big­ger even no solu­ti­ons to the pro­blem whe­re found. I have deci­ded to cleanup the tree on each down action: Remo­ve the node from tree and “for­get” this opti­on becau­se it obvious­ly does­n’t sol­ve the problem.

The Stefan­nuss pro­blem sol­ver lea­ves ~50 acti­ve nodes in the tree.

Steps per node

It takes ~ 3 steps for pla­cing one sin­gle node to the tree struc­tu­re. This ratio is based on a tree with 1.277.980 nodes and a total num­ber of 3.833.899 steps.

FSM-Action “Stay”

Con­di­ti­on:

  • id > 1
  • flag = 0

This node was found in a step befo­re. It repres­ents a sin­gle pos­si­bi­li­ty or decisi­on on the pathway. So lets pick up the given value of this node and go that direc­tion or place that token on the board. Once the value was used, drop a crumb and look for new nodes.

Important: May­be you have reached the end of our pathway! Check if this node sol­ves your problem!

If you are not finis­hed, you pro­bab­ly will find new nodes or pro­bab­ly not. Final­ly exami­ne this node again.

ToDo:

  • Pick up the value of this node do some­thing with it. Place a token on the board or put it on your list of decisions
  • Check if your pro­blem was sol­ved now!
  • Update dis­co­very sta­tus of this node (Crumb = True)
  • Search for new nodes and use ID of this as PID for new nodes
  • Run sta­te machi­ne, using the the same ID again.

FSM-Action “Up”

Con­di­ti­ons:

  • id > 0
  • flag = 1
  • at least one undis­co­ve­r­ed child nodes refe­rence here

This node was alrea­dy dis­co­ve­r­ed in a step befo­re and the­re are undis­co­ve­r­ed child nodes abo­ve. So find out the ID of one of the undis­co­ve­r­ed child nodes and use this ID to run the sta­te machi­ne again.

ToDo:

  • Get ID of an undis­co­ve­r­ed child node
  • Run sta­te machi­ne, using the ID of an undis­co­ve­r­ed child node

FSM-Action “Down”

Con­di­ti­ons:

  • id > 0
  • flag = 1
  • No undis­co­ve­r­ed child node refe­rence here

This node was alrea­dy dis­co­ve­r­ed a step befo­re and the­re are no undis­co­ve­r­ed child nodes abo­ve. This node could be a leaf node or the­re is not­hing more to do and we have to go back to find ano­t­her branch in the tree. Don’t for­get to stri­ke­out this node from you list or to remo­ve the token from the board becau­se we are on the way back toward root note and redu­ce the hops by one.

ToDo:

  • Pick up the value of this node do some­thing with it. Remo­ve the token from the board or stri­ke­out this node from the list of decisions
  • Run sta­te machi­ne, using the PID of this node as ID for the next step

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.