Х. ДосмҰхамедов
жүктеу/скачать 3 Mb.
|
| Тереңдігі бойынша іздеу
Графтарды өңдеу үшін бірнеше белгілі алгоритмді қолданады. Солардың бірі – тереңдігі (ағылш. depth-first search, DFS) бойынша іздеу. Алгоритм графтың барлық шыңын іздеуге қатысты есептерді шешеді. Аталған алгоритм қысқа жолдарды іздеу үшін тағайындалмаған, бірақ оның көмегімен графтың кез келген шыңынан бастап барлық іздеу жолын құруға болады. Елестетіңіз, сіз лабиринттесіз (граф) және оны қарастырғыңыз келеді. Ол үшін сізге оның барлық жолымен (қабырғасымен) жүріп, барлық үңгірін (шыңын) қарауыңыз керек. Бұл ретте лабиринттің барлық үңгірін қарау және барлық жолымен жүру міндетті емес, бірақ іздеу ережелерін сақтау қажет. Бұл есептің мағынасы осындай. Сонымен, сіз лабиринт кіре берісінде тұрсыз және бірнеше жолды көріп тұрсыз. Сіз былай істеуіңіз мүмкін: Кез келген әлі зерттелмеген аралық үңгірге бару; Үңгірдегі қол жетімдінің барлығын іздеу. Сол уақытта әрдайым алға, жаңа зерттелмеген үңгірлерге бару. Баратын жолы жоқ үңгірге тап болған кезде бұрынғы үңгірге қайта оралу; 1 және 2-қадамды басшылыққа алып, барлық аралық үңгірді зерттеу. Барлық үңгір зерттеліп біткен кезде, зерттеудің есебі толық аяқталады. Мұндай іздеуді рекурсивті іздеу деп атайды. Әр жаңа шыңға жеткенде бастапқы шыңды игеру кезінде қолданған іс-әрекетті қайталау керек болады. Шыңдарды іздеу процессі кезінде жаңа шыңдарды ерекшелеп қою қажет. Ол үшін бағдарламалық кодта visited тізімін қолданамыз. Егер шыңға кіріп шықсақ, visited == True белгісін, кірмесек False белгісін қоямыз. Іздеу кезінде жаңа шыңдардың кезегін path тізімінде сақтаймыз. Тереңдігі бойынша іздеуді жүзеге асыру үшін DFS рекурсивті функциясын қолданамыз. Функцияның формальді параметрі ретінде іздеу басталатын шыңның нөмірін пайдалануға болады. Графты қарастырайық: 1-сурет Бұл – байланысты, 6 шың және 6 қабырғаны қамтитын бағытталмаған граф. Осы графтың тереңдігі бойынша іздеуге арналған бағдарламалық кодтың мысалы 2-суретте көрсетілген. 2-сурет Аталған бағдарламаны қосу кезінде бастапқы шыңның мәнін енгізу қажет. Графта кез келгені бастапқы шың болуы мүмкін. Барлық шыңның өзіндік мәнін path тізімінен алуға болады. Іздеу кезінде аралық шыңдар графтың сипаттамасындағы кезектілікке сәйкес қарастырылады. Әдетте, граф шыңдары бағдарламалық кодта нөмірленеді және нөмірлерінің өсуі бойынша қарастырылады. 3 мәнін енгізген кезде бағдарлама беретін жауапты тексеру қиын емес. 3 шыңын тереңдігі бойынша іздеу коды: [3, 2, 1, 4, 5, 6]. жүктеу/скачать 3 Mb. Достарыңызбен бөлісу:
|