Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
17
votes
1answer
23k 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 ...
13
votes
1answer
15k 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 ...
12
votes
3answers
710 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 ...
11
votes
5answers
907 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
12k views

What is the fringe in the context of search algorithms?

What is the fringe in the context of search algorithms?
9
votes
2answers
14k 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
263 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
190 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 ...
8
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
3answers
34k 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
677 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
1answer
169 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 studying Artificial Intelligence. A Modern Approach, Stuart Russell, Peter Norvig, specifically about search and planning arguments. I don't understand the difference between the two terms. I was ...
6
votes
1answer
8k 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
171 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
600 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
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
218 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
814 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
950 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
1answer
778 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
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
623 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 ...
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
735 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 ...
5
votes
2answers
1k 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....
5
votes
1answer
250 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 ...
5
votes
1answer
209 views

Illustration of Von Neumann's Minimax theorem in games?

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
6k 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
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?
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
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
443 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
2k 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
194 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
117 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
112 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
293 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
413 views

Is the summation of consistent heuristic functions also consistent?

Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not? Is there any proof ...
3
votes
1answer
2k views

Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?

I understand that the actual algorithm calls for using Depth-First Search, but is there a functionality reason for using it over another search algorithm like Breadth-First Search?
3
votes
1answer
428 views

A* and uniform-cost search are apparently incomplete

Consider the following diagram of a graph representing a search space. If we start at $B$ and try to reach goal state $E$, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm ...
3
votes
1answer
312 views

How does a google choose it's autocomplete solution

While writing a paper yesterday this strange thing happened to me. I was wrtiting it in Word, and wasn't satisfied with the repeated usage of word "relesase" in last few senteces. So I've decided to ...