Hot answers tagged

14

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 applied to wildly different categories of problems: topological sorting, finding all the connected components in a graph, etc. It may be also used for searching. For ...


13

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 search space, which is usually represented as a graph. Differences Firstly, we have to understand that the underlying problem (or search space) is almost ...


10

In English, the fringe is (also) defined as the outer, marginal, or extreme part of an area, group, or sphere of activity. In the context of AI search algorithms, the state (or search) space is usually represented as a graph, where nodes are states and the edges are the connections (or actions) between the corresponding states. If you're performing a tree (...


10

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 definitions of admissible and consistent are correct. An admissible heuristic is basically just "optimistic". It never overestimates a distance. A consistent ...


10

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 function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$. There are other best-first search algorithms, which differ only in ...


8

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 discussions around brain as machine etc. The practice/reality of AI is about "using computing to solve problems" which basically means you take any problem, ...


8

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 intelligence (in that it does actually give better outcomes as more effort is expended) but very, very low intelligence (as the outcomes are better mostly by luck, ...


8

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 part of the world as a vertex in a graph. b. Represent, connected to the current state by edges, all states of the world that could be reached from the current ...


7

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 precisely state this, so you could either place them at the bottom or at random. Goal state The board with the k knights placed on the target squares. State transition function A function that takes ...


7

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 decisions based on what's happened before in similar instances. For something to be intelligent, it needs a way to keep track of what it's learned. A chess ...


7

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 abstraction which can be customized for a particular problem via three ingredients: Some representation for candidate solutions to the problem (e.g. permutation ...


7

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 a heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$ in the search space (often represented as a graph). ...


6

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-visual input of your surroundings and understanding it in a 3D and contextual sense) can be treated as searching for known objects in the input. Mathematical ...


6

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. The standard version of hill climb has some limitations and often gets stuck in the following scenario: Local Maxima: Hill-climbing algorithm reaching on the ...


6

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) = g(n) + h(n)$, where $g(n)$ means the same thing as in UCS and $h(n)$, called the "heuristic" function, is an estimate of the distance from $n$ to the goal ...


5

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.


5

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 general, any N-opt. See chapter 3 of the paper "The Traveling Salesman Problem: A Case Study in Local Optimization" (by David S. Johnson and Lyle A. McGeoch) for ...


5

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 perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an ...


4

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 optimal solution, if one exists. For example, with beam search (excluding an infinite beam width), it sacrifices completeness for greater efficiency by ordering ...


4

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 found using searching. Take an example of Tic Tac Toe. If you are designing an intelligent computer player for this, then what you will do is that you will form a ...


4

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 10 considered as successor of 5? Even if it do not leads me further to my start state 1? No, there is also a bit of misunderstanding of bidirectional search: ...


4

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, you won't need to search at all. This is not just an academic idea though! It's actually fairly widely used, and has been key to solving several games. The ...


4

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 (basically would have to know every single tiny detail of your implementation to be able to reproduce). Some things to consider: The size of your transposition table ...


4

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 improve the odds of finding the global minimum rather than a sub-optimal local one, a stochastic element is introduced by simulating Brownian (thermal) motion. ...


4

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 and vice-versa. Think of it as a game of rock paper scissors. Specifically, you may find that sometimes $h_1 < h_2$ and in other times $h_2 < h_1$, where $...


4

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, and then extended to a domain very similar to your problem in Deep Reinforcement Learning for Syntactic Error Repair in Student Programs by Gupta et al., 2019. ...


4

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 is $\frac{1}{4}$, the following is $\frac{1}{8}$, and so on forever. Every edge is greater than zero, meeting the condition being proposed in the question. ...


3

In general, Google autocompletes (and produces search results) based on wide variety of factors, including (but not limited to) your location, your search history, your other Google accounts, your site visit history, your language settings, etc. For the specific question, I see a few ways in which Google might have access to the relevant information: If ...


3

Let's begin with some definitions first. Hill-climbing is a search algorithm simply runs a loop and continuously moves in the direction of increasing value-that is, uphill. The loop terminates when it reaches a peak and no neighbour has a higher value. Stochastic hill climbing, a variant of hill-climbing, chooses a random from among the uphill moves. The ...


3

The steepest hill climbing algorithms works well for convex optimization. However, real world problems are typically of the non-convex optimization type: there are multiple peaks. In such cases, when this algorithm starts at a random solution, the likelihood of it reaching one of the local peaks, instead of the global peak, is high. Improvements like ...


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