Hello.
This is a video on the Hungarian algorithm.
We're going to just discuss briefly what it means to be a problem that you can solve and can solve and
then we'll talk.
But the Hungarian algorithm afterwards.
So there are two types of problems.
There's the something called in the problem or in the problem the problems are stuff that can be done
in polynomial time which means relatively quickly.
So for instance if I were to just have a list of numbers and I'm going to pick a random list over here
equals around between you know one and 100.
And can you find for me in that list the lowest number.
Well there's a couple of ways that you could do that.
So one way that you could do that is you can say Sure just go through the list and look look look the
lowest number happens to be 30 23 by walking through that list.
That's one possibility of setting up and find the lowest number.
However what about if you want to do that any quicker perhaps what you could do is you can sort this
list.
OK.
So I'm just going to bring this over here.
OK.
And what I'm going to do is I'm going to sort it now.
So I'm going to go over take selling and a sold smallest to largest and.
OK.
It's telling me that I can do it as an array so I'm just going to do it as an non-array and that's fine.
And now I'm going to sort it sort is too large or small is the largest continue with the current selection
and I don't know why it's not soaring at it because it's the previous one.
So let me copy and paste this so that it's just its own numbers.
And now I will sort of smallest to largest.
And you see that 23 is there so we change the problem into a problem that is just asking whether or
not we can sort quickly.
So that's one approach now.
Different problems take different amounts of time and we need to pick problem with that don't take forever.
One of those things that could be forever is something that if they try every possibility in this case
we tried any possibilities not every combination of every possibility.
So problems that can be done in less than two to the time are called polynomial greater than that is
in the non-polynomial time.
In other words greater than that there's a lot of technical details about it but let's just give an
example some of those problems these are carps 21 problems that everything can be broken into sat satisfiability
0 1 in the de-programming click etc. so all problems can be some type of subset of this group.
And even this group itself SAT is a it has a variation called klick has a variation called Zero an integer
Brugmansia of irritation called sat with at most three little claws.
Click has one of these so if you were to solve any of these For instance if you do some sequencing then
that means you solved knapsack.
That means you partition Max cat.
That means you solve everything and therefore if you solve one in less than Polon time in other words
you get an algorithm that does it.
Then you solved all of.
Now we don't know if there is such an algorithm that exists yes or no maybe we can't prove that there
is an organ that exists that would do it.
We can prove there is no algorithm that exists that could do it so we don't know.
We suspect these are long.
These are things that will take a long time.
As far as networks go for instance the directed Hamiltonian circuit is own network problem.
So let's look at some examples of what that is.
OK.
This is the Hamiltonian circuit.
What it means is that you can have some shape with edges and vertexes this is a verdict's vertex and
this is an edge and you have to start at an edge in the Hamiltonian circuit and started vertex and hits
every single vertex.
OK so this is hitting every single vertex.
If you follow this path it will hit every single vertex.
Now in a Hamiltonian circuit you care about the vertices.
You do not care about the edges it doesn't matter if you hit every edge more than once You just have
to hit every vertex more than once.
So here is again Hamiltonian circuit K and you can walk through this and you can see it every vertex
more than once every edge.
It's not it's not it's not even hitting every address.
But that's fine.
The Euler path is taking an example in walking through it to hit every edge.
In other words I can start at some position like C and then I can say OK do C to D back to C then go
to be than do B again then do a then do this then do this and do this or whatever you want.
There's lots of different variations but doing this is hitting every edge.
Now the Hamiltonian circuit isn't any problem it's takes too long to solve and we have to try every
possibility to figure it out.
The Euler path is not empty.
In other words we would be able to solve that so even little subtleties will change things.
But these are both obviously networks that we could talk about with nodes in the network.
One example of a problem you know just to give an example of a network problem is the Chinese postmen
problem.
OK let's make this drama bigger so we can see it.
The Chinese postmen problem is that there was a Chinese mathematician that came up with that.
How does let's say somebody starts a day.
How does he deliver all the mail in the shortest distance.
OK.
Now we want to he may have to you know hit an A second time because you have to go back or something
like that.
But how does he hit every edge in the shortest distance.
So that's looking at every edge doable.
Some graphs as you can see here like this first graph over here you can start at some edge you cannot
find a way that without picking up your pen so that you can trace every edge.
You can't do it it's impossible.
We can show which are which.
This one you can in fact do every edge.
Right.
You can do every edge you have to figure out how you have to start but you can do every edge but you're
not going to enter the same one if you started eight 8 and the deep you started and that today.
But you can hit every edge you just not going to start where you left but a postman probably wants to
start where he left this graph.
You can start somewhere and you can and at the same spot and let's say but you know that's more like
it.
But we have to figure out which graphs are which.
But the point being that this is a this is a network type problem.
The Traveling Salesman Problem has started at some point A and Treece the shortest route to wherever
you have to go in all your different stops like that.
Now the short the Traveling Salesman Problem is trying to minimize the distance here.
That's looking at the vertices that you have to stop that's similar to the Hamiltonian path and basically
hopefully realize that that is also going to be a problem that we can do in any reasonable amount of
time.
So subtleties will make a big difference.
OK.
So that's the background in what we need to know about time because what we're going to do is we're
going to look at the Hungarian algorithm which has this problem and ask can we solve this problem.
OK.
Now just to point out sometimes their problem is that we're happy that we have the tech check every
possibility.
For instance if you want to use it for cryptography then you don't want other people to be able to solve
the problem.
But maybe but you know have to you know you know a shortcut or you create the problem and therefore
it's good that they can sell the prominent reason amount of time.
But sometimes it's bad.
So for instance an airline that has to organize all its planes if it can find an optimal way to do it
it's not great to be sitting in the airport for eight hours or 30 hours or whatever it is.
This is the assignment problem.
And the Hungarian algorithm is used to do it.
We're going to assign the person from Austin who traveled to one of these cities.
We're going to assign the person from Boston to travel to one of those cities.
And this is the cost.
We're going to sign the person from Chicago to travel to one of those cities and that's the cost.
So the assignment problem is not the Traveling Salesman.
It's not an oilor path.
It's a slight different problem even though it sounds the same like we said the subtleties make all
the difference in terms of doing it and we're going to find the optimal way to figure out where we should
send all our sales people to to get to the cities that they need to and the cheapest way we're going
to assign them a city and it's going to be unique such that only one person goes to Denver one person
Deadman's and one person to of them.
So do that in the next video.