Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

2.4. РЕАЛЬНЫЕ ПРИЛОЖЕНИЯ
Поиск.играет.важную.роль.во.всех.полезных.программах..В.некоторых.случаях.
это.центральный.элемент.приложения.(Google.Search,.Spotlight,.Lucene),.в.других.
он.оказывается.основой.для.использования.структур,.на.которые.опирается.си-
стема.хранения.данных..Знание.правильного.алгоритма.поиска.для.применения.
к.структуре.данных.имеет.большое.значение.для.производительности..Напри-
мер,.было.бы.слишком.затратно.выполнять.в.отсортированной.структуре.данных.
линейный.поиск.вместо.двоичного.

---

2.5. Упражнения
83
A*.—.один.из.наиболее.распространенных.алгоритмов.поиска.пути..Его.превосхо-
дят.только.алгоритмы,.которые.выполняют.предварительный.расчет.в.простран-
стве.поиска..В.слепом.поиске.у.A*.все.еще.нет.конкурентов.в.любых.сценариях,.
и.это.сделало.его.неотъемлемым.компонентом.всех.областей,.от.планирования.
маршрута.до.определения.кратчайшего.способа.синтаксического.анализа.языка.
программирования..В.большинстве.картографических.программ,.прокладыва-
ющих.маршрут,.таких.как.Google.Maps,.для.навигации.используется.алгоритм.
Дейкстры.(вариант.A*).(подробнее.об.алгоритме.Дейкстры.читайте.в.главе.4)..
Всякий.раз,.когда.игровой.персонаж.с.элементами.искусственного.интеллекта.
находит.кратчайший.путь.от.одной.точки.игровой.карты.до.другой.без.вмеша-
тельства.человека,.он,.скорее.всего,.применил.алгоритм.A*.
Поиск.в.ширину.и.поиск.в.глубину.часто.являются.основой.для.более.сложных.
алгоритмов,.таких.как.поиск.с.равномерными.затратами.и.поиск.в.обратном.на-
правлении,.с.которыми.вы.познакомитесь.в.следующей.главе..Поиска.в.ширину.
часто.достаточно.для.прокладки.кратчайшего.пути.в.не.очень.большом.графе..Но.
поскольку.он.похож.на.A*,.то.для.большого.графа.его.легко.заменить.на.A*,.если.
существует.хорошая.эвристика.
2.5. УПРАЖНЕНИЯ
1.. Продемонстрируйте.преимущество.в.производительности.бинарного.по-
иска.по.сравнению.с.линейным.поиском,.создав.список.из.миллиона.чисел.
и.определив,.сколько.времени.потребуется.созданным.в.этой.главе.функциям.
linearContains()
.и.
binaryContains()
.для.поиска.в.нем.различных.чисел.
2.. Добавьте.в.
dfs()
,.
bfs()
.и.
astar()
.счетчик,.который.позволит.увидеть,.сколько.
состояний.просматривает.каждая.из.этих.функций.в.одном.и.том.же.лабиринте..
Найдите.значения.счетчика.для.100.различных.лабиринтов,.чтобы.получить.
статистически.значимые.результаты.
3.. Найдите.решение.задачи.о.миссионерах.и.каннибалах.для.разного.числа.
миссионеров.и.каннибалов.

---

3
Задачи с ограничениями
Многие.задачи,.для.решения.которых.используются.компьютерные.вычисления,.
можно.в.целом.отнести.к.категории.задач.с.ограничениями.(constraint-satisfaction.
problems,.CSP)..CSP-задачи.состоят.из.
переменных
,.допустимые.значения.кото-
рых.попадают.в.определенные.диапазоны,.известные.как.
области
.
определения
..
Для.того.чтобы.решить.задачу.с.ограничениями,.необходимо.удовлетворить.
существующие.ограничения.для.переменных..Три.основных.понятия.—.пере-
менные,.области.определения.и.ограничения.—.просты.и.понятны,.а.благодаря.
их.универсальности.задачи.с.ограничениями.получили.широкое.применение.
Рассмотрим.пример.такой.задачи..Предположим,.что.вы.пытаетесь.назначить.на.
пятницу.встречу.для.Джо,.Мэри.и.Сью..Сью.должна.встретиться.хотя.бы.с.одним.
человеком..В.этой.задаче.планирования.переменными.могут.быть.три.человека.—.
Джо,.Мэри.и.Сью..Областью.определения.для.каждой.переменной.могут.быть.
часы,.когда.свободен.каждый.из.них..Например,.у.переменной.«Мэри».область.
определения.составляет.2,.3.и.4.часа.пополудни..У.этой.задачи.есть.также.два.
ограничения..Во-первых,.Сью.должна.присутствовать.на.встрече..Во-вторых,.на.
встрече.должны.присутствовать.по.крайней.мере.два.человека..Решение.этой.
задачи.с.ограничениями.определяется.тремя.переменными,.тремя.областями.
определения.и.двумя.ограничениями,.тогда.задача.будет.решена.и.при.этом.не.
придется.объяснять.пользователю,.
как
.
именно
.(рис..3.1).
В.некоторых.языках.программирования,.таких.как.Prolog.и.Picat,.есть.встроенные.
средства.для.решения.задач.с.ограничениями..В.других.языках.обычным.подхо-
дом.является.создание.структуры,.которая.включает.в.себя.поиск.с.возвратами.
и.несколько.эвристик.для.повышения.производительности.поиска..В.этой.главе.
мы.сначала.создадим.структуру.для.CSP-задач,.которая.будет.решать.их.простым.

---

3.1. Построение структуры для задачи с ограничениями