Assignment Help - homework help

  Depth First Search, DFS algorithm Implementation and DFS Solution

Depth First Search (DFS):

Depth-first search expands the deepest node in search tree first. This is neither complete nor optimal, and consists of time complexity of O(b^m) and space complexity of O(bm), where m is the maximum depth. In search trees of large or infinite depth, the time complexity builds this impractical.

The DFS always expands one of the nodes at deepest level of the tree. Only if the search hits a dead end (that is, a non-goal node with no expansion) does the search go back and expand nodes at the shallower levels.

Algorithmically:

DFS(G) {
  for each vertex u in V
    color[u] = WHITE;
  time = 0; // global variable
  for each vertex u in V
    if (color [u] == WHITE)
      DFS_Visit(u);
}
 
DFS_Visit(u) {
  color[u] = GRAY;
  time = time + 1; // global variable
  d[u] = time; // compute discovery time d[]
  for each v adjacent to u
    if (color[v] == WHITE) {
      p[v] = u; // build DFS-tree
      DFS_Visit(u);
    }
  color[u] = BLACK;
  time = time + 1; // global variable
  f[u] = time; // compute finishing time f[]
}

DFS runs in O(V+E):

DFS can be utilized to categorize edges of G:

A) Tree edges: edges in the depth-first forest.
B) Back edges: edges (u,v) joining a vertex u to an ancestor v in the depth-first tree.
C) Forward edges: non-tree edges (u,v) joining a vertex u to a descendant v in  the depth-first tree.
D) Cross edges: all other edges

An undirected graph is acyclic if a DFS outcomes no back edges.

DFS algorithm Implementation:

Make a one-element queue comprises of the root node.

Until the queue is vacant or the goal has been reached, find out if the first element in the queue is goal node. If the first element is the goal node, do nothing. If the first element is not the goal node, eliminate the first element from the queue and add up the first element's children, if any, to the front of queue.

If the goal node has been found, announce the success, or else announce failure.

Note: This implementation varies with BFS in insertion of first element's children, DFS from FRONT whereas BFS from BACK. The worst case of DFS is the best case of BFS and vice-versa. Though, avoid employing DFS whenever the search trees are very big or with infinite maximum depths.

DFS Solution:

1 search(col)
2    if filled all columns
3       print solution and exit 
4    for each row
5       if board(row, col) is not attacked
6          place queen at (row, col)
7          search(col+1)
8          remove queen at (row, col) 

Calling search(0) starts the search. This runs rapidly, as there are relatively few choices at each and every step: once a few queens are on board, the number of non-attacked squares goes down dramatically.

This is an illustration of depth first search, since the algorithm iterates down to the bottom of the search tree as rapidly as possible: once k queens are situated on the board, the boards with even more queens are observed before examining other possible boards with just k queens. This is okay however sometimes this is desirable to find the easiest solutions before trying more complicated ones.

Depth first search checks each and every node in a search tree for some property. The search tree might appear like this:

The algorithm searches the tree by going down as far as probable and then backtracking when essential, making a sort of outline of tree as the nodes are visited. Pictorially, the tree is traversed in the following way:

991_t3.jpg

Assume that there are d decisions which must be made. (In this case d = n, the number of columns we should fill.)

Assume further that there is C choices for each decision. (In this case c = n as well, as any of the rows could potentially be selected.) Then the whole search will take time proportional to c^d, that is, an exponential amount of time. This scheme needs little space, though: as it only keeps track of as many decisions as there are to make, it needs only O(d) space. 

Depth First with Iterative Deepening (DF-ID):

The alternative to breadth first search is iterative deepening. Rather than a single breadth first search, run D depth first searches in the succession, each search permitted to go one row deeper than the prior one. That is, the first search is permitted only to explore to row 1, second to row 2, and so forth. This ‘simulates’ a breadth first search at a cost in time however a savings in space.

1 truncated_dfsearch(hnextpos, depth)
2    if board is covered
3       print solution and exit
4    if depth == 0
5       return 
6    for i from nextpos to n*n
7       put knight at i
8       search(i+1, depth-1)
9       remove knight at i 
10      dfid_search
11    for depth = 0 to max_depth
12       truncated_dfsearch(0, depth)

The space complexity of iterative deepening is merely the space complexity of depth first search: O(n). The time complexity, on other hand, is more complicated. Each truncated depth first search stopped at depth k takes ck time. Then if d is the maximum number of decisions, then depth first iterative deepening takes c^0 + c^1 + c^2 + ... + c^d time. 

Depth Limited Search: 

Depth-limited search puts a limit on how deep a depth-first search can go. When the limit occurs to be equivalent to the depth of shallowest goal state, then space and time complexity are minimized.

DLS stops to go any further if the depth of search is longer than what we have defined.

Latest technology based Programming Languages Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.
Home | Company Overview | Services | Discover Q&A | Sitemap | Contact Us | T & C | Refund Policy | Copyright Policy | Blog | Q&A | Directory

©TutorsGlobe All rights reserved 2022-2023.