Background Information

An uninformed search is a search algorithm for a given object in a graph, without any other knowledge to help its search.  For example, breadth-first search starts at a point in the graph and checks each node, generation by generation.  Depth-first search starts at a point in the graph and continues to check down a path until it meets a dead-end, then retraces to check other paths.  Iterative-deepening search uses depth-first search, but limits the number of generations the algorithm checks down to.


Task to Complete

Develop a program for uninformed searching.  This program must:

  • be able to store a graph of nodes, where each node can have any number of adjacent nodes
  • be able to search for a given nod using breadth-first, depth-first, and iterative-deepening algorithms
  • be able to show a path from the starting node to the goal node after the goal node has been found

October 18th, 2016 – Node, Graph, and GraphSearcher Classes

  • Create the class Node to hold the nodes in the graph, that will have:
    • List adjacent of the connected nodes
    • String text to store the data
    • boolean visited to record whether or not it has been searched already
    • accessor and mutator methods for text
    • method connect(Node n) to add n to adjacent while adding this to n‘s adjacent
    • method getAdjacents() to return the adjacent
    • accessor and mutator methods isVisited() and setVisited() for visited
  • Create the class Graph to represent the graph used to store the nodes, which has:
    • Node head, referring to the Node in the graph that the search begins from.  (It can be any node in the graph because all nodes are connected.)
    • createGraph() method which sets up a preset graph by creating more Nodes and connecting them
    • creating accessor and mutator methods for head
  • Create the “singleton” class GraphSearcher to search a graph, with:
    • static getInstance() method (part of the “singleton” setup)
    • breadthFirstSearch() method that takes in a Graph g to search in and a String txt to search for, and will return a List<Node> with the path
    • depthFirstSearch() method that takes in a Graph g to search in and a String txt to search for, and will return a List<Node> with the path
    • iterativeDeepeningSearch() method that takes in a Graph g to search in, a String txt to search for, and an int limit for the depth limit, and will return a List<Node> with the path

October 20th, 2016 – Search Algorithms

  • Adding a retrace(Node n) method to GraphSearcher that will retrace the path that n was found with, through:
    • having each Node store another Node parent, which:
      • can be used via accessor/mutator methods in Node
      • will be filled with whichever Node called on this Node first
    • recursively calling the getParent() method of each successive Node, and storing them in a List<Node> path
    • returning path
  • Implementing the breadthFirstSearch() method in GraphSearcher by having it:
    • create a List<Node> fringe to store the nodes that need to be checked
    • add head to fringe, and marking head as visited
    • run a while loop while fringe isn’t empty (meaning there is something to check), that:
      • creates a List<Node> fringeTemp to store the nodes to add to fringe later
      • using a for-each loop to loop through fringe, that will:
        • check each Node in fringe to see if it matches txt, and if it does, calling the retrace() method on that Node and returning the result
        • if not, loop through all the unvisited “adjacents” and add them to fringeTemp
      • moving all the elements from fringeTemp into fringe, and loops back to the start again
    • if fringe becomes empty but nothing has been found, then return null
  • Implementing the depthFirstSearch() method in GraphSearcher by:
    • creating a dfsRecursive(String txt) method in Node that will:
      • check if it matches txt, and if it does, returning itself
      • looping through the unvisited “adjacents”, and calling their dfsRecursive() methods, only returning a result if the method returns something other than null
      • return null if nothing has been found
    • calling the dfsRecursive() method on head
    • returning the result of calling retrace() on the above result
  • Implementing the iterativeDeepeningSearch() method in GraphSearcher by:
    • creating a List<Node> fringe to store the nodes that need to be checked
    • adding head to fringe, and marking head as visited
    • creating a idsRecursive(String txt, int limit) method in Node that does the same thing as dfsRecursive(), except that:
      • if limit is equal to 1, then instead of looping through the “adjacents”, it adds all the unvisited “adjacents” to fringeTemp
      • when calling the idsRecursive() methods of its unvisited “adjacents”, it passes in limit – 1
    • running a while loop while fringe is not empty, that:
      • creates a new fringeTemp
      • loops through fringe using a for-each loop, and:
        • calls the idsRecursive() method on each Node
        • if something other than null is returned, returning the retrace() of the result
      • moves all the elements from fringeTemp into fringe, and looping back to the start again
    • if fringe() becomes empty but nothing has been found, then returning null
  • Adding a main() method that creates a Graph and tests the various search algorithms on it
  • At this point, the program is pretty much complete
Advertisements