Saturday, May 2, 2026
type here...
Home Blog Page 11

Uninformed Search Strategies: Breadth-First Search

Lakshmi Durga
-
0
Uninformed Search Strategies: Breadth-First Search

Uninformed Search Strategies

  • To understand this Breadth- First Search  lets take a graph with nodes A, B, C, D, E,F and G . here I expand the shallowest unexpanded node.
  • Here the fringe you see is the FIFO(First In First Out) queue .i.e., New successors go at end
  • Here in Graph Search method we create two lists open list and closed list.
  • We will place the start node In open and as we expand we take A to the closed list and generates the successors of A.
  • The successors of A that I get are placed in closed list. Here in this case I got B and C are the successors of A.
  • In the next step I take B for expansion, As we take B for expansion , place it in the closed list and generates the successors and these successors are placed in open list . Here the successors of B are D and E these are placed after the C in the next step..i.e.,C,D,E
  • In the next step we expand c not D or E. As we expand C we place that in closed list and generates the successors.
  • These successors of C i.e., F and G are placed in open list

.                                                                                                                                                   

This is how break-first search  works. I expand  the slowest unexpanded node. The fringe is a first in first out queue that is the new  successors go at the end. First I check if A  is a goal state. If A is not a goal state, I get its successors which is B and C .So, the fringe for me is B, C now. Next I check if B is a goal node  if not I get its expansion . and the next node  to be expanded is C not D this must be noted clearly. And then next node to be expanded becomes D and so on and so forth.

Procedure For Graph Search, reordering the open list

Lakshmi Durga
-
1
Procedure For Graph Search, reordering the open list

1. Create a search graph G consisting a start node S.

2. Create two lists open and close

3. Initially start node S is placed in open list.

4. Check whether the Sis goal node itself if it is the goal node then place S in the close list. If  S is not the goal node then generate the successors.

5. This generated successors are placed in open list.

6. If n is the goal node then simply come out. Otherwise, we expand the node n generating the set M of its   successors. So, we install them as a successors of M  in the open list.

7. So, add this  members of M to the open list. And then expand them further.

8.Now , if each member of M is already in G  then  we can decide whether or not to redirect  its pointer to n or if each member of M already on closed i.e., ,   one of the successor is already expanded then we can redirect its descendants  whatever are there to that pointer .Else we ignore  that node to be expanded further.

How to reorder the open list

If it is uninformed search , we can reorder  according to  some orbitary  scheme ,In case of informed search it is according to some heuristic merit .Firstly we discuss about uninformed search

           â€¢  Uninformed search is also called as blind search  this is because of the fact that it do not use any information  about the likely direction of the goal nodes. We do not have any idea of the problem domain.

            • So Informed search on the other hand most popularly called heuristic search are informed search technique in the sense that they use information about the domain. And to try usually ahead in the general direction of the goal.

            • Informed search method and uninformed search methods are distinctly different in only either use of no information or  use of information   about the domain.

•  Few of the uninform search methods are

  • Breadth-First Search
  • Depth-First Search
  • Depth-Limited Search
  • Uniform cost
  • Depth-First iterative deepening
  • Bidirectional Search

Few of Informed search methods are

  • Hill Climbing
  • Best-First
  • Greedy Search
  •  Beam Search
  • A and A *

Evaluating Search Strategies

Lakshmi Durga
-
0
Evaluating Search Strategies

We have many searching techniques  that we have discussed as uninformed but to evaluate such search strategies we talk  about the following four

Completeness

Completeness is a guarantee of  finding a solution whenever  one  exists.This means that if a solution exists andif you are searching technique can find that solution and the technique is said to be complete.

Time Complexity

Time complexity is how long does it take to find a solution and this is usually measured  in terms of the number of nodes that the searching technique expands.

Space Complexity

Space complexity  is the measurement of the maximum size of the nodes list during the search .

Optimality

 Optimality states, If a solution is found, is it guaranteed to be an optimal one? this means  is it the one with minimum cost?

Important parameters to be considered before evolving search technique

1.Maximum number of successors of any state of the search tree.i.e., the branch factor  b of the search tree.

2.Minimal length of the path in the state space between the initial and a goal state.

3.Depth d of the shallowest goal node in the search tree.

4.Maximum depth m of the state space.

Cost Of Solution

Lakshmi Durga
-
0
Cost Of Solution

1.Cost of  solution is the sum of the arc costs on the solution path.

• If all arcs have the same (unit) cost, then the solution cost is just the length of solution (number of steps/state transitions).then the solution cost is just the length of the solution or the number of steps or state transitions that is involved.

State space search  under such scenario is the process of searching through a state space for a solution, by making explicit a sufficient portion of an implicit state space graph.

Note: here we are generating the complete graph for finding a solution of problem solving. We keep on generating the graph as we keep on exploring for the solution.

In case of large state spaces, it is not possible in practical to represent the whole space.

1.Initially V= {S} , where S is the start node

•  When S is expanded its successors are generated and those nodes are added to the set V and the associated arcs are added to the set E.

• This process goes on until a goal node is reached.

So, Instead of having the whole state  space graph as it is explicitly generated and then looking for a solution, the idea is to make explicit a sufficient portion of this as I go on expanding for nodes.

And every node I expand  have to answer a question that whether it is my goal node ; if the answer is no then  getting the successor nodes and the process must  be continued  until the goal node is reached.

In general, from every node, there are many possible paths that have its partial  as prefix.

Tree , Graph searching for problem solving as state space, Formalizing search in a graph,

Lakshmi Durga
-
0

•   A tree is graph connected  without any cycles.

•  Trees comes with different types: tournament brackets, family trees, organizational charts and decision trees. In the above figure  there is a path between a to b and b to a this forms  a cycle. Here in tree no such  cycles are formed.

                          

Graph searching for problem solving as state space

•  Graph searching for problem solving as state space  search  is to find a sequence of actions to achieve a goal as searching for paths in a directed graph.

•  To solve the problem ,We define the underlying search space  and then apply a search algorithm.

•  Searching  in  graphs, therefore, provides  an appropriate  abstract model of problem solving , independent of the particular domain.

Formalizing search in a graph

  1. To formalize search in a graph, first we need to define a state space. Lets a say the state space is a graph    of vertices and edges  i.e., (V,E)

• V is a set of nodes and

•  E is a set of arcs , directed from a node to another node.

2. Each node  refers to a simple node  data structure that contains a state description  and other information  such as the parent of the node , operator that generated the node from that parent, and other book keeping data.

3. Each arc corresponds to an instance of one of the operators.

4.Whenever we are formalizing search in state space  , we are converting the entire state space into nodes with each operator with some instances that takes me  to next nodes which ends up in a directed graph. This searching in a directed graph for a path from Start to Goal gives the solution.

5. Each arc in a directed graph has a fixed positive cost associated with it corresponding to the cost of the operator.

6. Each node has a set of successor nodes corresponding to all of the legal operators as that can be applied to the source node state.

•   expanding a node means  it is a continuous process of generating  all the successor nodes and add them to their associated arcs.

7.  One or more nodes are designated as the start node later there will be a  goal test predicate that  is applied to a state to determine if its associated node is goal node.

8. A solution is a sequence of operators that is associated with a path in a state space from a start node to goal node.

Notion of path in a graph

Lakshmi Durga
-
0

The notion of a path in a graph is  clear and is shown below

•             Suppose G (V,E) is a graph with vertices v¬0, v1,v2,……,vk. and edges are e1,e2,……..,ek in which edge  ei={vi-1,vi} for i= 1,…,k.

•             The alternating sequence that I get of vertices and edges , starting from the vertice v0 to vk is a path from  v0 to vk of length k. The length is the number of edges and it is not the number of vertices.

•             The length of the path is 1,2, 3 and 4 so here is a 4 length path. And the path is made up of edges e1,e2,e3,e4 and it had vertices va,  vb,  vc  .So the path from the start to goal for the given graph is  s, e1,va, e2,vb,e3,vc,e4, g.

 Directed graph(Digraph)

A directed graph  or a Digraph in short consists of  a set V of vertices and asset E of directed edges.

•A directed edge is an ordered pair of elements of V .put another  way the pair  G(V,E) with E is a sub set of VxV is a digraph

•Digraphs allow for loops of the form (a, a), it is also possible to have two edges (a, b) and (b, a)  between the vertices  a and b

•We take the ordering of pairs in E to give each edge a direction: namely the edge (a, b) goes from a to b.

•If we draw a digraph ,we draw the edge (a, b) as an arrow from a to b.

Example:

V= {a, b, c, d}

E= {(a ,b),(a, c),(b, a),(c, c),(d, c)}

UNINFORMED SEARCH

Lakshmi Durga
-
0

Uninformed search does not have any domain knowledge. Here we are going to learn about some uniformed search strategies. Before getting into this take a review on problem solving as search, state spaces, graph searching and generic searching algorithms.

We have previously learnt about the general definitions of problem solving as search and state space

In general ,problem solving as a state space can be defined as mathematical form of finding a path from start node to a goal node in the directed path.

Graph:

A graph,  G  has  two sets , set  V of vertices and a set E of edges. Vertex set is the collection of letters or numbers.

•  The set of edges consists of  doubleton subsets of V. That is E is the subset of {a, b} such that a, b belongs to V  and a≠ b.

•  We denote the graph by G(V,E).

        If G (V,E) is a graph and {a, b} belongs to E ; Then we say vertices a and b are adjacent and the edge {a, b} Joins them or connects them or is incident on them .We call a and b the endpoints of the edge .

•   Two edges such as {a, b} and { b, c} shares same vertex  with a≠ c, are adjacent to each other.

Network categories

Rajeshwari Chiluveru
-
0

Network categories:

Depending upon the size of the network, distance, and physical characteristics network is categorized into three types local area network(LAN), wide area network (WAN), and metropolitan area network(MAN).

Fig: Categories Of Networks

Local area network(LAN):

Local area network size is limited to few kilometers, which is mainly depends on privately-owned organizations. Based upon the requirements of the organization different types of technologies are used, LAN is very simple which will connect two personal computers within the same building, office, and home.

LAN can share some resources between two PC’s or workstations, these resources sharing may include hardware or software, or information. Let us consider some examples of LAN which may found in some engineering workstations or accounting Personal computers. One of them found in business environments, like linking a workgroup of task-related computers. The large capacity disk drive is considered as a server to clients, while the size of LAN may depend on licensing restrictions and the number of users per copy of the software. Its speed is 100 or 1000 Mbps. The most commonly used LAN topologies are ring, star, and bus.

Wide Area Network(WAN):

For transferring video, images, data, and audio information even for long-distance or across the country or all over the world we require a large network that may be a wide area network which will act as a backbone to connect the internet or simple dial-up line that connect a home computer to the internet. There are two types of WAN which are switched WAN and point to point WAN from this the switched WAN is connected to the end systems, which is usually considered as a router it will connect to another WAN or LAN. Point to point WAN is normally a line leased from a telephone or cable TV provider which is connected to a home computer or a small LAN to an internet service provider(ISP).

Let’s consider examples for both switched and point to point WAN, asynchronous transfer mode(ATM) network is an example of switched WAN it has fixed-size data packets called cells.

Metropolitan Area Network(MAN):

The size of the MAN network is in between LAN and WAN, which will cover the distance area inside a city or town. The best example of a MAN network is the part of the telephone company network that provides a high-speed DSL line to the customer.

Gibbs Phenomenon and Verifying its stability for the given Unit step, unit sample, and sinusoidal response of the LTI system

Rajeshwari Chiluveru
-
0

Verifying its stability for the given Unit step, unit sample, and sinusoidal response of the LTI system

Verifying its stability for the given Unit step, unit sample, and sinusoidal response of the LTI system. A discrete-time system performs an operation on an input supported predefined criteria to supply a modified output. The input x(n) is that the system excitation and y(n) is that the system response. If the input of the system is unit impulse i.e. x(n) = δ(n) then the output of the system is understood as impulse response denoted by h(n)where h(n)= T[δ(n)] we all know that any arbitrary sequence x(n) can be represented as a weighted sum of discrete impulses.

Program:

%given difference equation y(n)-y(n-1)+.9y(n-2)=x(n);

clc;

clear all;

close all;

b=[1];

a=[1,-1,.9];

n =0:3:100;

%generating impulse signal

x1=(n==0);

%impulse response

y1=filter(b,a,x1);

subplot(3,1,1);

stem(n,y1);

xlabel(‘n’);

ylabel(‘y1(n)’);

title(‘impulse response’);

%generating step signal

x2=(n>0);

% step response

y2=filter(b,a,x2);

subplot(3,1,2);

stem(n,y2);

xlabel(‘n’);

ylabel(‘y2(n)’)

title(‘step response’);

%generating sinusoidal signal

t=0:0.1:2*pi;

x3=sin(t);

% sinusoidal response

y3=filter(b,a,x3);

subplot(3,1,3);

stem(t,y3);

xlabel(‘n’);

ylabel(‘y3(n)’);

title(‘sin response’);

% verifying stability

figure;

zplane(b,a);

Gibbs Phenomenon

The Gibbs phenomenon, the Fourier series of a piecewise continuously differentiable periodic function behaves at a jump discontinuity. The n the approximated function shows amounts of ripples at the points of discontinuity. This is known as the Gibbs Phenomena. Partial sum of the Fourier series has large oscillations near the jump, which could increase the utmost of the partial sum above that of the function itself. The overshoot doesn’t die out because the frequency increases, but approaches a finite limit The Gibbs phenomenon involves both the very fact that Fourier sums overshoot at a jump discontinuity, and that this overshoot does not die out as the frequency increases.

Program:

% Gibb’s phenomenon.

clc;

clear all;

close all;

t=linspace(-2,2,2000);

u=linspace(-2,2,2000);

sq=[zeros(1,500),2*ones(1,1000),zeros(1,500)];

k=2;

N=[1,3,7,19,49,70];

for n=1:6;

an=[];

for m=1:N(n)

 an=[an,2*k*sin(m*pi/2)/(m*pi)];

end;

fN=k/2;

for m=1:N(n)

 fN=fN+an(m)*cos(m*pi*t/2);

end;

nq=int2str(N(n));

subplot(3,2,n),plot(u,sq,’r’);hold on;

plot(t,fN); hold off; axis([-2 2 -0.5 2.5]);grid;

xlabel(‘Time’), ylabel(‘y_N(t)’);title([‘N= ‘,nq]);

end;

VERIFICATION OF BOTH LINEAR AND TIME INVARIANT SYSTEMS

Rajeshwari Chiluveru
-
0

LINEARITY PROPERTY:

If any system is claimed to be linear if it satisfies the superposition principal. Superposition principal state that Response to a weighted sum of input adequate to the corresponding weighted sum of the outputs of the system to every of the individual input signals.
If x(n) may be a input and y(n) may be a output then

y(n)=T[x(n)]

 y1(n) =T[x1(n)] and y2(n)=T[x2(n)]

 x3 =[a*x1(n) +b *x2(n) ]

Y3(n) = T [x3(n)]

 T [a*x1(n) + b*x2(n)] = a y1(n) +  b y2(n)

Program:

clc;

close all;

clear all;

% Verification of Linearity of a given System.

% a) y(n)=nx(n) b) y=x^2(n)

n=0:40;

a1=input(‘enter the scaling factor a1=’);

a2=input(‘enter the scaling factor a2=’);

x1=cos(2*pi*0.1*n);

x2=cos(2*pi*0.4*n);

x3=a1*x1+a2*x2;

%y(n)=n.x(n);

y1=n.*x1;

y2=n.*x2;

y3=n.*x3;

yt=a1*y1+a2*y2;

yt=round(yt);

y3=round(y3);

if y3==yt

 disp(‘given system [y(n)=n.x(n)]is Linear’);

else

 disp(‘given system [y(n)=n.x(n)]is non Linear’);

end

%y(n)=x(n).^2

x1=[1 2 3 4 5];

x2=[1 4 7 6 4];

x3=a1*x1+a2*x2;

y1=x1.^2;

y2=x2.^2;

y3=x3.^2;

yt=a1*y1+a2*y2;

if y3==yt

 disp(‘given system [y(n)=x(n).^2 ]is Linear’);

else

 disp(‘given system is [y(n)=x(n).^2 ]non Linear’);

end

Output will obtained as

Enter the scaling factor a1=3

Enter the scaling factor a2=5

Given system [y(n) =n.x(n)]is Linear

Given system is [y(n) =x(n).^2 ]non Linear

Time-Invariant System:

A system is named time-invariant if its input-output characteristics don’t change with time. X(t) is the input and Y(t) will be the output, X(t-k) is a delayed form of input by k seconds, Y(t-k) is delayed form of output by k seconds.

 If Y(t)=T[X(t)] while Y(t-k)=T[X(t-k)] then system is time invariant system.

clc;

close all;

clear all;

% Verification of your Time Invariance of a Discrete System

% a)y=x^2(n) b) y(n)=nx(n)

clc;

clear all;

close all;

n=1:9;

x(n)=[2 1 4 3 6 5 8 7 9];

d=3; % some time delay

xd=[zeros(1,d),x(n)];%x(n-k)

y(n)=x(n).^2;

yd=[zeros(1,d),y];%y(n-k)

disp(‘transformation of delay signal yd:’);

disp(yd)

dy=xd.^2; % T[x(n-k)]

disp(‘delay of transformation signal dy:’);

disp(dy)

if dy==yd

 disp(‘given system [y(n)=x(n).^2 ]is time invariant’);

else

 disp(‘given system is [y(n)=x(n).^2 ]not time invariant’);

end

y=n.*x;

yd=[zeros(1,d),y(n)];

disp(‘transformation of delay signal yd:’);disp(yd);

n1=1:length(xd);

dy=n1.*xd;

disp(‘delay of transformation signal dy:’);disp(dy);

if yd==dy

 disp(‘given system [y(n)=nx(n)]is a time invariant’);

else

 disp(‘given system [y(n)=nx(n)]not a time invariant’);

 end

Output:

Transformation of delay signal yd:

     0     0     0     4     1    16     9    36    25    64    49    81

Delay of transformation signal dy:

     0     0     0     4     1    16     9    36    25    64    49    81

Given system [y(n)=x(n).^2 ]is time invariant

Transformation of delay signal yd:

     0     0     0     2     2    12    12    30    30    56    56    81

Delay of transformation signal dy:

     0     0     0     8     5    24    21    48    45    80    77   108

Given system [y(n)=nx(n)]not a time invariant

1...101112...17Page 11 of 17

© Web Vidyalayam , All rights reserved. WEB VIDYALAYAM® is part of A Savvy Web LLC

About Us

Popular Category

Editor Picks