So, we're going to change this to breadth first search, but we're going to do it really easily,
at least for the people version, by grabbing the first element off the open list
instead of the last element off the open list.
Let's take a look at how that changes things.
We start off with d as the first thing added to the list and d on the open list, and now
what we do is, well the first and the last element are the same, so nothing changed yet.
We grab d off, we mark any unmarked neighbors of that node of d,
which in this case are e and c just as before and that's done for this time through.
And now, we go back up to the top and things get a little different.
This time, well, actually not that different, the order was sort of
arbitrary and so first and last are sort of arbitrary.
We're going to grab the first thing off the list just like the instruction say and that's e,
add its neighbors in, they still get added to the end of the list, so that's a little different in terms
of the numbering so far, but now it's where we go back up to the top and we grab the first
element of the list in which this case is c, so we're alternating.
Instead of continuing in one direction, we're actually expanding outward from d,
with the d and then c and e, and then b and f.
And now, what happens next if we expand from f with expanded g, add it to the open list,
but now, before we touch g, we're always pulling off the front of the list now, we get to b.
Right now, we've visited everything.
The next thing we pull off is g, we notice that it has no open neighbors, then we pull off a,
we notice that it has no open neighbors, and the open list is empty, the search is finish.
You can see what happens in this case is we expanded out from d and now a and g,
well the sum of the a and g are 13 instead of 12, which is not a really significant or
meaningful difference at this point but it is indicating that the search is proceeding differently
and the way it's proceeding importantly is out from the center.
All the paths that it found, all the edges that it expanded
in new shortest distances it was away from the beginning state.
So, this is going to give us what we need to actually find shortest paths.
तो, हम इस प्रथम चौड़ाई खोज करने के लिए परिवर्तित करने के लिए जा रहे हैं, लेकिन हम यह सच में आसानी से क्या करने जा रहे हैं,
कम से कम लोगों के संस्करण के लिए, करके खुला सूची बंद के पहले तत्व कब्जाने
खुला सूची बंद पिछले तत्व के बजाय।
चलो कैसे कि चीजें बदल जाता है पर एक नज़र रखना।
हम पहली बात सूची करने के लिए जोड़ा गया के रूप में डी और खुले सूची, पर डी के साथ शुरू और अब
है क्या हम करते हैं, अच्छी तरह से पहले और अंतिम तत्व एक ही है, हैं तो अभी तक कुछ नहीं बदला।
हम डी से बाहर ले लो, हम किसी अगोचर पड़ोसियों डी के उस नोड के निशान,
जो इस मामले में ई और सी के रूप में पहले ही हैं और जो के माध्यम से इस समय के लिए किया जाता है।
और अब, हम वापस ऊपर जाना और कुछ थोड़ा अलग हो।
इस समय, अच्छी तरह से, वास्तव में अलग नहीं, आदेश की तरह था
मनमाने ढंग से और इतने पहली और आखिरी की तरह मनमाने ढंग से कर रहे हैं।
हम जैसे कहना है अनुदेश और ई है कि पहली बात है बस सूची बाहर हड़पने के लिए जा रहे हैं,
उसके पड़ोसी देशों में जोड़ने के लिए, कि शब्दों में कुछ अलग है, तो वे अभी भी सूची के अंत में जोड़ा मिल
अभी तक है, लेकिन अब क्रमांकन का यह है है जहाँ हम वापस शीर्ष करने के लिए ऊपर जाना है और हम पहले ले लो
तत्व सूची में सी, यह मामला है तो हम बारी कर रहे हैं।
एक ही दिशा में आगे बढ़ने के बजाय, हम वास्तव में बाहर की ओर डी से विस्तार कर रहे हैं,
डी और फिर सी और ई, और फिर बी और एफ के साथ।
और अगर हम विस्तारित जी के साथ f से विस्तृत करें अब, आगे क्या होता है, यह खुले सूची में जोड़ें,
लेकिन अब, इससे पहले कि हम जी को छूने, हम हमेशा सूची के सामने से खींच कर रहे हैं अब, हम बी करने के लिए जाओ।
ठीक है अब, हम सब कुछ देखी गई।
अगली बात हमें करना बंद है जी, हम सूचना है कि यह कोई खुला पड़ोसी है, तो हम करना बंद एक,
हम नोटिस कि यह कोई खुला पड़ोसियों, है और खुले सूची खाली है, खोज समाप्त है।
आप देख सकते हैं क्या इस मामले में होता है हम डी से बाहर विस्तृत और अब एक और जी,
अच्छी तरह से योग का एक और जी हैं बजाय 12, 13 जो एक वास्तव में महत्वपूर्ण नहीं है या
सार्थक अंतर इस बिंदु पर, लेकिन यह इंगित करता है कि खोज अलग ढंग से आगे बढ़ रहा है
और जिस तरह से यह महत्वपूर्ण बात आगे बढ़ रहा है केंद्र से बाहर है।
सभी रास्तों कि यह पाया, सभी किनारों कि यह का विस्तार किया
नए कम से कम दूरी में इसे शुरुआत के राज्य से दूर था।
तो, यह हमें क्या हम वास्तव में कम से कम पथ को खोजने के लिए की आवश्यकता देने के लिए जा रहा है।
次はこれを幅優先探索に変えますが
自分でやる場合は簡単で
リストから消す要素の順番が
最後から最初に変わるだけです
では実際に見ていきましょう
まずはdをオープンリストに加えます
リストにあるのはdだけなので
最初の要素も最後の要素も同じです
リストからdを消して隣接するノードをマークします
この場合はeとcですがここは前と同じです
そしてここからの手順が変わってきます
今回は最初と最後の要素の順序が任意なので
実は大して変わらないのですが
ここでリストの最初の要素であるeを消します
次は前と同様に隣接するノードを
リストの最後に加えます
これでノードの下に振る番号順が前と変わってきます
次にリストの最初の要素であるcを消します
つまりここでは
1方向に進む代わりに両側に広がっていきます
最初がdで次がcとeその次がbとfときています
次にfを消して隣接するgをリストに加えます
次はまたリストの最初にあるbを消します
最後にaをリストに加えて
次はgですが隣接するノードは
マーク済みなのでaを消します
aと隣接するノードもマーク済みで
リストも終わりなのでこれで完了です
今回はdからスタートして最後はaとgに広がっています
この場合のaとgの合計は12ではなく13になりましたが
この時点では重要ではありません
しかしこれが処理の違いを示しています
ここで重要なのは処理が中から外へ広がることです
すべてのエッジが外に広がっており
パスは最初のノードから外に向かっています
これが最短経路を見つける手立てになります