I'm going to talk about an algorithm called Floyd Warshall
after two of the inventors of this algorithm back in the early 60s,
and it uses an idea called dynamic programming, which sounds so much cooler than its actually is.
That means, it actually is a very cool idea.
I have a professor friend who believes that I am predispose
to see all problems at dynamic programming problems because it an algorithm design technique
that I have been able to use successfully in a bunch of occasion,
but it really is just an algorithm design technique.
Its not particularly dynamic and it doesn't really change the way you think about programming.
It just have to do with optimizing using tables. Alright.
Let me start up by explaining this algorithm in terms of simple but possibly strange idea.
First just for simplicity, let's imagine all the nodes in our graph are numbered from 0 to n-1,
and lots of graph have exactly have their structure, but for example for our marvel data set,
we have to all our characters be assigned numbers from 0 to n-1,
but that's an easy thing to do, let's imagine that's already been done.
What we're going to imagine now is that someone has given us matrix.
Square matrix D of k and the entries of this matrix, just a big table like a spread sheet
and is filled in with values as follows.
The ij element of the i row, j column is filled in with the number
and that number is the length of the shortest path from i to j
hopping only all nodes numbered less than k.
So I don't know about you but I used to play a game like this when I was younger,
if I was in a building where the tiles were different colors, I'd sometimes declare
let's say, the blue tiles are alligators, so I'm not going to step on any of the blue tiles
and I'd try to walk stepping only on the tiles that I was allowed to use,
so that the analogue of this in the graph is imagine we've got our graph,
and we're trying to get a path from i to j, and some of the nodes are colored pink.
Those are the okay nodes because they are numbered less than k and some of the nodes
maybe including j itself are numbered higher than k, and we're not allowed to step on those.
We're trying to get from i to j, we're allowed to step on j opposite
but only the intermediate nodes that are pink.
We only consider making paths along pink nodes and there's only one in this case.
But there's some pink nodes that we don't use and their maybe multiple different pink paths,
but we want to know the distance of the shortest path using only the pink nodes.
Only the ones that are numbered less than k.
So let's imagine, some very hopefully, has done this for us and filled in the matrix with all those values.
There's big Πof n² values that have to get filled in, but someone has does that for us. That's all great.
Our mission should we choose to accept it. Is to fill in Dk + 1.
So this will be a new matrix just like the old matrix,
but now when your going on a path from i to j, you're allowed to use node k.
You don't have to use it but your allowed so that's all we have to do right now.
Let's try to figure out if someone gives use Dk, how do we figure out Dk+1.
मैं एक एल्गोरिथ्म Floyd Warshall बुलाया के बारे में बात करने जा रहा हूँ
60 के दशक में वापस इस कलन विधि के अन्वेषकों में से दो के बाद,
और यह कहा जाता है गतिशील प्रोग्रामिंग, जो बहुत बहुत से कूलर लगता है की एक विचार का उपयोग करता है इसकी असल में है।
इसका मतलब है, यह वास्तव में एक बहुत अच्छा विचार है।
मैं एक प्रोफेसर दोस्त है जो विश्वास करता है कि मैं कर रहा हूँ संभावना अधिक होती है
यह एक एल्गोरिथ्म डिजाइन क्योंकि तकनीक गतिशील प्रोग्रामिंग समस्याओं पर सभी समस्याओं को देखने के लिए
मैं सफलतापूर्वक में इस अवसर का एक गुच्छा का उपयोग कर रहा है कि,
लेकिन यह सच में सिर्फ एक एल्गोरिथ्म डिजाइन तकनीक है।
अपनी विशेष रूप से गतिशील नहीं है और यह आप प्रोग्रामिंग के बारे में सोचने का तरीका बदल सच नहीं करता।
यह तालिकाओं का उपयोग कर अनुकूलन के साथ क्या करने के लिए बस है। ठीक है।
मुझे शुरू इस एल्गोरिथ्म सरल लेकिन संभवतः अजीब विचार के संदर्भ में समझा।
पहले सिर्फ सादगी के लिए, चलो कल्पना है हमारी ग्राफ में सभी नोड्स को एन-1, 0 से गिने
और ग्राफ के बहुत सारे बिल्कुल उनकी संरचना, लेकिन उदाहरण के लिए हमारे चमत्कार डेटा सेट के लिए किया है,
हम है हमारे सभी वर्णों के लिए सौंपा जाएगा संख्या 0 से n-1 करने के लिए,
लेकिन जो पहले से ही किया गया है करने के लिए करते हैं, हम सोच भी एक आसान बात है।
क्या हम अब कल्पना करने के लिए जा रहे हैं कि किसी ने हमें दिया है मैट्रिक्स है।
वर्ग मैट्रिक्स D k और इस मैट्रिक्स के प्रविष्टियों की, बस एक बड़ी मेज की तरह एक स्प्रेड शीट
और मूल्यों से इस प्रकार से भरा है।
I के ij तत्व जे स्तंभ, पंक्ति संख्या के साथ भर दिया है
और है कि संख्या मैं से जम्मू के कम से कम पथ की लंबाई
केवल सभी क्रमिक नोड्स से कम k hopping.
मैं आप के बारे में तो पता नहीं, लेकिन मैं जब मैं छोटा था इस तरह का खेल खेलने के लिए इस्तेमाल किया,
अगर मैं में एक इमारत जहां टाइल अलग अलग रंग के थे था, मैं कभी कभी घोषित होगा
चलो कहना, नीली टाइल्स alligators, कर रहे हैं तो मैं नीली टाइल्स से किसी पर कदम करने के लिए नहीं जा रहा हूँ
और मैं केवल पर टाइल है कि मैं का उपयोग करने की अनुमति दी थी आगे बढ़ चलने की कोशिश करेंगे,
इतना है कि इस के अनुरूप ग्राफ में कल्पना है हम हमारे ग्राफ मिल गया है,
और हम एक रास्ता मैं से जम्मू के लिए पाने के लिए कोशिश कर रहे हैं, और कुछ नोड्स के गुलाबी रंग होते हैं।
क्योंकि वे कम गिने जा रहे हैं जो ठीक नोड्स रहे हैं कश्मीर और नोड्स में से कुछ की तुलना
शायद ही जम्मू सहित गिने k से अधिक है, और हम उन पर कदम करने की अनुमति नहीं कर रहे हैं।
हम मैं से जम्मू के लिए पाने के लिए कोशिश कर रहे हैं, हम विपरीत जम्मू पर कदम की अनुमति हो
लेकिन केवल मध्यवर्ती नोड्स कि गुलाबी रहे हैं।
हम केवल गुलाबी नोड्स के साथ पथ बनाने पर विचार करें और वहाँ केवल एक इस स्थिति में है।
वहाँ है, लेकिन कुछ गुलाबी नोड्स कि हम का उपयोग नहीं करते और अपने शायद कई अलग गुलाबी पथ,
लेकिन हम जानते हैं की दूरी कम से कम पथ केवल गुलाबी नोड्स का उपयोग करने के लिए चाहते हैं।
केवल लोगों को है कि गिने जा रहे हैं से कम k.
तो हम सोच भी, कुछ बहुत उम्मीद है, इस हमारे लिए किया है और उन सभी मूल्यों के साथ मैट्रिक्स में भर दिया।
वहाँ भरा हो जाओ करने के लिए है कि n² मूल्यों का बड़ा मैं है, लेकिन किसी को है कि हमारे लिए करता है। यह सब बहुत अच्छा है।
हमारे मिशन हम इसे स्वीकार करने के लिए चुनना चाहिए। डी. के. + 1 में भरने के लिए है।
तो यह सिर्फ पुराने मैट्रिक्स की तरह एक नए मैट्रिक्स हो जाएगा,
लेकिन अब जब अपने एक पथ पर मैं से जम्मू के लिए जाने, आप नोड कश्मीर का उपयोग करने की अनुमति हो।
तुम तो है कि हम सभी को अब ठीक करने के लिए यह आपकी अनुमति प्राप्त लेकिन का उपयोग करने के लिए नहीं है।
चलो पता अगर किसी ने जानने की कोशिश देता है डी. के. का प्रयोग करें, कैसे कर हम यह आंकड़ा बाहर डी. के. + 1।
ワーシャル-フロイド法について少し触れます
60年代初頭に2人の数学者によって考案されました
動的計画法という概念を用いています
事実役立ちますが
本質以上にクールな名前ですね
実際私も様々な機会に
動的計画法を活用してきました
しかしそれは単に1つの
アルゴリズムの設計テクニックなのです
プログラミングを動的に変えるというより
テーブルの利用を最適化しているのです
このアルゴリズムについて説明していきます
まずグラフ上のノードに0からn-1まで番号が
振られていると思ってください
アメコミのデータセットを例に挙げて考えましょう
登場人物に0からn-1番までの番号を振ります
簡単ですね
次のDk正方行列と入力のための集計表のような
大きなテーブルを与えられたと仮定します
次の値が入っています
i行とj列の要素には番号が入っておりその番号は
iからjへの最短距離の値です
kより小さい値のノードにだけ移動します
子供の頃こんなゲームをして遊びました
いろんな色のタイルが敷かれた床で
例えば青のタイルはワニだから踏まないとか
決めた色のタイルの上だけ踏んでよいとかです
グラフ上でも同じように考えます
iからjへ移動する時いくつかのノードは
ピンクだと仮定します
ピンクのノードはkより小さい値なので
通っても大丈夫です
kより大きい値のノードは通ることはできません
jは到達点なので例外ですが
間のノードはピンクのものだけです
ピンクだけを通っていくパスはこの場合1つだけです
踏まれないピンクのノードもあるかもしれませんが
ピンクのノードのみを通る最短の距離を知りたいのです
Kより小さい値のノードです
これらの値がすべて行列に入力されていると仮定します
Θ(n³)個の値がすでに入力されていると仮定します
ここでDk+1という新しい行列を用意することは
許容されるのでしょうか
この場合はノードkを使うことが許されます
絶対使わなくてはならないわけではありません
Dk+1はどのように算出すべきでしょうか