19
votes
What is the difference between tree search and graph search?
There is always a lot of confusion about this concept, because the naming is misleading, given that both tree and graph searches produce a tree (from which you can derive a path) while exploring the ...
15
votes
Accepted
Why is depth-first search an artificial intelligence algorithm?
This is a fundamentally a philosophical question. What makes AI AI? But first things, why would DFS be considered an AI algorithm?
In its most basic form, DFS is a very general algorithm that is ...
- 436
14
votes
Accepted
What are the differences between A* and greedy best-first search?
Both algorithms fall into the category of "best-first search" algorithms, which are algorithms that can use both the knowledge acquired so far while exploring the search space, denoted by $g(n)$, and ...
- 39.1k
13
votes
Accepted
Why is A* optimal if the heuristic function is admissible?
This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details.
First, let's review the definitions:
Your ...
- 9,147
11
votes
Accepted
How is iterative deepening A* better than A*?
A* is a best-first search algorithm, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an admissible heuristic ...
- 39.1k
8
votes
Why teaching only search algorithms in a short introductory AI course?
There is lots of misconceptions about AI, specifically the idea that it is about making computers "think" like humans, simulating brain, the sci-fi robots taking over the world, all the philosophical ...
- 531
8
votes
Are methods of exhaustive search considered to be AI?
If one thinks of intelligence as a continuous measure of optimization power (that is, how much better are outcomes for any unit of cognitive effort expended), then exhaustive search has non-zero ...
- 4,262
8
votes
Accepted
What is the difference between search and learning?
In the context of AI:
Search refers to Simon & Newell's General Problem Solver, and it's many (many) descendant algorithms. These algorithms take the form:
a. Represent a current state of some ...
- 9,147
7
votes
Accepted
What are the state space and the state transition function in AI?
Initial state
How things are at first.
In your particular example, it would be where your k knights are placed on the board initially. Your problem doesn't ...
- 575
7
votes
Are methods of exhaustive search considered to be AI?
If a computer is just brute-forcing the solution, it's not learning anything or using any kind of intelligence at all, and therefore it shouldn't be called "artificial intelligence." It has to make ...
- 2,589
7
votes
Accepted
Why is search important in AI?
State space search is a general and ubiquitous AI activity that includes numerical optimization (e.g. via gradient descent in a real-valued search space) as a special case.
State space search is an ...
- 7,206
7
votes
Accepted
How do I show that uniform-cost search is a special case of A*?
Yes, UCS is a special case of A*.
UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) =...
- 39.1k
6
votes
Why teaching only search algorithms in a short introductory AI course?
What it comes down to is that most AI problems can be characterized as search problems. Let's just go through some examples:
Object recognition & scene building (e.g. the process of taking
audio-...
- 712
6
votes
Accepted
What are the limitations of the hill climbing algorithm and how to overcome them?
As @nbro has already said that Hill Climbing is a family of local search algorithms. So, when you said Hill Climbing in the question I have assumed you are talking about the standard hill climbing. ...
- 2,023
6
votes
Accepted
Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?
Let's consider a problem where all edge costs are greater than zero, but not above some $\epsilon$:
Image a problem where we have an infinite path where the first edge is cost $\frac{1}{2}$, the next ...
- 371
5
votes
How does A* search work given there are multiple goal states?
Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.
- 7,206
5
votes
Why teaching only search algorithms in a short introductory AI course?
Why would one professor only teach searching algorithms in AI course? What are the advantages/disadvantages?
My answer to this question is that there are lots of problems where the solution can be ...
- 343
5
votes
Accepted
Why does Monte Carlo work when a real opponent's behavior may not be random
First, we need to distinguish plain Monte-Carlo from Monte-Carlo Tree Search. They're different things.
Monte-Carlo search, in the context of game AI search algorithms, is typically understood to ...
- 9,934
5
votes
What are the limitations of the hill climbing algorithm and how to overcome them?
Hill climbing is not an algorithm, but a family of "local search" algorithms. Specific algorithms which fall into the category of "hill climbing" algorithms are 2-opt, 3-opt, 2.5-opt, 4-opt, or, in ...
- 39.1k
5
votes
Is the summation of consistent heuristic functions also consistent?
No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1.
s --1-- g
Assume that $h_0$ and $h_1$ are ...
- 371
4
votes
Accepted
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
You are correct, they should also be the immediate ones:
If 11 is the goal state and I start going backwards, is ...
- 575
4
votes
Accepted
What is the difference between local search and global search algorithms?
The difference between a local search algorithm (like beam search) and a complete search algorithm (like A*) is, for the most part, small.
Local search algorithms will not always find the correct or ...
- 1,235
4
votes
Is a good evaluation function as good as any of the extensions of alpha-beta pruning?
To build on Neil's answer a bit, you're right that the better your evaluation function gets, the less work your optimization function will need to perform. If your evaluation function gets good enough,...
- 9,147
4
votes
Accepted
Transposition table is only used for roughly 17% of the nodes - is this expected?
I don't think that's necessarily a strange number. It's impossible for anyone to really tell you whether that 17% is "correct" or not without reproducing it, which would require much more info (...
- 9,934
4
votes
What are the differences between uniform-cost search and greedy best-first search?
In the case of UCS, the evaluation function (that is, the function that is used to select the next node to expand) is $f(n) = g(n)$, where $g(n)$ is the cost of the path from the initial node to $n$, ...
4
votes
When should I use simulated annealing as opposed to a genetic algorithm?
Simulated Annealing vs genetic algorithm?
Simulated annealing is a materials science analogy and involves the introduction of noise to avoid search failure due to local minima. See images below. To ...
- 7,433
4
votes
Accepted
Can two admissable heuristics not dominate each other?
This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another ...
- 1,096
4
votes
How to create an AI to solve a word search?
This sounds like a problem that might be solvable with a LSTM-DQN approach, as described in Language Understanding for Text-based Games using Deep
Reinforcement Learning by Narasimhan et al., 2015, ...
- 9,147
3
votes
Why is the larger value, as opposed to the smaller one, chosen, in the hill climbing algorithm?
When we climb a hill:
We move higher in altitude. The person who is climbing, will always look for rocks/mud on the hill that are higher, so that he can climb higher.
That is what the algorithm does ...
- 481
Only top scored, non community-wiki answers of a minimum length are eligible