Материал готовится,

пожалуйста, возвращайтесь позднее

пожалуйста, возвращайтесь позднее

Welcome back to algorithms. Today, we're

going to talk about the union find

problem. A set of algorithms for solving

the so-called dynamic connectivity

problem. We'll look at two classic

algorithms. Quick Find and Quick Union,

and some applications and improvements of

those algorithms. The subtext of today's

lecture really is to go through the steps

that we'll follow over and over again to

develop a useful algorithm. The first step

is to model the problem. Try to

understand, basically, what are the main

elements of the problem that need to be

solved. Then we'll find some algorithm to

solve the problem. In many cases, the

first algorithm we come up with would be

fast enough and maybe it fits in memory

and, we'll go ahead and use it, and be off

and running. But in many other cases maybe

it's not fast enough, or there's not

enough memory. So, what we do is try to

figure out why, find a way to address

whatever's causing that problem, find a

new algorithm and iterate until we're

satisfied. This is the scientific approach

to designing and analyzing algorithms,

where we build mathematical models to try

and understand what's going on, and then

we do experiments to validate those models

and help us improve things. So, first

we'll talk about the dynamic connectivity

problem, the model of the problem for

union find. So, here's the idea. They're

going to have a set of N objects. Doesn't

really matter what they are. We're going

to use the numbers, zero through N to

model our objects. And then, we have the

idea of a connection between two objects.

And, we'll, postulate that there's going

to be a command that says, connect two

objects. Given two objects, provide a

connection between them. And then key part

of the problem is find query or the

connected query, which just asks, is there

a path connecting the two objects. So for

example, in this set of ten objects, we

performed already, a bunch of union

commands, connecting four and three, three

and eight, six and five, nine and four,

two and one. And now we might have a

connected query that says, is zero connect

ed to seven? Well, in this case, there is

no connection, so we say no. But if we ask

is eight connected to nine? We are going

to say yes, even no we don't have a direct

connection between eight and nine. There

is a path from eight to three to four to

nine. So, that's our problem, to be able

to officially support these two commands

for given set of objects. Now, let's say

we add a union five, zero. So, that

creates a connection between five and

zero. Seven and two creates a connection

between seven and two. And six and one,

between six and one. So, now if we ask our

zero connected to seven, well one and zero

we can do that too. And that's a redundant

connection. And now, if we ask is zero

connected to seven we're going to answer

yes. So that's our problem, intermix

union, commands and connected queries and

we need to be able to officially support

those commands for a large number of

objects. So, here's a much bigger example.

And you can see that we're going to need

efficient algorithms for this. First of

all, you can see we're going to need a

computer for this. It would take quite,

quite some time for a human to figure out

whether there's a connection. In this case

there is a connection. Now, the algorithms

that we're looking at today are not going

to actually give the path connecting the

going to talk about the union find

problem. A set of algorithms for solving

the so-called dynamic connectivity

problem. We'll look at two classic

algorithms. Quick Find and Quick Union,

and some applications and improvements of

those algorithms. The subtext of today's

lecture really is to go through the steps

that we'll follow over and over again to

develop a useful algorithm. The first step

is to model the problem. Try to

understand, basically, what are the main

elements of the problem that need to be

solved. Then we'll find some algorithm to

solve the problem. In many cases, the

first algorithm we come up with would be

fast enough and maybe it fits in memory

and, we'll go ahead and use it, and be off

and running. But in many other cases maybe

it's not fast enough, or there's not

enough memory. So, what we do is try to

figure out why, find a way to address

whatever's causing that problem, find a

new algorithm and iterate until we're

satisfied. This is the scientific approach

to designing and analyzing algorithms,

where we build mathematical models to try

and understand what's going on, and then

we do experiments to validate those models

and help us improve things. So, first

we'll talk about the dynamic connectivity

problem, the model of the problem for

union find. So, here's the idea. They're

going to have a set of N objects. Doesn't

really matter what they are. We're going

to use the numbers, zero through N to

model our objects. And then, we have the

idea of a connection between two objects.

And, we'll, postulate that there's going

to be a command that says, connect two

objects. Given two objects, provide a

connection between them. And then key part

of the problem is find query or the

connected query, which just asks, is there

a path connecting the two objects. So for

example, in this set of ten objects, we

performed already, a bunch of union

commands, connecting four and three, three

and eight, six and five, nine and four,

two and one. And now we might have a

connected query that says, is zero connect

ed to seven? Well, in this case, there is

no connection, so we say no. But if we ask

is eight connected to nine? We are going

to say yes, even no we don't have a direct

connection between eight and nine. There

is a path from eight to three to four to

nine. So, that's our problem, to be able

to officially support these two commands

for given set of objects. Now, let's say

we add a union five, zero. So, that

creates a connection between five and

zero. Seven and two creates a connection

between seven and two. And six and one,

between six and one. So, now if we ask our

zero connected to seven, well one and zero

we can do that too. And that's a redundant

connection. And now, if we ask is zero

connected to seven we're going to answer

yes. So that's our problem, intermix

union, commands and connected queries and

we need to be able to officially support

those commands for a large number of

objects. So, here's a much bigger example.

And you can see that we're going to need

efficient algorithms for this. First of

all, you can see we're going to need a

computer for this. It would take quite,

quite some time for a human to figure out

whether there's a connection. In this case

there is a connection. Now, the algorithms

that we're looking at today are not going

to actually give the path connecting the

Загрузка...

Выбрать следующее задание

Ты добавил

Выбрать следующее задание

Ты добавил