Негізгі бет

Компьютерлік ғылымдар

Course: Компьютерлік ғылымдар > Unit 1

Lesson 10: Ені бойынша іздеу

Ені бойынша іздеу алгоритмі

Ені бойынша іздеу алгоритімі алдымен әр екі шыңға мән береді

v

A қашықтығы, бастапқы шыңнан $v$ ‍ шыңына дейінгі кез-келген жолдағы жиектеріне ең аз санын береді.
бастамашы $v$ ‍ шыңы бастапқы шыңнан біршама қысқа жолға тең болады. Бастапқы шыңның бастамашысы белгілі бір ерекше мәнге тең болып келеді , мысалы, null, бұл оның бастамашысы жоқ екенін көрсетеді.

Егер бастапқы шыңнан

v

- ға дейінгі жол болмаса, онда

v

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

Мысалы, мына суретте, 0-ден 7-ге дейін сегіз шың бар. Олардың нөмірлері жоғарыда немесе төменде орналасқан. Әр шыңның ішінде екі сан бар: бірі деректемеден қашықтығы, оның шыңы 3-ке тең, одан кейін оның алдындағы 3 шыңнан ең қысқа жолмен жүреді. Сызықша null дегенді білдіреді:

BFS - де біз бастапқыда әр шыңның қашықтығы мен бастамашысын арнайы мәнге орнатамыз (null). Біз іздеуді деректемеден бастаймыз және оған 0\ қашықтықты тағайындаймыз. Содан кейін біз деректеменің барлық көршілеріне барып, әр көршімізге 1 қашықтықты береміз және оның алдындағы адамды деректеме ретінде орнатамыз. Содан кейін біз бұрын-соңды болмаған 1 және болатын барлық шыңдардың көршілеріне барамыз, және біз осы шыңдардың әрқайсысына 2 қашықтықты береміз және біз барған шыңды оның алдыңғысына орнатамыз. Біз бастапқы шыңнан қол жетімді барлық шыңдарға барғанға дейін барамыз, әрқашан

k + 1

қашықтықтағы кез-келген шыңға бармас бұрын барлық шыңдарға деректемеден

k

қашықтықта барамыз.

Жоғарыда келтірілген мысалды ескере отырып, әр қадамды ойнату үшін қадамдар мен визуализация қажет:

3-ші шыңнан бастаңыз, оның 0-ге дейінгі қашықтығын орнатыңыз.
содан кейін 2 және 6 шыңдарына барып, олардың 1-ге дейінгі қашықтықты және 3-ші шыңға дейінгі қашықтықты орнатыңыз.
сапарды 2 шыңынан бастап, деректемеден 1 қашықтықтағы шыңдардан бастаңыз. 2-ші шыңнан 4 және 5-ші шыңдарға барып, олардың қашықтықтарын 2-ге, ал олардың алдындағы шыңдарын 2- ге орнатыңыз. 3-ші шыңға бармаңыз, өйткені ол бұрын болған.
- 6-шы шыңнан 5-ші шыңға бармаңыз, өйткені ол 2-ші шыңнан келді, сонымен қатар 3-ші шыңға да бармаңыз.
- енді шыңдарға деректемеден 2 қашықтықта баруды бастаңыз. 4 жоғарғы жағына барудан бастаңыз. 2 шыңы қазірдің өзінде барған. 1-ші шыңға 3-ке дейінгі қашықтықты және оның алдындағы 4-ші шыңға барыңыз.
- 5 шыңынан оның көршілерінің ешқайсысына бармаңыз, өйткені олардың барлығы барған.
- енді шыңдарға деректемеден 3 қашықтықта баруды бастаңыз. Мұндай жалғыз шың-1 шыңы. Оның көршілері, 4 және 5 шыңдары қазірдің өзінде болды. Бірақ 0 шыңы мұны істемеді. 0-ші шыңға оның 4-ші қашықтығын және оның алдындағы 1-ші шыңды орнатыңыз.
- енді шыңдарға деректемеден 4 қашықтықта баруды бастаңыз. Бұл жай ғана 0 шыңы, ал оның көршісі, 1 шыңы қазірдің өзінде бар. Біз аяқтадық!

Назар аударыңыз, 3-ші шыңнан 7-ші шыңға дейінгі жолдың болмауына байланысты іздеу ешқашан 7шыңына бармайды. Оның қашықтығы мен бастамашысы бастапқы null мәндерімен салыстырғанда өзгеріссіз қалады.

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

Тағы бір сұрақ - қандай шыңдарға барғанын, бірақ әлі келмегенін қалай бақылау керек. Біз кезек қолданамыз, бұл жойылатын элемент әрқашан ең ұзақ кезекте тұрған элементтерді енгізуге және жоюға мүмкіндік беретін деректер құрылымы. Біз бұл әрекетті бірінші кіріс, бірінші шығу деп атаймыз. Кезек үш операциядан тұрады:

enqueue(obj) объектіні кезекке қояды.
enqueue(obj) сол объектіні қайтару кезінде ең ұзақ тұрған объектіні кезектен алып тастайды.
isEmpty() егер кезекте объектілер болмаса, шын және егер кезекте кемінде бір объект болса, жалған жауабын қайтарады.

Біз кез-келген шыңға алғаш барған кезде оны кезекке қоямыз. Басында біз бастапқы шыңды кезекке қоямыз, өйткені бұл әрқашан біз баратын алғашқы шың. Келесіге қай шыңға бару керектігін шешу үшін біз ең ұзақ кезекте тұрған шыңды таңдаймыз және оны кезектен алып тастаймыз—басқаша айтқанда, dequeue() - тен қайтарылған шыңды қолданамыз. Біздің графикалық мысалды ескере отырып, әр қадам үшін кезек қалай көрінеді, сонымен қатар кезек күйімен көрсетілген алдыңғы визуализация:

Бастапқыда кезек тек 3 шыңынан тұрады, 0 қашықтықта.
- 3 шыңын кезектен алып тастаңыз және 2 және 6 шыңдарын кезекке қойыңыз, екеуі де 1 қашықтықта. Енді кезек 2-ден 1-ге дейінгі және 6-дан 1-ге дейінгі шыңнан тұрады.
- 2 шыңын кезектен алып тастаңыз және 4 және 5 шыңдарын кезекке қойыңыз, екеуі де 2 қашықтықта. Енді кезек 6-дан 1-ге дейін, 4-тен 2-ге дейін және 5-тен 2-ге дейін.
- 6 шыңын кезектен алып тастаңыз және ешқандай шыңдарды кезекке қоймаңыз. Енді кезекте 4 қашықтық 2 және 5 қашықтық 2 шыңы бар.
- 4-ші шыңнан кезекті алып тастаңыз және 1-ші шыңды 3-ші қашықтыққа кезекке қойыңыз. Енді кезек 5-тен 2-ге дейінгі және 1-ден 3-ке дейінгі шыңнан тұрады.
- 5 шыңын кезектен алып тастаңыз және кезекке ешқандай шыңдарды қоймаңыз. Енді кезек тек 1 қашықтықпен 3 шыңын қамтиды.
- 1 шыңын кезектен алып тастаңыз және 4 қашықтықпен 0 шыңын кезекке қойыңыз. Енді кезек тек 0-ден 4-ке дейінгі шыңнан тұрады.
- 0 шыңын кезектен алып тастаңыз және ешқандай шыңдарды кезекке қоймаңыз. Кезек қазір бос. Кезек бос болғандықтан, ені бойынша іздеу аяқталады.

Назар аударыңыз, кез-келген сәтте кезек бірдей қашықтықтағы шыңдардан тұрады немесе

k

қашықтықтағы шыңдардан тұрады, одан кейін

k + 1

қашықтықтағы шыңдар болады.

k + 1

қашықтықтағы кез-келген шыңдарға бармас бұрын, біз барлық шыңдарға

k

қашықтықта баруды қамтамасыз етеміз.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.

Талқылауға қосылғыңыз келе ме?

Кіру

Сұрыптау:

Әзірге посттар жоқ.

Ағылшынша түсінесің бе? Ағылшын тіліндегі Khan Academy сайтында қандай талқылау болып жатқанын білу үшін мына жерге бас.