Advertisement
Guest User

Untitled

a guest
Nov 26th, 2014
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.98 KB | None | 0 0
  1. public static Solution GBFS(State startState, State endState, Func<State, State, int> heuristic, bool considerDepth=false)
  2.         {
  3.             Stopwatch watch = Stopwatch.StartNew();
  4.             Tree<State> tree = new Tree<State>(startState);
  5.             HashSet<Node<State>> openSet = new HashSet<Node<State>>();
  6.             PriorityQueue<Node<State>> fringe = new PriorityQueue<Node<State>>();
  7.             HashSet<int> closedSet = new HashSet<int>();
  8.  
  9.             Node<State> currentNode = tree.Root;
  10.             int expandedNodes = 0;
  11.             while(currentNode != null && !currentNode.Data.Equals(endState))
  12.             {
  13.                 if (watch.ElapsedMilliseconds > (1000 * 60 * 5))
  14.                     break;
  15.                 //expand this node and add it to the closed set + remove it from the open set
  16.                 expandedNodes++;
  17.                 closedSet.Add(currentNode.Data.GetHashCode());
  18.                 openSet.Remove(currentNode);
  19.  
  20.                 //consider all nodes we can get from here that are not in the closed set
  21.                 IEnumerable<Node<State>> successors = currentNode.Data.GetAllMoves().Where(s => !closedSet.Contains(s.GetHashCode()))
  22.                     .Select(d => new Node<State>(d, currentNode));
  23.  
  24.                 //add them to the tree, and the open set
  25.                 //also keep track of the new nodes
  26.                 foreach(Node<State> successor in successors)
  27.                 {
  28.                     currentNode.Children.Add(successor);
  29.                     openSet.Add(successor);
  30.                     fringe.Add(heuristic(successor.Data, endState) + (considerDepth? successor.Depth() : 0), successor);
  31.                 }
  32.  
  33.                 //get the first node that has a heuristic value equal to the lowest heuristic value in the fringe and make that our current node
  34.                 currentNode = fringe.Pop();
  35.             }
  36.  
  37.             watch.Stop();
  38.             //no solution possible
  39.             if (currentNode == null)
  40.                 return new Solution((List<State>)null, expandedNodes, watch.ElapsedMilliseconds, tree.Size(), false);
  41.  
  42.             //so now we've reached the final state, so return the solution
  43.             return new Solution(tree.BacktrackFrom(currentNode), expandedNodes, watch.ElapsedMilliseconds, tree.Size());
  44.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement