Walking the tree

Stefannuss_Tree-after-30-stepsImagine you have to find out the best way from your home flat to the next computer store. You walk out of your flat and than you have to decide: Should you go right or left? You decide to go right and at the next crossing, you can walk left, straight on or right again. You have to make your second decision. Time goes by and after a long walk you finally have reached the store. The way back to your home is quite simple: You just walk back the same way. You could use breadcrumbs like Hansel and Gretel did to remember the pathway.

There are many ways to reach the store and each way has its pros and cons: The shortest is not always the the fastest one because of traffic lights or speed limitations. The way you usually take is OK, but it might be boring because you already know all cobbles.

The board game Stefannuss might be solved by a tree structure. The Stefannuss Simulation is based on the tree algorithm.

Tree Structure

A tree structure is quite similar to the way you have taken: Your flat is a kind or root where all ways start. Each crossing or diversion is a node where you have to check out a new branch. Some decisions may misleading while other are straight forward. The store is the destination of your pathway. Once the store is reached, you don’t need to make further decisions. It’s like a leaf at the end of a branch.

A tree consists of a single root and probably very much nodes. Each node has a link to one parent node or the root node. A node without child node is called a leaf. The way from each leaf node to the root node is called a path or a branch.

It’s very easy to use a SQL database for building a tree. SQL database engines help you to read, insert and update nodes of a tree structure. It’s important to understand, that the database is like a spreadsheet with rows and columns. Columns are the place holders and each row represents a single node.

Our tree of nodes table structure provides five columns per row or node:

id and id_parent build the links between nodes. Each node has a pointer 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 indicator. It represents whether the node war already examined or not.

The tree nodes table structure provides two columns that depend on your problem. I have decided to provide a column for an small integer (0-255) and a column for a small text.

Root, Junction, Leaf

Each node of the tree is can be classified as Root, Junction or Leaf:

Root Junction Leaf
#childs >= 0
could root be the only node?
> 0
other nodes available
= 0
no other nodes from here
ID = 1
other nodes reference here
> 1
other nodes reference here
> 1
no other nodes reference here
PID = 0
references nowhere
> 1
references to another node
> 1
references to another node

Finite State Machine

Walk_the_Tree

Walk the tree example

Each node of the tree has a unique id where id is the primary key. id_parent is not unique because one single node can have many child nodes. Once a node is explored, examined or visited, flag is set to 1. This avoids unnecessary walking or loop conditions.

Imagine you are walking the tree shown beside. You have just reached node id = 10. You may remember where you have been because you have set flag = 1 on your way to that node.

Now think of a Finite State Machine (FSM) and follow one of the following action rules per step:

  • Root (you have just started! explore child nodes)
  • Stay (stay, work on problem, explore child nodes)
  • Up (go ahead to one of the child nodes)
  • Down (go backward to the parent node)

The actions per step depend on id, flag and number of „undiscovered/raw“ child nodes:

Undiscovered/raw child nodes

What is that? These nodes are options that you have and where you have not been before. Think of the way from your flat to the next shopping centre: Undiscovered child nodes are the directions you can take from here: left, straight, right

Undiscovered child nodes have flag = 0 and probably further child nodes…

Cleanup the tree

My first versions have stored all nodes the the tre n odes table. The table became bigger and bigger even no solutions to the problem where found. I have decided to cleanup the tree on each down action: Remove the node from tree and „forget“ this option because it obviously doesn’t solve the problem.

The Stefannuss problem solver leaves ~50 active nodes in the tree.

Steps per node

It takes ~ 3 steps for placing one single node to the tree structure. This ratio is based on a tree with 1.277.980 nodes and a total number of 3.833.899 steps.

FSM-Action „Stay“

Condition:

  • id > 1
  • flag = 0

This node was found in a step before. It represents a single possibility or decision on the pathway. So lets pick up the given value of this node and go that direction or place that token on the board. Once the value was used, drop a crumb and look for new nodes.

Important: Maybe you have reached the end of our pathway! Check if this node solves your problem!

If you are not finished, you probably will find new nodes or probably not. Finally examine this node again.

ToDo:

  • Pick up the value of this node do something with it. Place a token on the board or put it on your list of decisions
  • Check if your problem was solved now!
  • Update discovery status of this node (Crumb = True)
  • Search for new nodes and use ID of this as PID for new nodes
  • Run state machine, using the the same ID again.

FSM-Action „Up“

Conditions:

  • id > 0
  • flag = 1
  • at least one undiscovered child nodes reference here

This node was already discovered in a step before and there are undiscovered child nodes above. So find out the ID of one of the undiscovered child nodes and use this ID to run the state machine again.

ToDo:

  • Get ID of an undiscovered child node
  • Run state machine, using the ID of an undiscovered child node

FSM-Action „Down“

Conditions:

  • id > 0
  • flag = 1
  • No undiscovered child node reference here

This node was already discovered a step before and there are no undiscovered child nodes above. This node could be a leaf node or there is nothing more to do and we have to go back to find another branch in the tree. Don’t forget to strikeout this node from you list or to remove the token from the board because we are on the way back toward root note and reduce the hops by one.

ToDo:

  • Pick up the value of this node do something with it. Remove the token from the board or strikeout this node from the list of decisions
  • Run state machine, using the PID of this node as ID for the next step
Veröffentlicht in Technik Getagged mit:

Schreibe einen Kommentar

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

*