Hot answers tagged

18 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 ...
user avatar
  • 436
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 ...
user avatar
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 ...
user avatar
  • 33.8k
9 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 ...
user avatar
  • 33.8k
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 585
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 ...
user avatar
  • 2,559
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 ...
user avatar
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-...
user avatar
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. ...
user avatar
  • 1,953
6 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) =...
user avatar
  • 33.8k
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 ...
user avatar
  • 361
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.
user avatar
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 ...
user avatar
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 ...
user avatar
  • 33.8k
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 ...
user avatar
  • 361
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 ...
user avatar
  • 585
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 ...
user avatar
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,...
user avatar
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 (...
user avatar
  • 9,379
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
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 ...
user avatar
  • 1,016
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, ...
user avatar
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 ...
user avatar
  • 311
3 votes

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

You may start assigning penalties for undesirable conditions in a state like: 1) Number of blocks outside stack 0. Supose you penalize with 10 units each block outside stack 0, then the starting ...
user avatar
  • 176

Only top scored, non community-wiki answers of a minimum length are eligible