Okay, so maybe you watched the first the introduction to this
larger Playlist the "Intelligence and Learning" set of videos
But now this video is an introduction to just the first session and the first session is about
Search and graph systems now. Why why why should that be the first session?
I don't know might be a bad idea first of all I wanted a warm-up.
So I wanted something to kind of get us thinking about algorithms
Data and
things that the intelligence, or that solve problems in an intelligent way, so
And also there are some very you know some ways common unsolved problems of computer science like the traveling Salesperson problem
which is one of the topics of this week's that could could use of
new newly invented
Machine learning system to solve it. You know I don't have my prop
if I had my book
Artificial Intelligence: A Modern Approach [Stuart Russell and Peter Norvig]
Books yes, and I hope I got that right um you would see a lot of. I don't got my pen anymore.
continuity error
You would notice
that
There's a lot of algorithms in these books about search because one of the first one of the kinds of problems that
artificial intelligence algorithms that intelligent algorithms
often need to solve in computer science in
applications
Interactivity all the sort of kind of projects you might be thinking of making is
there's a problem. I need to figure out the answer to this problem, but there are so many possible answers
I couldn't possibly check every single one and so search refers to the idea of
searching for the answer in A
sea of possibilities now one way is to search every single possibility I mentioned the traveling salesperson problem. Let's talk about that for a second.
So, I] want to talk about
search and graph system. This is kind of loosely the topic for right now
There goes that eraser. Oh my God! Sorry everybody the erasers okay! Everything's fine! OK so the traveling salesperson
says oh, I have videos on this already, so you can go watch those there are some number of cities and
let's say there are five and
that a
sales person
needs to visit all of the cities in the shortest amount of time or picking it with the shortest distance in any order
Starting with anyone ending with anyone, so I might be able to eyeball this and say like okay?
Well, maybe that's the path that's probably not the path. It's probably more like that
whatever the point is we could have a computer algorithms figure this out let's just check every single possibility, so
first let's pick a city how many cities should I pick how many cities click? Oh? There's five okay?
Now if I pick if there's five possibilities now once I picked one city. How many possibilities are there left? Four?
I'm how many are left three now
We're left to and we left one so five factorial 20 60 120 120 possibilities for five cities
And this is 5 factorial, so this is a kind of problem. That doesn't seem like such a big deal
but if I just have 10 cities
What's 10 factorial no the computer could probably crunch through that number? What about 50 cities?
Okay, that's just three with 64 zeros after it
It's like a really really really big number. I mean, what's the listing the
age of the known universe
If you 13.6 times 2 billion years that other numbers a lot more than that
So and you know even if we could do like a million per second or something. It's trust me
We're going to have some issues. I'll talk about it. So what are some solutions to this next week
We're going to look at genetic algorithms. Which is a technique for
trying to optimally find a solution, and there are ways we might say something known as a greedy algorithm. I
went off on a tangent there! We'll see if it is a problem and edit this part out
but a greedy algorithm which might say like
I don't know
Let's just pick a city and then pick the closest one they took the closest one to that
Trying to get us a pretty good answer
Even if it's not the exact optimal answer... the point of what I'm saying is this is the application that I want to look at
In this first week so the things that we need to learn about to be able to do things and work with
problems like the Traveling Salesperson are:
number one
graph systems and
number two
search algorithms
Okay, now. What is a graph system? A graph system
is something ...
a system that is made up of two elements
node and an edge
We can name these other things, but I'm going to call them the nodes and edges.
One of the next videos that you'll watch if you follow this playlist will be on something called a binary search tree a binary tree
Is a graph system where every node is connected to two
children nodes a left and a right and those are connected to two and those are connected to two
ETc, Etc, Etc, so this is one example of a graph system. So what you'll notice is
We need some sort of Data structure to store
what are all the nodes and what are all the edges and this depends on the problem a
Common example also the graph system similar to the traveling Salesperson problem in a subway map
So let's say you to get from this station to this station.
Well there are all these other stations and roots and maybe they all are interconnected
And there's many ways to get on this bus subway map makes no sense there's many ways to get there
But they all take different amounts of time like maybe I could go from here to here to here to here to here
Which is, hold on, let me redraw. Let me redraw this let me just draw it like this
So let's say I want to get from here to here
We could see like oh, I'm going to get from in one step to here and it's going to a two-step
I want to take two trains to get to hear what if this train takes
60 minutes this train takes 30 minutes and each one of these is 65 to 60 to the 61 in this pic 6
So even though I have to go on 1 2 3 4 or trains. This is optimal this will get me there faster
This is known as a weighted graph system.
So the graph system is a bunch of nodes those nodes might have value so a binary search tree
You can use to organize
An alphabetical order a lot of words or numbers and other variety of things and you could think of this...
But the edges here don't necessarily have weights at least in a standard binary tree, but here they do. Now. There's an algorithm for
Searching for that optmal path in this scenario in a weighted graph and it's called
Dijkstra's Algorithm
there's also another algorithm called A* and
ETc ETc. So these are different examples binary search algorithm
Dijkstra's Algorithm, A*, and the one that I'm actually doing today
But that doesn't really matter to you because you're to watch these videos in sequence. I'll talk about a second
It's something called Breadth first search
So breadth-first search is a good algorithm for finding the shortest path between two nodes in a graph that
Aren't weighted so the shortest number of steps and I'll talk about the example that I'm gonna use for that in a bit
so this week is all about learning how to program a graph system and
learning about different algorithms to efficiently solve a
some type of problem associated with the graph system like the shortest path and you'll and so now
Once you stop watching this video
There's going to be a bunch of others in this playlist that I've made at all different times under different circumstances
So this is experiment that I'm trying to put together a sequence course with all different coding challenges
So you'll see there's a binary search tree example there will be a breadth-first search example
There's there is no at the time of this recording
but there might be at the time as you're watching a Dijkstra's algorithm
A*. So, you'll see, and I'm going to be filling stuff in as time goes on
Once you get to the end of all of those if you choose to watch them all I'll make another video that kind of wraps
up and shows you a bunch of examples all together and
gives you some ideas for some homework exercises that you might do that
you could share with me in the comments
And that sort of thing
If you want to participate in a slack channel that I have that's going on for this course you can sign [up]
Patreon.com coding train is a crowdfunding thing if you want to participate in this Slack channel
but you can also always hit me up on Twitter at shiffman
In the comments here which I do read. Okay.
So that's what's going to happen next and I will see you if you decide [to] [come] back in a wrap-up video where I
Kind of summarize bunch of this tough and give you some exercise ideas great, so I'm going to go and actually record a video
Right now on breadth-first search, but you might watch some of these other ones first. Thanks very much.
OOPS! I've always it back at the end of my videos when you think they're over so one thing
I want to mention that if you're about to watch
Some of these the rest of the videos in [this] sequence first of all you should you know if you don't know...
Javascript programming in Pjs. You might want to take a look at some of my intro people have shows videos
but more importantly than that if you have experience with
Two things that [I'm] using in these videos is one is this a concept of prototype as a way of attaching
Methods to an object in Javascript as well as this idea of an associative array, or hash table, and how that works in Javascript.
So those two things or might be videos that you might wanna go and watch first before you start looking at some of the graph
systems and different search algorithms, okay, just in case that matters to you, you know
But you don't really have to know very much to follow this up along if you know a bit about
Programming you've tried you watched them my other videos. Hopefully you'll be okay. If not let me know and I'll see what I can do okay.
See you soon!