Графиктерді іздеу алгоритмдеріне және жолдарды іздеу алгоритмдеріне бөлу

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 4 бет
Таңдаулыға:

Қазақстан Республикасының Білім және ғылым министрлігі

С. Сейфуллин атындағы қазақ агротехникалық университеті

«Ақпараттық жүйелер» кафедрасы

КУРСТЫҚ ЖҰМЫС

6В061 - «АКТ» даярлау бағыты бойынша «Бағдарламалық инженерия » мамандығы

Тақырыбы: Іздеу Алгоритмдер

Пәні: Алгоритм, деректер құрлымы және бағдарламалау

Орындаған: топ студенті

(Аты-жөні)

Тексерген

( оқытушы аты-жөні)

Курстық жұмыс қорғауға жіберілді

(оқытушы қолы)

Нұр-Сұлтан 2023

Мазмұны:

Кіріспе

Іздеу алгоритмі-берілген деректер жиынындағы белгілі бір элементті немесе мәнді іздеу жолын анықтайтын процедура немесе нұсқаулар жиынтығы. Әр түрлі іздеу алгоритмдері бар, олардың әрқайсысының өзіндік сипаттамалары мен әртүрлі жағдайларда қолданылуы бар. Ең көп таралған іздеу алгоритмдерінің қатарына Сызықтық іздеу, екілік іздеу, хэш кестелерін іздеу және т. б.

Сызықтық іздеу-бұл сәйкестік табылғанға дейін немесе барлық элементтер тексерілгенге дейін берілген деректер жиынындағы әрбір элементті дәйекті түрде тексеретін қарапайым іздеу алгоритмі.

Екілік іздеу-сұрыпталған деректер жиынына қолданылатын іздеу алгоритмі. Ол сәйкестік табылғанша немесе іздеу аймағы бос болғанша іздеу аймағын үнемі екіге қысқартуға негізделген.

Хэш кестелерін пайдаланып іздеу-ізделетін мәнді массив индексіне түрлендіру үшін хэш функциясын пайдалануға негізделген іздеу алгоритмі. Бұл массив индексін іздеу арқылы мәнді табуға мүмкіндік береді, бұл алгоритмді өте тиімді етеді.

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

Жолды іздеу алгоритмдері-графиктегі немесе тордағы екі нүкте арасындағы оңтайлы жолды (ең қысқа немесе ең арзан) табу үшін қолданылады. Мысалдарға Дайкстра алгоритмі және А алгоритмі жатады.

Машиналық оқыту әдістері-оқытылған модельге негізделген үлгілерді немесе ізделетін мәндерді табу үшін пайдалануға болады. Мысалдарға нейрондық желілерді, SVM немесе шешуші ағаштарды пайдалану әдістері жатады.

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

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

Іздеу алгоритмдерін әртүрлі критерийлер бойынша жіктеуге болады:

Сызықтық және сызықтық емес алгоритмдерге бөлу:

Сызықтық Алгоритмдер барлық элементтерді ізделген элемент табылғанға дейін немесе барлық элементтер өткенге дейін реттелген ретпен қайталайды.

Сызықтық емес Алгоритмдер ізделетін элементті тиімдірек табу үшін екіге бөлу немесе ағаштарды пайдалану сияқты күрделі стратегияларды қолданады.

Сұрыпталған және сұрыпталмаған массивте іздеу алгоритмдеріне бөлу:

Сұрыпталған массивтегі іздеу алгоритмдері массивтегі элементтер реттелген кезде қолданылады. Олар екілік іздеу немесе интерполяциялық іздеу сияқты әдістерді қолдана алады.

Сұрыпталмаған массивтегі іздеу алгоритмдері қажетті элементті тапқанға дейін массивтің барлық элементтерін дәйекті түрде сұрыптауға негізделген.

Графиктерді іздеу алгоритмдеріне және жолдарды іздеу алгоритмдеріне бөлу:

Графикалық іздеу алгоритмдері графиктегі белгілі бір элементті немесе жолды табу үшін қолданылады. Мұнда ені бойынша іздеу (BFS) немесе тереңдігі бойынша іздеу (DFS) алгоритмдері қолданылуы мүмкін.

Жолдардағы іздеу алгоритмдері жолдағы бір немесе бірнеше ішкі жолдарды табу үшін қолданылады. Мысалы, Кнут-Моррис-Пратт алгоритмі (KMP) немесе Бойер-Мур алгоритмі.

Соңғы автоматты іздеу алгоритмдеріне және тұрақты өрнектердегі іздеу алгоритмдеріне бөлу:

Соңғы автоматтардағы іздеу алгоритмдері жолдағы кейбір үлгіні табу немесе жоқтығын анықтау үшін қолданылады. Мысалы, Ахо-Корасик алгоритмі немесе Рабин-сазан алгоритмі.

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

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

Толық шамадан тыс анықтау:

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

Толық шамадан тыс алгоритмдердің мысалдары:

- Барлық ішкі жиындарды іздеу: бұл алгоритм кейбір жиын элементтерінің барлық тіркесімдерін қайталайды. Мысалы, берілген жиынтық үшін {1, 2, 3} ол барлық ішкі жиындарды, соның ішінде бос жиынды табады, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.

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

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.