Stack Overflow
Stack Overflow

Questions tagged [tree-search]

46 questions
114
votes
7 answers

What is the difference between graph search and tree search?

What is the difference between graph search and tree search versions regarding DFS, A* searches in artificial intelligence?
Rayhanur Rahman
  • 1,141
  • 2
  • 8
  • 4
9
votes
3 answers

Any distributed parallel tree search algorithm suggestions?

I'm writing a distributed Go/Gomoku bot. Basically the point is to distribute tree search onto many computers. With basic tree search algorithms like DFS this would be very simple, as I could just partition search space into subtrees. Though I'd…
kurczak
  • 1,521
  • 1
  • 10
  • 18
5
votes
5 answers

Library for tree search for combinatorial optimization problems

I notice that some of the "hard" combinatorial problems I come across can be cast in terms of some type of tree search like alpha-beta pruning, or beam search, or a similar algorithm. However, programming them seems like repetitively coding the same…
highBandWidth
  • 16,751
  • 20
  • 84
  • 131
4
votes
2 answers

Is it possible to do a depth first search iteratively without copying visited nodes?

Background I am searching a 2D grid for a word. We can search left/right and up/down. For example, in this grid, searching for "abef" starting at (0,0) will return True Example (grid1): Where I'm at The recursive version gives expected results…
user1594322
  • 2,008
  • 3
  • 19
  • 16
4
votes
1 answer

What would Negamax' initial function call look like were it to minimize root node rather than maximize?

Negamax typically looks like the below: function negamax(node, depth, α, β, color) is if depth = 0 or node is a terminal node then return color × the heuristic value of node childNodes := generateMoves(node) childNodes :=…
gator
  • 3,465
  • 8
  • 36
  • 76
4
votes
3 answers

Steepest Ascent Hill Climbing vs Best First Search

I am trying to solve a problem using different algorithms and Steepest Ascent Hill Climbing (SAHC) and Best First Search are two of these algorithms that I need to implement. According to Wikipedia: "In steepest ascent hill climbing all successors…
karancan
  • 2,152
  • 4
  • 23
  • 35
3
votes
3 answers

Is there a name for the do -> recurse -> undo pattern in backtracking?

In backtracking, i.e. the algorithm used for solving the n-queens problem, there are basically two ways to do the recursive call: copy the parent board to make a child board, modify the child board by placing a new queen, then do the recursive call…
Kevin Wang
  • 2,673
  • 2
  • 10
  • 18
3
votes
2 answers

How to do a Breadth First Search easily with beautiful soup?

I am trying to do a Breath First Search on a Beautiful soup tree. I know, we can do a Depth First Search with Beautiful soup like this : html = """SOME HTML FILE""" soup = BeautifulSoup(html) for child in soup.recursiveChildGenerator(): # do…
Baptiste O'Jeanson
  • 31
  • 3
3
votes
2 answers

how to prove a compatible heuristics can be a admissible heuristics in A* search algorithm

compatible heuristics (h) is the one that has below condition: h(n) <= c(n,a,n') + h(n') **************************************************** admissible heuristics (h) is the one that has below condition: 0 <= h(n) <= h*(n) h*(n) is the real…
Vahid Najafi
  • 4,654
  • 11
  • 43
  • 88
3
votes
3 answers

How to stop tree search after child was found

The following is failing to return the correct child node, even though it is actually finding the child further up the tree. It appears to drop the child after finding it, ad proceed to just keep searching the rest of the tree. private Node…
marc3l
  • 2,525
  • 7
  • 34
  • 62
3
votes
2 answers

Haskell summarize all paths through a tree

I try to summarize ALL paths though a tree that expands every level between 1 and 10 times from the root to the lowest children. My function walks recursive to all children but I have the problem that when I try to make a List of the nodes and do…
Dante Miller
  • 43
  • 4
3
votes
2 answers

Possible to simulate a simple CPU in prolog?

My understanding is that a simple model of a CPU is a state machine. When I look at prolog, it appears to tree-search (or graph search) combinations, whilst stopping at constraints running until its goals are found. I've been told that you can…
hawkeye
  • 34,745
  • 30
  • 150
  • 304
2
votes
1 answer

Java Heap Space Issue with my MCTS Gomoku player

When I run my program I get this error: Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap space at MCTSNode.setPossibleMoves(MCTSNode.java:66) at MCTSNode.Expand(MCTSNode.java:167) at…
oldfield33
  • 23
  • 5
2
votes
0 answers

Make a MCTS in Haskell

I have to implement a Monte Carlo Tree Search in Haskell. I defined a data type like this: data Tree s a = TreeNode { rGame :: s, -- state rPlayed :: a, -- action visit ::…
JoeDonald
  • 125
  • 3
  • 12
2
votes
1 answer

python 3, super() function and class inheritance - can it even be done this way?

this is my first question so I hope I won't throw too much stuff at once.. I'm implementing four different algorithms for a Vacuum Cleaner World problem. So far I made four different working .py files but I thought I would make it fancier since a…
tadek
  • 100
  • 7
1
2 3 4