Tree search algorithms

class Tree_search(open, max_depth)[source]

Bases: object

Tree_search is an abstract class which determines how to explore a partition tree defined by Decomposition Based Algorithm. It is based on the OPEN/CLOSED lists algorithm.

open

Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

close

Close list containing explored nodes from the partition tree.

Type

list[Fractal]

max_depth

Maximum depth of the partition tree.

Type

int

add(c)[source]

Add a node c to the fractal tree

get_next()[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

abstract add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

abstract get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

Basics

class Breadth_first_search(open, max_depth, Q=1, reverse=False)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Breadth First Search algorithm (BFS). It is inefficient with Decomposition Based Algorithm. Indeed before selecting node of the next level, all nodes of the current level must have been decomposed.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Breadth_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(c)[source]

Add a node c to the fractal tree

get_next()[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Depth_first_search

Tree search Depth based startegy

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

class Depth_first_search(open, max_depth, Q=1, reverse=False)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Depth First Search algorithm (DFS). It is inefficient with Decomposition Based Algorithm. Indeed DFS, is favorising the deep nodes no matter their quality.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Depth_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(self, c)[source]

Add a node c to the fractal tree

get_next(self)[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Breadth_first_search

Tree search Breadth based startegy

Cyclic_best_first_search

Hybrid between DFS and BestFS

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

class Best_first_search(open, max_depth, Q=1, reverse=False)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Best First Search algorithm (BestFS). At each iterations, it selects the Q-best nodes.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Best_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(self, c)[source]

Add a node c to the fractal tree

get_next(self)[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Beam_search

Memory efficient tree search algorithm based on BestFS

Cyclic_best_first_search

Hybrid between DFS and BestFS

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

Advanced

class Diverse_best_first_search(open, max_depth, Q=1, reverse=False, P=0.1, T=0.5)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Diverse Best First Search (DBFS). DBFS is an improvement of BestFS. When a node is badly evaluated, this one has no more chance to be explored. DBFS tries to overcome this problem by randomly selecting nodes according to a probability computed with its heuristic value (score) and its parents scores, or according to a probability P.

open

Initial Open list containing not explored nodes from the fractal rooted tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Diverse_best_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

P

Probability to select a random node from the open list. Determine how random the selection must be. The higher it is, the more exploration DBFS does.

Type

float, default=0.1

T

Influences the probability of a node to be selected according to its score compared to the best score from the open list.

Type

float, default=0.5

add(c)[source]

Add a node c to the fractal tree

get_next()[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Best_first_search

Tree search algorithm based on the best node from the open list

Epsilon_greedy_search

Based on BestFS, allows to randomly select a node.

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

fetch_node()[source]
get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

class Epsilon_greedy_search(open, max_depth, reverse=False, epsilon=0.1)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Epsilon Greedy Search (EGS). EGS is an improvement of BestFS. At each iteration nodes are selected randomly or according to their best score.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Epsilon_greedy_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

epsilon

Probability to select a random node from the open list. Determine how random the selection must be. The higher it is, the more exploration EGS does.

Type

float, default=0.1

add(c)[source]

Add a node c to the fractal tree

get_next()[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Best_first_search

Tree search algorithm based on the best node from the open list

Diverse_best_first_search

Tree search strategy based on an adaptative probability to select random nodes.

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

Prunning

class Beam_search(open, max_depth, Q=1, reverse=False, beam_length=10)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Beam Search algorithm (BS). BS is an improvement of BestFS. It includes a beam length which allows to prune the worst nodes.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Beam_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(c)[source]

Add a node c to the fractal tree

get_next()[source]

Get the next node to evaluate

beam_length : int, default=10

Determines the length of the open list for memory and prunning issues.

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Best_first_search

Tree search algorithm based on the best node from the open list

Cyclic_best_first_search

Hybrid between DFS and BestFS, which can also perform pruning.

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

class Cyclic_best_first_search(open, max_depth, Q=1, reverse=False)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Cyclic Best First Search (CBFS). CBFS is an hybridation between DFS and BestFS. First, CBFS tries to reach a leaf of the fractal tree to quickly determine a base score. Then CBFS will do pruning according to this value, and it will decompose the problem into subproblems by inserting nodes into contours (collection of unexplored subproblems). At each iteration CBFS selects the best subproblem according to an heuristic value. Then the child subproblems will be inserted into their respective contours according to a labelling function.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Cyclic_best_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(c)[source]

Add a node c to the fractal tree

get_next()[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Best_first_search

Tree search algorithm based on the best node from the open list

Depth_first_search

Tree search Depth based startegy

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

Miscellaneous

class Potentially_Optimal_Rectangle(open, max_depth=600, error=0.0001, maxdiv=3000)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Potentially Optimal Rectangle algorithm (POR), is a the selection strategy comming from DIRECT.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Best_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(self, c)[source]

Add a node c to the fractal tree

get_next(self)[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Beam_search

Memory efficient tree search algorithm based on BestFS

Cyclic_best_first_search

Hybrid between DFS and BestFS

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

optimal(groups)[source]
class Locally_biased_POR(open, max_depth=600, error=0.0001, maxdiv=3000)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Potentially Optimal Rectangle algorithm (POR), is a the selection strategy comming from DIRECT.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Best_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(self, c)[source]

Add a node c to the fractal tree

get_next(self)[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Beam_search

Memory efficient tree search algorithm based on BestFS

Cyclic_best_first_search

Hybrid between DFS and BestFS

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

optimal(groups)[source]
class Adaptive_POR(open, max_depth=600, error=0.01, maxdiv=3000, patience=5)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

Adaptive_POR, is a the selection strategy comming from DIRECT-Restart.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Best_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(self, c)[source]

Add a node c to the fractal tree

get_next(self)[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Beam_search

Memory efficient tree search algorithm based on BestFS

Cyclic_best_first_search

Hybrid between DFS and BestFS

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

optimal(groups)[source]
class Soo_tree_search(open, max_depth, Q=1, reverse=False)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Depth_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(self, c)[source]

Add a node c to the fractal tree

get_next(self)[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Breadth_first_search

Tree search Breadth based startegy

Cyclic_best_first_search

Hybrid between DFS and BestFS

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore

class Move_up(open, max_depth, Q=1, reverse=False)[source]

Bases: zellij.strategies.tools.tree_search.Tree_search

FDA tree search.

open

Initial Open list containing not explored nodes from the partition tree.

Type

list[Fractal]

max_depth

maximum depth of the partition tree.

Type

int

Q

Q-Depth_first_search, at each get_next, tries to return Q nodes.

Type

int, default=1

reverse

if False do a descending sort the open list, else do an ascending sort

Type

boolean, default=False

add(self, c)[source]

Add a node c to the fractal tree

get_next(self)[source]

Get the next node to evaluate

See also

Fractal

Abstract class defining what a fractal is.

FDA

Fractal Decomposition Algorithm

Tree_search

Base class

Breadth_first_search

Tree search Breadth based startegy

Cyclic_best_first_search

Hybrid between DFS and BestFS

add(c)[source]

__init__(open,max_depth)

Parameters

c (Fractal) – Add a new fractal to the tree

get_next()[source]

__init__(open, max_depth)

Returns

  • continue (boolean) – If True determine if the open list has been fully explored or not

  • nodes ({list[Fractal], -1}) – if -1 no more nodes to explore, else return a list of the next node to explore