Лабораторная работа X «Поиск, хеширование и поиск с возвратом»
Эта работа раскрывает тему «Поиск и расстановка» шире простого бинарного поиска.
Работа состоит из двух частей.
Хеш-поиск:
-
простая хеш-функция;
-
массив таблицы;
-
коллизии;
-
цепочки либо открытая адресация;
-
вставка;
-
поиск;
-
удаление;
-
коэффициент заполнения.
Поиск с возвратом:
-
генерация перестановок;
-
расстановка N ферзей либо задача составления расписания;
-
отсечение заведомо неверных частичных решений.
Прикладной вариант для бизнес-информатики:
распределить работников по сменам при наборе ограничений.
Основная идея работы — показать различие между:
-
прямым перебором;
-
перебором с возвратом;
-
отсечением;
-
эвристическим порядком перебора.