Графтар және алгоритмдер: түйіндер, байланыстар және ең жақсы жол

Картадағы орнымыз

Логика ауысу ережелерін берді. Граф оларды нысандар арасындағы қырларға айналдырады, алгоритм әрекеттердің қайталанатын ретін белгілейді.

Алдымен таныс бейне

Жол картасы, достар желісі, тапсырма тәуелділігі және веб-сілтемелер бір құрылымды бөліседі: нысандар мен байланыстар. Қыр салмағының бірлігі ортақ болуы тиіс.

Дәл мағынасы

Граф төбелер мен қырлардан тұрады. Қыр бағытталған не бағытталмаған, салмақталған не салмақсыз болады. Жол — көршілес төбелер тізбегі. Теріс емес салмақта Дейкстра ең жақын бекітілмеген төбені таңдап, көршілер бағасын жаңартады. Теріс қырлар басқа алгоритмді талап етеді.

Сабақтың тірек сигналы

мағына → модель → есептеу → тексеру → өз сөзіңмен түсіндіру

түйіндер мен қырлар → салмақ бірлігі → бастапқы арақашықтық → ең жақын төбе → көршілерді жаңарту → қайталау → жолды қалпына келтіру

Талданған мысал

A-дан C=2, B=4. C арқылы B=3 болып жақсарады. B арқылы D=8, D арқылы E=10, E арқылы F=13. Алдыңғы төбелер A→C→B→D→E→F, қосынды 2+1+5+2+3=13 жолын береді.

Көмегі азайған мысал

Мысалдағы сандарды өзгертіп, шешімді дайын жолға қарамай қайталаңыз. Алдымен нәтижені шамалаңыз, содан кейін дәл есептеп, бастапқы шартпен тексеріңіз.

Көмексіз жаңғыртыңыз

1. Негізгі ұғымды бір сөйлеммен анықтаңыз.
2. Тірек сигналын жапқан күйде қайта жазыңыз.
3. Мысалды басқа сандармен шешіп, әр қадамның себебін айтыңыз.

Қатені тауып түзетіңіз

Әр қиылыстағы ең қысқа шығыс қырды таңдап, оны жалпы ең қысқа жол деу қате. Жергілікті арзан қадам қымбат жалғасуға апаруы мүмкін; толық қашықтық салыстырылады.

Жаңа жағдайға көшіру

Осы байланысты өзіңіз өлшей алатын жағдайға қолданыңыз. Шамаларды, өлшем бірліктерін және модель жарамды болатын шекараны атаңыз. Жауапты екінші тәсілмен немесе кері амалмен тексеріңіз.

Тапсырма

Міндетті. Сызбада A-дан барлық төбеге дейінгі қысқа қашықтықтарды Дейкстра кестесімен табыңыз. D–E қырын алып тастап, F-ке есепті қайталаңыз. Салмақсыз ен бойынша іздеу керек болатын бір мысал келтіріңіз.

Өз дерегіңізбен. Күнделікті өмірден осы құрылымға сай бір мысал құрып, оны сөзбен, формуламен және тексерумен көрсетіңіз.

Қалауыңызша. Жеті күннен кейін сандарды ауыстырып, тірекке қарамай қайталаңыз.

Ашық перспектива

Келесі сабақ дерек, ықтималдық, функция, матрица және графты бір тексерілетін модельдеу цикліне біріктіреді.

Курс мазмұны