РусҚаз

Дейкстра алгоритмі

Информатика · 10-сынып · Графтар және жол іздеу · Сабақ 3 / 4

Интерактивті сабақты ашу ›Өз қолыңмен тәжірибе, дауыспен дәріс, ЖИ-тәлімгер және тест. Тегін.

Бұл не?

Сабақтың тақырыбы — «Дейкстра алгоритмі». Талдап көрейік. Қала арқылы келе жатырсың деп елестет: кептелісі бар үш қиылыстан өтуге болады, ал бос жолмен бес қиылыстан өтіп, ертерек жетуге де болады. Дейкстра алгоритмі бөліктер саны аз жолды емес, салмақтарының қосындысы ең аз жолды іздейді — минуттардың, километрлердің немесе ақшаның.

Дейкстра алгоритмі — Бұл не?

Бұл не үшін керек?

Осы идеяға навигаторлар мен жеткізу қызметтері, жүргізушісіз көліктер мен дрондардың маршруттары, интернеттегі және дата-орталықтардағы серверлер арасында деректер пакеттерін жіберу сүйенеді. Амазон сияқты ірі компаниялардың логистикасы күн сайын орасан зор графтарда ең арзан маршруттар туралы есептер шешеді. Жасанды интеллект кодты бір секундта жасап бере алады, бірақ салмақ деп нені санау керегін — уақытты ма, бағаны ма, әлде энергия шығынын ба — түсінетін, алгоритм бұзылатын теріс салмақты байқайтын және маршруттың өмірде ақылға қонымды екенін тексеретін адам керек. Машиналарға тапсырма қойып, нәтижеге жауап беретін де дәл осындай адамдар.

Дейкстра алгоритмі — Бұл не үшін керек?

Бұл қалай жұмыс істейді?

Әр төбенің белгісі бар — бастаудан белгілі ең жақсы қашықтық: бастауда нөл, қалғандарында шексіздік. Әр қадамда алгоритм кезектен белгісі ең кіші төбені алып, оны біржола бекітеді. Содан кейін оның көршілеріне қарайды: егер осы төбе арқылы көршіге дейінгі жол бұрынғыдан қысқа шықса, көршінің белгісін азайтады. Бекітілген белгіні енді ештеңе жақсарта алмайды, өйткені кез келген басқа жол белгілері одан кем емес төбелер арқылы өтеді, ал салмақтар теріс емес. Ал ашкөз тәсіл — әрқашан ең арзан жолмен жүру — алдап кетеді: басындағы арзан қабырға соңында өте қымбат бөлікке апаруы мүмкін.

Дейкстра алгоритмі — Бұл қалай жұмыс істейді?

Аздап тарих

Нидерландтық ғалым Эдсгер Дейкстра өз алгоритмін мың тоғыз жүз елу алтыншы жылы ойлап тапты. Кейін ол дүкендерді аралағаннан кейін қалыңдығымен Амстердамдағы кафенің террасасында отырып, бәрін жиырма минуттай уақытта, қарындаш пен қағазсыз ойлап тапқанын айтып берген. Оның айтуынша, алгоритмнің соншалық қарапайым әрі әдемі болып шыққаны да сондықтан.

Дейкстра алгоритмі — Аздап тарих

Формула: жаңа белгі

Алгоритмнің басты әрекеті қабырғаны релаксациялау деп аталады. Біз вэ төбесінде тұрмыз, оған дейінгі қашықтықты білеміз, және одан у көршісіне салмағы дубль-вэ қабырға апарады. Егер вэ-дан алынған дэ қосу дубль-вэ у-дан алынған дэ-дан кіші болса, онда біз қысқарақ жол таптық, және сонда у-дан алынған дэ вэ-дан алынған дэ қосу дубль-вэге тең болады. Мұндағы дэ — белгі, яғни бастаудан қашықтық, ал дубль-вэ — қабырғаның салмағы, және олар бірдей бірліктермен, мысалы минутпен өлшенеді. Қабырғаның салмағы неғұрлым үлкен болса, бұл өту бірдеңені соғұрлым сирек жақсартады, ал қабырға өте жеңіл болса — көршінің белгісі айтарлықтай азаяды.

  • если d(v) + w < d(u), то d(u) = d(v) + wd(v) — v төбесінің белгісі — бастаудан қашықтық, мин
    d(u) — u көршісінің белгісі, мин
    w — v-дан u-ға дейінгі қабырға салмағы, мин

Практикада не істейміз?

Ал енді практикалық тапсырманы орындап көрейік. Алдыңда A-дан G-ге дейінгі төбелері бар жолдар графы тұр, қабырғаларда жолдағы минуттар жазылған; бастау A-да, мәре G-де, A-ның белгісі нөл, қалғандарының бәрінде шексіздік. Алгоритмнің рөлін өзің атқарасың: әр қадамда алгоритм кезектен алатын төбені, яғни белгісі ең кішісін басып, оның көршілерінің белгілері қалай өзгеретінін бақыла. Осылай мәреге дейін жет, содан кейін «Ашкөз» батырмасын басып, екі маршрутты салыстыр: олардың қайсысы жылдам және неге. Бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, жауап беремін. Уайымдама.

Тәжірибедегі тапсырма

Дейкстра алгоритмін өзіңіз жүргізіңіз: әр қадамда алгоритм кезектен алатын төбені басыңыз. Мәреге жетіңіз, содан кейін «Ашкөз» басып, маршруттарды салыстырыңыз.
Интерактивті сабақты ашу ›Өз қолыңмен тәжірибе, дауыспен дәріс, ЖИ-тәлімгер және тест. Тегін.

Тақырып сабақтары: Графтар және жол іздеу

  1. Граф деген не
  2. Ені бойынша аралау
  3. Дейкстра алгоритмі
  4. Айналамыздағы графтар