Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
18
votes
1answer
25k views

What is the difference between tree search and graph search?

I have read various answers to this question at different places, but I am still missing something. What I have understood is that a graph search holds a closed list, with all expanded nodes, so ...
12
votes
3answers
728 views

Why teaching only search algorithms in a short introductory AI course?

I understood that the concept of search is important in AI. There's a question on this website regarding this topic, but one could also intuitively understand why. I've had an introductory course on ...
12
votes
1answer
17k views

Why is A* optimal if the heuristic function is admissible?

A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...
11
votes
5answers
958 views

Are methods of exhaustive search considered to be AI?

Some programs do exhaustive searches for a solution while others do heuristic searches for a similar answer. For example, in chess, the search for the best next move tends to be more exhaustive in ...
10
votes
8answers
4k views

Why is search important in AI?

Why is search important in AI? What kinds of search algorithms are used in AI? How do they improve the result of an AI?
9
votes
2answers
1k views

Why is depth-first search an artificial intelligence algorithm?

I'm new to the artificial intelligence field. In our first chapters, there is one topic called "problem-solving by searching". After searching for it on the internet, I found the depth-first ...
9
votes
1answer
13k views

What is the fringe in the context of search algorithms?

What is the fringe in the context of search algorithms?
9
votes
2answers
16k views

What are the limitations of the hill climbing algorithm and how to overcome them?

What are the limitations of the hill climbing algorithm? How can we overcome these limitations?
9
votes
2answers
318 views

What is the difference between search and learning?

I came across an article, The Bitter Truth, via the Two Minute Papers YouTube Channel. Rich Sutton says... One thing that should be learned from the bitter lesson is the great power of general ...
9
votes
4answers
4k views

When to choose Stochastic Hill Climbing over Steepest Hill Climbing?

Stochastic Hill Climbing generally performs worse than Steepest Hill Climbing, but what are the cases in which the former performs better?
8
votes
2answers
219 views

Are there local search algorithms that make use of memory to give better solutions?

I have been studying local search algorithms such as greedy hill-climbing, stochastic hill-climbing, simulated annealing, etc. I have noticed that most of these methods take up very little memory as ...
7
votes
3answers
37k views

What are the differences between A* and greedy best-first search?

What are the differences between the A* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?
7
votes
3answers
691 views

More effective way to improve the heuristics of an AI... evolution or testing between thousands of pre-determined sets of heuristics?

I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can ...
7
votes
3answers
1k views

Why does Monte Carlo work when a real opponent's behavior may not be random

I am learning about Monte Carlo algorithms and struggling to understand the following: If simulations are based on random moves, how can the modeling of the opponent's behavior work well? For ...
7
votes
2answers
2k views

Can someone help me to understand the alpha-beta pruning algorithm?

I understand the minimax algorithm, but I am unable to understand deeply the minimax algorithm with alpha-beta pruning, even after having looked up several sources (on the web) and having tried to ...
7
votes
1answer
183 views

A* is similar to Dijkstra with reduced cost

According to this Wikipedia article If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge),...
7
votes
2answers
3k views

What is the difference between search and planning?

I'm reading the book Artificial Intelligence: A Modern Approach (by Stuart Russell and Peter Norvig). However, I don't understand the difference between search and planning. I was more confused when I ...
6
votes
1answer
9k views

How is iterative deepening A* better than A*?

The iterative deepening A* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals. The A* algorithm evaluates nodes by combining the ...
6
votes
1answer
3k views

What are the state space and the state transition function in AI?

I'm studying for my AI final exam, and I'm stuck in the state space representation. I understand initial and goal states, but what I don't understand is the state space and state transition function. ...
6
votes
1answer
194 views

Can two admissable heuristics not dominate each other?

I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am ...
6
votes
2answers
603 views

Why is the larger value, as opposed to the smaller one, chosen, in the hill climbing algorithm?

In the hill climbing algorithm, the greater value, compared to the current value, is selected, but I cannot understand why it takes the larger value instead of the smaller one. Why is that? I greatly ...
6
votes
1answer
5k views

What is the difference between local search and global search algorithms?

What is the difference between local search and global (or complete) search algorithms?
6
votes
1answer
826 views

How do we determine whether a heuristic function is better than another?

I am trying to solve a maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions. Currently, I explored the Manhattan and Euclidean ...
6
votes
2answers
2k views

Are leaf nodes included in the calculation of average branching factor for search trees?

In the search tree below, there are 11 nodes, 5 of which are leaves. There are 10 branches. Is the average branching factor given by 10/6, or 10/11? Are leaves included in the calculation? ...
6
votes
1answer
287 views

To deal with infinite loops, should I do a deeper search of the best moves with the same value, in alpha-beta pruning?

I have implemented minimax with alpha-beta pruning to play checkers. As my value heuristic, I am using only the summation of material value on the board regardless of the position. My main issue lays ...
6
votes
1answer
854 views

Are iterative deepening, principal variation search or quiescence search extensions of alpha-beta pruning?

I know that there are several optimizations for alpha-beta pruning. For example, I have come across iterative deepening, principal variation search, or quiescence search. However, I am a little bit ...
5
votes
2answers
1k views

How does A* search work given there are multiple goal states?

When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture. These are the heuristic estimates: ...
5
votes
2answers
2k views

How can I formulate the map colouring problem as a hill climbing search problem?

I have a map. I need to colour it with $k$ colours, such that two adjacent regions do not share a colour. How can I formulate the map colouring problem as a hill climbing search problem?
5
votes
1answer
855 views

How to create an AI to solve a word search?

This at first sounds ridiculous. Of course there is an easy way to write a program to solve a wordsearch. But what I would like to do is write a program that solves a word-search like a human. That ...
5
votes
1answer
3k views

What are the differences between uniform-cost search and greedy best-first search?

What are the differences between the uniform-cost search (UCS) and greedy best-first search (GBFS) algorithms? How would you convert a UCS into a GBFS?
5
votes
1answer
1k views

Is the 'direction' considered, when determining the branching factor in bidirectional search?

If I am correct, the branching factor is the maximum number of successors of any node. When I am applying bidirectional search to a transition graph like this one below If 11 is the goal state and I ...
5
votes
1answer
7k views

How does the uniform-cost search algorithm work?

What is the uniform-cost search (UCS) algorithm? How does it work? I would appreciate seeing a graphical execution of the algorithm. How does the frontier evolve in the case of UCS?
5
votes
1answer
221 views

Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality. I understand the max-min inequality, basically ...
4
votes
1answer
7k views

How do I show that uniform-cost search is a special case of A*?

How do I show that uniform-cost search is a special case of A*? How do I prove this?
4
votes
2answers
4k views

If an heuristic is not admissible, can it be consistent?

I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in ...
4
votes
1answer
673 views

Transposition table is only used for roughly 17% of the nodes - is this expected?

I'm making a Connect Four game using the typical minimax + alpha-beta pruning algorithms. I just implemented a Transposition Table, but my tests tell me the TT only helps 17% of the time. By this I ...
4
votes
2answers
2k views

When should I use simulated annealing as opposed to a genetic algorithm?

What kind of problems is simulated annealing better suited for compared to genetic algorithms? From my experience, genetic algorithms seem to perform better than simulated annealing for most problems....
4
votes
1answer
251 views

Given an image and two points $A$ and $B$ on that image, how could we find a path from $A$ to $B$?

If we have a search or path-finding problem, A* and Dijkstra's algorithm require that we formulate it as a search in a graph with nodes and connections between these nodes. If there are obstacles, we ...
4
votes
1answer
3k views

What is a good heuristic function for A* to solve the "blocks world" game?

I am developing a heuristic solution for the blocks world problem. I tried using the number of blocks out of place as my $h(n)$. It seems a little ineffective. Can someone please point out a suitable ...
4
votes
1answer
2k views

Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?

Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}. If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) ...
4
votes
1answer
5k views

How is simulated annealing better than hill climbing methods?

In hill climbing methods, at each step, the current solution is replaced with the best neighbour (that is, the neighbour with highest/smallest value). In simulated annealing, "downhills" moves are ...
4
votes
1answer
186 views

How do I train a bot to solve Katona style problems?

Cognitive psychology is researched since the 1940s. The idea was to understand human problem solving and the importance of heuristics in it. George Katona (an early psychologist) published in the ...
4
votes
1answer
508 views

Why is it possible to eliminate this branch with alpha-beta pruning?

Can someone explain to me why it is possible to eliminate the rest of the middle branch in this image for alpha-beta pruning? I am confused because it seems the only information you know is that Helen ...
4
votes
1answer
1k views

Why is breadth-first search only optimal when the cost solution is a non-decreasing function?

I am learning about searching strategies in AI and I was reading that breadth-first search is only optimal when the cost solution is a non-decreasing function? I am not really sure what this refers to ...
4
votes
1answer
3k views

How do I solve the knapsack problem using the hill climbing algorithm?

I need to solve the knapsack problem using hill climbing algorithm (I need to write a program). But I'm clueless about how to do it. My code should contain a method called ...
4
votes
1answer
260 views

How do we find the length (depth) of the game tic-tac-toe in adversarial search?

When we perform the tic-tac-toe game using adversarial search, I know how to make a tree. Is there a way to find the depth of the tree, and which level is the last level?
4
votes
1answer
120 views

What is the basic purpose of local search methods?

I read about the hill climbing algorithms, the simulating annealing algorithm, but I am confused. What is the basic purpose of local search methods?
4
votes
2answers
133 views

What is the proof that the branch and bound algorithm always finds optimal path in a graph?

I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others However, I haven't been able to find a ...
3
votes
2answers
309 views

Is a good evaluation function as good as any of the extensions of alpha-beta pruning?

I would like to know if having a really good evaluation function is as good as using any of the extensions of alpha-beta pruning, such as killer moves or quiescence search?
3
votes
1answer
255 views

Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?

I was reading Artificial Intelligence: A Modern Approach 3rd Edition, and I have reached to the UCS algorithm. I was reading the proof that UCS is complete. The book state that: Completeness is ...