Performance Analysis of Searching Algorithms

Texte Universitaire , 2021 , 14 Pages

Informatique - Informatique appliquée

Problem-solving is an essential topic in Artificial Intelligence study and application. It is concerned with solving mathematical problems and clues such as puzzles. This study is primarily concerned with the ability of some searching algorithms such as Restricted Boltzmann Machines, Message Passing, Breadth First Search and Depth First Search to Solve Sudoku puzzle problems in the area of AI. For each of these methods, a code in Java language will be written and executed so that performance analysis can take place. A comparison analysis between the selected algorithms will be done. The analysis will cover some parameters such as time, space, optimality, completeness.

Abstract – Problem solving is an essential topic in Artificial Intelligence study and application. It is concerned with solving mathematical problems and clues such as puzzles. The study is primarily concerned with the ability of some searching algorithms such as Restricted Boltzmann Machines, Message Passing, Breadth First Search and Depth First Search to Solve Sudoku puzzle problems in the area of AI. For each of these methods, a code in Java language will be written and executed so that performance analysis can take place. A comparison analysis between the selected algorithms will be done. The analysis will cover some parameters e.g. Time, space, optimality, completeness.

keywords—tree graph, Sudoku puzzles, problem solving, time complexity, completeness.

I. Introduction

Problem solving in AI may be characterize as a systematic search through a range of possible actions in order to reach some predefined goal or solution. The real art of problem solving is in deciding the description of the states and operators. With this regard, there are different kinds of searching algorithms applied in artificial intelligence used for problem solving. There is a variety of problems in artificial intelligence area many of which are mathematical based in nature. Sudoku puzzle is a mathematical based problem considered as one of major problems addressed by researcher for solving. In late of 1990s, Sudoku is one of the interesting problems that gained popularity. It is not considered as a confusing and complex and therefore, may be dealt with by pencil and eraser. Many of the researchers started looking for tools, steps or methods to solve Sudoku using computer applying uninformed searching algorithms. The problem needs to be solved is formulated through the state space based on the nature of tools applied. During this process, search tree is generated by taking initial state and applying the successive function to it. The way problems are described can be formulated as follows:

1. Initial State: the initial state describes the situation at which problem starts.
2. Successor function: an intermediate states or functions describe the possible actions and their outcomes.
3. Goal Test: determines if the given state is the goal state or not. For example; in chess the goal is to reach a state called checkmate where the opponent’s king is under attack and can’t escape.
4. Path Cost: A path cost is a function that assigns a numeric cost to each path. The problem-solving agents choose a cost that reflects its own performance measure, e.g. path distance between the cities, (Russell & Norvig, 2010).

Sudoku puzzles problem:

Sudoku is a popular logic-based combinatorial puzzle game {1, 2, 3…9}. It is consisting of 81 cells, contained in a 9x9 grid (Behrooz, 2009). Each cell can contain a single integer ranging between one and nine as shown in Fig 1.

Abbildung in dieser Leseprobe nicht enthalten

Figure 1. 9x9 Sudoku Puzzle grids

- Each row of cells is only allowed to contain the integers one through nine exactly once.
- Each column of cells is only allowed to contain the integers one through nine exactly once.
- Each 3x3 sub-grid is also allowed only to contain the integers one through nine exactly once.

II. Searching Algorithms

Problem solving is basically a search or tracing towards the goal or solution of the puzzle. However there are many searching algorithms among which four have been applied in this paper. Following is a brief description of the used algorithms:

1. Restricted Boltzmann Machine algorithm (RBM): Boltzmann machines is a class of neural networks introduced in late 1980’s. They are based on statistical physics. In contrary to most other neural network methods, Boltzmann Machines are probabilistic graphical models that can be interpreted as stochastic neurons (Wolfgang Maass, 2014). Boltzmann machines where connections between the hidden neurons and the visible neurons in the original Boltzmann, RBM is an energy based model and the energy between visible and hidden units as in (Ruslan, et al., 2007).

Abbildung in dieser Leseprobe nicht enthalten

Where θ = {W,a,b} represent the parameters of the model. Wij represents the symmetric weight between ith visible unit and the jth hidden. The connection between bias term and the ith visible unit is defined by bi. aj connection between bias unit and the jth hidden unit. v and h represent the visible and hidden vectors respectively. Weights are stored in a weight matrix as in (2).

Abbildung in dieser Leseprobe nicht enthalten

The other properties of unique rows, unique columns and unique sub-grid are encoded in the same way but processed with the whole weight matrix. Equation 3 presents the joint probability distribution of visible and hidden units (Navdeep & Geoffrey, 2011).

Abbildung in dieser Leseprobe nicht enthalten

Due to stochastic nature of Boltzmann machines there is a separate probability function used to determine if a single neuron should flip its state during a discrete time step. The probability that the model assigns to the visible vector v as in (5).

Abbildung in dieser Leseprobe nicht enthalten

2. Message Passing algorithm (MP): Message passing provides powerful approximation algorithms for problems that can be formulated in terms of, probabilistic, graphical models such as factor graphs that used to represent factorization of a probability distribution function. (Arunkumar & Komala, 2015). Enabling efficient computations, such as the computation of marginal distributions through the sum-product algorithm in loopy graphical models (Frank R, et.al, 2001; Jonathan S, et.al, 2005). The sum-product algorithm in loopy graphical models, normally presented as message update equations on a factor graph, involving messages between variable nodes and their neighboring factor nodes and vice versa is based on passing messages between adjacent nodes of the underlying factor graph (Andre, et al., 2014; Frank R, et al., 2001). The following is the sum-product equations.

The constraint-to-variable messages as in (6).

Abbildung in dieser Leseprobe nicht enthalten

Where is n=x the variable node in vector Nm,n and n'=xn represent the neighbours of x in Factor Graph (FG) that all are unique. The Posteriori beliefs is presented as in (7) (Kristian, et al., 2009).

Abbildung in dieser Leseprobe nicht enthalten

The message m is a vector must contain all possibility of factor node into the specific domain Mn for a variable node. The variable-to-constraint messages as in (8).

Abbildung in dieser Leseprobe nicht enthalten

Represent P(n=x) a priori probabilities vector, if the variable node is k then the element k in probability vector is 1 and all other elements are 0. And m'ϵ Mn,m represent the neighbours of a message m into the specific domain Mn,m (Olusegun,et al.,2014).

3. Breadth First Search algorithm (BFS): Is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root, selecting a node as a root(Rong & Eric A, 2006). This root node will be at the top of the tree. The top is searched and it is level-by-level traversal and then the nodes below are searched for the solution . The properties of BFS are presented in Table 1. It exhaustively searches the entire graph or sequence without considering the goal node or solution until it finds it. From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a First in_First out queue. First in_First out mean that nodes accessed first explored or expanded first. This elaborates the level-by-level traversal policy.

Table 1. The properties of Breadth First Search

Abbildung in dieser Leseprobe nicht enthalten

[...]

• Auteurs: Mohamed Eshtawie (Auteur), Waafa Alrahman (Auteur), Nuri Elshamam (Auteur)
• Année de publication: 2021
• Pages: 14
• N° de catalogue: V1134609
• ISBN (ebook): 9783346511249
• ISBN (Livre): 9783346511256
• Langue: anglais
• mots-clé: Sudoku, Performance Analysis, Algorithm