Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
29
votes
4answers
951 views

How to find the optimal number of neurons per layer?

When you're writing your algorithm, how do you know how many neurons you need per single layer? Are there any methods for finding the optimal number of them, or is it a rule of thumb?
14
votes
1answer
12k 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
6answers
648 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 ...
11
votes
3answers
559 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 ...
9
votes
2answers
8k 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
8answers
3k 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
156 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
3k 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
1answer
8k 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 ...
8
votes
2answers
137 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
15k 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
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
1k 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 ...
6
votes
1answer
7k views

What is the fringe in the context of search algorithms?

What is the fringe in the context of search algorithms?
6
votes
1answer
75 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
565 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
6k 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?
6
votes
3answers
530 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 ...
6
votes
2answers
1k 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
666 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
1answer
4k 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 ...
5
votes
2answers
281 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
400 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 is the difference between local search and global search algorithms?

What is the difference between local search and global (or complete) search algorithms?
5
votes
1answer
737 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
1k 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 ...
5
votes
1answer
144 views

How do we determine whether a heuristic 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 heuristics. Currently, I explored the Manhattan and Euclidean distances. ...
5
votes
1answer
157 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 ...
5
votes
1answer
99 views

A* is similar to Dijkstra with reduced cost

According to this Wikipedia article If the heuristic $h$ satisfies the additional condition $h(x) ≤ d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), ...
4
votes
1answer
3k 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
1answer
303 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
865 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
2answers
358 views

Is there any website that allows you to choose an algorithm, code it and visualise how it works?

I would like to do some practical implementation of a planning algorithm (of course, something a bit simple and easy). Is there any website where I can pick an algorithm (e.g. A* or hill climbing), ...
4
votes
1answer
62 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
394 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
74 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 make a tree. Is there a way to find the depth of the tree; which level is the last level?
4
votes
1answer
102 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
1answer
712 views

Exploration Strategies for Reinforcement Learning w/ Continuous Action Space

I'm building a deep neural network to serve as the policy estimator in an Actor-Critic reinforcement learning algorithm for a continuing (not episodic) case. I'm trying to determine how to explore ...
4
votes
2answers
45 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
220 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
95 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
2answers
5k views

What is an objective function?

Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function. My question is what is the objective function ?...
3
votes
1answer
308 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 ...
3
votes
1answer
121 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
206 views

How do I find whether this heuristic is or not admissible and consistent?

I was given the following problem to solve. Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge ...
3
votes
1answer
38 views

What are the common techniques one could use to deal with collisions in a Transposition Table?

Consider an iterative deepening search using a transposition table. Whenever the transposition table is full, what are common strategies applied to replace entries in the table? I'm aware of two ...
3
votes
2answers
563 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....
3
votes
1answer
2k 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 ...