РусҚаз

Ені бойынша аралау

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

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

Бұл не?

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

Ені бойынша аралау — Бұл не?

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

Толқынды іздеу робот шаңсорғыштардың және сөрелер арасынан өтетін жол іздейтін қойма роботтарының ішінде, кейіпкерлер кедергілерді айналып өтетін компьютерлік ойындарда жұмыс істейді. Дәл осы тәсілмен әлеуметтік желілер достарыңның достарын табады, ал баспа платалары мен чиптердегі жолдарды орналастыратын бағдарламалар сымға қысқа трасса іздейді. Жасанды интеллект аралау кодын бір секундта оңай жазып береді, бірақ тапсырмада нені шаршы деп санау керегін, қабырғалар қайда екенін және жол неге кенеттен басқаша шыққанын адам шешуі керек. Толқынның қалай жүретінін түсінетін адам машинаны тексеріп, қатені таба алады.

Ені бойынша аралау — Бұл не үшін керек?

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

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

Ені бойынша аралау — Бұл қалай жұмыс істейді?

Аздап тарих

Өткен ғасырдың елуінші жылдарының соңында америкалық математик Эдвард Мур лабиринттегі ең қысқа жолды табудың толқынды тәсілін сипаттады. Шамамен сол уақытта инженерлер дәл осы идеяны электрондық платалардағы қосылыстарды салу үшін қолданды. Бүгін бұл тәсіл кез келген бағдарламалау оқулығына және микросхемаларды жобалау бағдарламаларына енген.

Ені бойынша аралау — Аздап тарих

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

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

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

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

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

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