9
$\begingroup$

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 search algorithm. The algorithm is easy to understand, but no one explains why this algorithm is included in the artificial intelligence study.

Where do we use it? What makes it an artificial intelligence algorithm? Is every search algorithm is an AI algorithm?

$\endgroup$
14
$\begingroup$

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 instance, you could use DFS for finding a path in a 2D maze (although not necessarily the shortest one). Or you could use it to navigate through more abstract state spaces (e.g. between configuration of chess or in the towers of Hanoi). And this is where the connection to AI arises. DFS can be used on its own for navigating such spaces, or as a basic subroutine for more complex algorithms. I believe that in the book Artificial Intelligence: A Modern Approach (which you may be reading at the moment) they introduce DFS and Breadth-First Search this way, as a first milestone before reaching more complex algorithms like A*.

Now, you may be wondering why such search algorithms should be considered AI. Here, I'm speculating, but maybe the source of the confusion comes from the fact that DFS does not learn anything. This is a common misconception among new AI practitioners. Not every AI technique has to revolve around learning. In other words, AI != Machine Learning. ML is one of the many subfields within AI. In fact, early AI (around the 50s-60s) was more about logic reasoning than it was about learning.

AI is about making an artificial system behave "intelligently" in a given setting, whatever it takes to reach that intelligent behavior. If what it takes is applying well-known algorithms from computer science like DFS, then so be it. Now, what is it that intelligent means? This is where we enter more philosophical grounds. My interpretation is that "intelligence" is a broad term to define the large set of techniques that we use to approach the immense complexity that reality and certain puzzle-like problems have to offer. Often, "intelligent behavior" revolves around heuristics and proxy methods away from the perfect, provable algorithms that work elsewhere in computer science. While certain algorithms (like DFS or A*) may be proven to give optimal answers if infinitely many resources can be devoted to the task at hand, only in sufficiently constrained settings would such techniques be affordable. Fortunately, we can make them work in many situations (like A* for chess or for robot navigation, or Monte Carlo Tree Search for Go), but only if reasonable assumptions and constraints over the state space are imposed. For all the rest is where learning techniques (like Markov Random Fields for image segmentation, or Neural Nets paired with Reinforcement Learning for situated agents) may come handy.

Funny enough, even if intelligence is often regarded as a good thing, my interpretation can be summed up as imperfect modes of behavior to address immensely complex problems for which no known perfect solution exists (with rare exceptions in sufficiently bounded problems). If we had a huge table that, for each chess position, gives the best possible move you can make, and put that table inside a program, would this program be intelligent? Maybe you'd think so, but in any case it seems more arguable than a program that makes real-time reasoning and spits a decision after some reasonable time, even if it's not the best one. Similarly, do you consider sorting algorithms intelligent? Again, the answer is arguable, but the fact is that algorithms exist with optimal time and memory complexities, we know that we can't do better than what those algorithms do, and we do not have to resort to any heuristic or any learning to do better (disclaimer: I haven't actually checked if there's some madman out in the wild applying learning to solve sorting with better average times).

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Good answer. I speak and teach in the ML and AI fields. I find that, generally, people who are not working in this field or who are new to the field have a misconception as to what ML and AI actually are and how they work. They imagine what they read in scifi books and see in movies. It is, however, effectively the application of algorithms to mathematical models to perform transformations in high dimensional vector space. In another sense, it is just applied computational statistics and probability theory. Since DFS fits in terms of an AI search approach. $\endgroup$ – David Hoelzer Aug 12 at 13:35
  • $\begingroup$ Thanks Asher for such a good explanation $\endgroup$ – himari Aug 12 at 13:45
  • 3
    $\begingroup$ @DavidHoelzer Exactly. Another pervasive trend that I've found with the rise of Deep Learning is the even narrower belief that if something does not have a neural net inside, then it cannot possibly be AI. $\endgroup$ – Asher Aug 12 at 15:23
  • $\begingroup$ "It's just a linear model, that's not AI" is something I keep running into. Basic machine learning is taught in high school, but nobody seems to realise because it's written on a whiteboard instead of displayed in neon blue on a touchscreen. $\endgroup$ – Joe Bloggs Aug 13 at 8:50
  • $\begingroup$ Regarding sorting with ML: Isn't it the rule 34 of computer science? For every problem, there is a ML solution. $\endgroup$ – jpa Aug 13 at 9:03
1
$\begingroup$

DFS on its own would not typically be considered AI imo. It is a standard computer science deterministic algorithm. Instead an intelligent agent might use DFS to inform its decision making as part of an AI package.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Any reason why you highlight that DFS is deterministic? Would you say that there is a stronger connection between AI and random algorithms than between elsewhere in computer science and random algorithms? Also, I would say that determinism isn't a strong feature of DFS. After all, you could visit the successor nodes in a random order, and the algorithm would be essentially the same. Other than that, I agree that DFS doesn't belong to AI anymore that it belongs to CS. However, it is worth it to study it in introductory AI courses as a basic building block. $\endgroup$ – Asher Aug 13 at 6:56
  • $\begingroup$ AI and ML have strong components of probability. There may not be absolutely correct "answers" for the objective functions they seek to solve. Instead statistical concepts such as maximum likelihood estimation and bayesian analysis come into play. DFS does not involve randomization. $\endgroup$ – javadba Aug 13 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.