Finding Bridge Edges - Intro to Algorithms Udacity English Japanese

Finding Bridge Edges - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 7.8K views 21 likes 20 dislikes 23 Feb 2015

Udacity 651K subscribers United States YouTube↗

Click to Play Video

Alright, so I’ve redrawn the graph from the previous examples just to make a little bit more room and

先ほどのグラフを描き直して少しスペースを作りました

what we’ve got so far is the original graph and the –

このオリジナルのツリー型のグラフは

a tree version of the graph that we built by search, some kind of data depth-first, breadth-first – any kind

深さ優先探索や幅優先探索などのデータで作られています

of search actually will do, as long as we now have these green edges pointing downward and these red

グラフは緑のエッジが下に向かって伸びており

no-tree edges connecting nodes that need to be connected if the edge wasn’t actually part of this

赤い非ツリーエッジがグラフに含まれないエッジとしてノードをつないでいます

tree. Then we post ordered the nodes and now what

そしてノードは後行順に番号が振られています

do we do next.We now compute the number of descendents for each node in the graph and the

では次に各ノードの子孫の数を計算していきましょう

number of descendents is the number of nodes that

子孫の数とはノードの数で

are either the node or reachable from the node by

緑のエッジをたどって到達できる

following green edges only. So this is easiest to start

ノードのみを指していますでは一番簡単な方法で

at the bottom here, F has just the node itself and no

下のfから見ていきます

descendants, so it’s got a number of descendant of

fに子孫はいないのでノード数は1です

one, same thing with G.E has one descendant, one

gもfと同様でeは子孫ノードが2と

descendent plus itself for three. D has the three

eでノードの合計は3です

descendants of E plus itself for four. C has the four

dは子孫ノードが3とdで4 cの子孫は

descendants of D plus itself is five. B has just itself

4でcを含めて5 bは1です

and A has B’s descendants, C’s descendants plus

aはbとcの子孫にaを足して7になります

itself for seven. So the next thing we’re going to compute is for each of the nodes, we’re going to

次に計算していくのはノードのペア数です

consider the set of nodes that are descendants of

子孫ノードもしくは子孫から

the node or reachable from the descendants of the

非ツリーエッジで1ホップで到達できるノードか

node by one hop of a non-tree edge and of all those

子孫から到達可能なノードです

nodes that are reachable, we’re going to look at the

そこから後行順の最小値を

post-order value that is the smallest, we’ll call that L.

見ていきますこの最小値をLと呼びます

So in the case of F, F has itself and it also can reach

まずはfです fはf自身とgに到達できるので

G, the smallest value there is two. G has no

fの最小値は2です

descendants but it can reach by one red edge F. So

gに子孫はいませんが赤のエッジでfに行けるので

the smallest least values two and three is two. E has

最小値は2と3で2です

F and G and itself that it can reach no other nodes by non-tree edges and the smallest of those

eは自分とfとgに到達できるので最小値は2です

numbers is two. D can reach all of these nodes in

dは下のすべてのノードに到達できて

itself but also by a non-tree edge it can reach this

非ツリーエッジでbにも行けます

node and the smallest of those numbers is one. C

そのためこれらのの最小値は1です

can reach all of these nodes and through one of

cは下のすべてのノードと

those nodes one tree edge gets it to one. B values

dの赤のエッジがあるので1です

itself as one so that’s going to be the smallest. And

bは自分だけなので最小の1になります

A includes everything, so that’s going to include the

aは全部を含むので最小の1です

one, so that’ll be the smallest. H is the same idea

次のHも同じ考え方です

except of those that same set that we computed for L, we want to know the largest value. For G between

ただし今回はLと違って最大値を求めます

F and G the largest value is three. For E between E,

gはfとgの間なので最大値は3です

F and G the largest value is four. For D, D,E,F, G

eはfとgなので最大値は4 dはd、e、f、gと

and B reachable by a red edge, the largest value is

赤のエッジでつながったbで最大値は5です

itself five. C same set for adding in C now and the

cはdのペアと自分なので最大値は6になります

largest value becomes six and A set contains everybody so that’s going to include itself with the

aは全部に自分も加わるので最大値は7です

value of seven. Alright, now we’ve decorated these nodes with lots of interesting numbers, now we can

ノードの横にはカラフルな数字が並んでいますが

get to the last step. So given all these nicely decorated nodes, we now have a rule for figuring out

与えられたこのノードとあるルールを使って

which ones are the bridge edges and this is the rule.

ブリッジとなるエッジを探します

All the bridge edges are ones that are green, they

ブリッジのルールは緑のエッジであること

have to be three edges and the green number is less or equal black number and the red number is

緑の数字が黒の数字より小さいか同じであること

bigger than the blue number minus the black

赤の数字が青の数と黒の数の差より大きいことです

number or in words the – each value has to be less

簡単に言うとそれぞれの値が

or equal to the post order value, the lowest value

後行順の値よりも小さいか同じであることと

has to be bigger than the number of descendants

最小値が子孫ノード数と後行順の値の差よりも

minus the post order value. So apart from the fact

大きいことですこのルールが

that it’s not immediately obvious why this is the right

なぜ正しいのかはさておき

rule let’s apply it to the tree to see what gets picked

ルールを応用してブリッジを見つけましょう

out. So, what we’re doing here is we’re looking at each green edge and we’re checking the numbers

では下から順番に各エッジを見ながら

on the downward part of the edge. So here is a

それぞれの数を調べていきます

green edge and let’s look at the numbers here and

この緑のエッジの数字を見てみましょう

see if they fit the pattern. We need the green number to be less or equal to the black number. So

ルールでは緑の数字は黒の数字より小さいか同じなので

that doesn’t work, right. Here is another green edge.

これは違います次です

You need the green number to be less or equal to the black number, oh that works. So the red number

この緑の数字は黒の数字より小さいですね

needs to be bigger than the difference between the black and the blue. So black and the blue the

赤の数字は黒と青の差より大きい必要があります

difference is two. The red number is two, so that

黒と青の差が2で赤の数字は2なので

doesn’t work. Alright next edge to check is this one,

これも違います次に移ります

so we need to check is green less or equal to black,

まず緑の数字はクリア

yes. Is red bigger than black minus blue? Two is

赤の数字はどうでしょうか黒と青の差は1なので

bigger than one, so yes. So this edge has been

赤の数字もクリアですこのエッジが

identified as a tree edge. That’s the right answer and

ブリッジということが分かりました

none of the other edges are tree edges but let’s just check them just to be sure. For this edge, we have –

他のエッジはブリッジではありませんが一応確認していきましょう

we need green to be less or equal to black which we

この緑の数字はクリア

have. And we need red to be bigger than the difference between blue and black but one is not

赤の数字は青の数字と黒の数字の差より大きい必要がありますが

bigger than one, so this edge is out. How about this?

1と1なので違います次はどうでしょうか

We need green less or equal to black, yes. We need

緑の数字は黒の数字と同じなのでクリア

red bigger than the difference, no. Green number is

赤の数字は該当しませんここの緑の数字は

five because the D node is reachable by a non-tree

赤のエッジでdとつながるので5です

edge. Alright, so green less or equal to black, no.

ここも条件に該当しません

Alright, well that’s it. Those are all the edges. So in

これで全部ですね

this example anyway the one edge that the

今回アルゴリズムで見つけたエッジが

algorithm finds is exactly the bridge edge. Can we

まさにブリッジでした

get a handle on why this works? It seems kind of

なぜこのルールで分かるのでしょう?

magic at this point.

今の時点では魔法のようです

Similar videos:

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

10 Everyday Things You've Been Doing Wrong
Facts Verse
345.2K views 3.4K likes 534 dislikes 18 May 201761% match

It's a Finding Dory Toy Haul
Tic Tac Toy
379.9K views 472 likes 88 dislikes 05 May 201661% match

Python Numpy Empty Array
Python Marathon
831 views 13 likes 2 dislikes 19 Jul 201960% match

Learn Excel 2010 - "Next Invoice Number": Podcast #1505
MrExcel.com
382.9K views 2K likes 92 dislikes 10 Jan 201260% match

Ciambellone soffice all’arancia – Il segreto per farlo alto e soffice | ricetta facile e veloce
Cucina Geek
381.7K views 0 likes 0 dislikes 18 Jan 202060% match

Road Trip Europe (Hamburg to Copenhagen) | From Germany To Denmark by Car | RoamerRealm
RoamerRealm
877 views 51 likes 3 dislikes 30 Sep 201959% match

Conecta tu celular a tu Televisor SIN CABLES (2da Parte)!
[email protected]
403.4K views 9.7K likes 546 dislikes 19 Sep 201859% match

HOW TO CREATE E-COMMERCE WEBSITE IN BUILDERALL (STEP-BY-STEP) [PART 1 OF 2]
Fábio Ourique // AI Solutions
765 views 74 likes 0 dislikes 16 Jun 202059% match

Ultimate Repair Hacks! Best Ways To Fix Your Boots!
Football Boots
2.3M views 25.9K likes 1.5K dislikes 29 Sep 201758% match

PASTA E FAGIOLI | Ricetta tradizionale pugliese fatta in casa dalla nonna
Cucina Geek
27.4K views 0 likes 0 dislikes 16 Jan 202158% match

100 Pull Up THENX Challenge | 2018
THENX
3.4M views 117.9K likes 1.8K dislikes 04 Mar 201858% match

DIY GUANTE GARRA de FREDDY KRUEGER | PESADILLA en ELM STREET | MANUALIDADES RECICLAJE | Te Digo Cómo
Te Digo Cómo
1.2M views 13.6K likes 843 dislikes 31 Oct 201758% match

10 MOST INNOVATIVE FURNITURE CREATIONS | BEDS | TABLES | DESKS
MINDS EYE DESIGN
17K views 510 likes 47 dislikes 06 Sep 202058% match

Batir 2 ingredientes, cocinar a la sartén y listo! Tenemos postre!
Recipes that work
451.1K views 23.7K likes 481 dislikes 11 May 202058% match

DIY Cómo HACER una PARRILLA GIRATORIA ( Paso a Paso) ( Rotating Grill) #locosxelasado
Leo Besson
1.2M views 21.3K likes 1.1K dislikes 01 Dec 201758% match

Bubble Stitch | Bobble Knitting Pattern
Studio Knit
973K views 25.5K likes 444 dislikes 12 Aug 201758% match

10 Surprising Uses Of Silica Gel You Didn't Know
Facts Verse
2.8M views 16.4K likes 1.8K dislikes 27 Nov 201658% match

Agri R&D 1- Banana Farming केला खेती 8989038222 one Minute video किसानपाठशाला BALRAMKISAN
किसान पाठशाला, FARMER SCHOOL
4.1K views 288 likes -1 dislikes 09 Mar 202158% match

EPICfunnels Review Demo Bonuses~Watch EPICfunnels Review before you buy~
Larry Keen
1.1K views 24 likes 0 dislikes 20 Sep 202058% match

How To Clone or Copy Your Hard Drive With Acronis
Tech Steve
321.9K views 3.9K likes 194 dislikes 02 Feb 201658% match

PENNE ALL’ARRABBIATA 🍝 pochi ingredienti per un successo assicurato
Cucina Geek
44.8K views 0 likes 0 dislikes 21 Oct 202058% match

New start! FORSAGE on Binance Smart Chain
Old Forsage
13.3K views 437 likes 22 dislikes 08 Mar 202157% match

How To ONE ARM Pull Up
THENX
658.3K views 22.2K likes 251 dislikes 03 Jun 201857% match

BEYBLADE BURST SURGE: Brave Valtryek V6 SPARK POWER SET UNBOXING BEYBLADE BURST SPEEDSTORM
Cyprus Channel BEYBLADE X
79.5K views 3.2K likes 149 dislikes 31 Dec 202057% match

Vlogger Kit (which you already have) to record your videos with good quality
GTechMx
15.2K views 71 likes 31 dislikes 20 Aug 202057% match

Escape the Black Hole! Searching for Sneaky Mystery Villain w Sneak Attack Squad
SuperHeroKids
16.2M views 80.6K likes -1 dislikes 06 Jul 201957% match

Life Hacks Which You Didn't Know About
Facts Verse
2.3M views 13.8K likes 2K dislikes 02 Mar 201757% match

BUILD A STRONGER CHEST WITH RINGS
THENX
426.9K views 13.5K likes 133 dislikes 21 Jan 201857% match

【完全マスター13】鼻を高くする！たるまない顔のマル秘法則「たるみ改善！顔ダンス」【アラ還おきゃんママ（加藤ひとみ）】
Method channel that makes you look younger
6.4K views 194 likes 5 dislikes 06 Nov 202057% match

Settings Privacy About Contact Donate