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

135
4.6. РЕАЛЬНЫЕ ПРИЛОЖЕНИЯ
Очень.многое.в.нашем.мире.можно.представить.в.виде.графов..В.этой.главе.вы.
увидели,.как.эффективны.они.при.работе.с.транспортными.сетями..С.подобными.
важными.проблемами.оптимизации.сталкиваются.и.многие.другие.виды.сетей:.
телефонные,.компьютерные,.инженерные.(электричество,.водопровод.и.т..п.)..
Графовые.алгоритмы.необходимы.для.эффективного.решения.задач.в.области.
телекоммуникаций,.судоходства,.транспорта.и.коммунального.хозяйства.
Предприятиям.розничной.торговли.приходится.решать.сложные.задачи.дис-
трибуции..Магазины.и.склады.можно.рассматривать.как.вершины,.а.расстояния.
между.ними.—.как.ребра.графов,.к.которым.применяются.все.те.же.алгоритмы..
Сам.интернет.—.это.гигантский.граф,.в.котором.каждое.подключенное.устройство.
представляет.собой.вершину,.а.каждое.проводное.или.беспроводное.соединение.—.
ребро..Минимальное.связующее.дерево.и.поиск.кратчайшего.пути.помогут.узнать,.
экономит.ли.компания.топливо.или.провода.для.соединений,.—.эти.алгоритмы.
полезны.не.только.для.игр..Некоторые.из.наиболее.известных.мировых.брендов.
стали.успешными.благодаря.оптимизации.с.использованием.графовых.задач:.
например,.компания.Walmart.построила.эффективную.дистрибьюторскую.сеть,.
Google.проиндексировала.интернет.(гигантский.граф),.а.FedEx.нашла.правильный.
набор.концентраторов.для.подключения.к.адресам.по.всему.миру.
Одни.из.самых.очевидных.приложений.графовых.алгоритмов.—.это.социальные.
сети.и.картографические.приложения..В.социальной.сети.люди.играют.роль.
вершин,.а.связи.между.ними.(такие,.как.дружба.в.Facebook).—.ребер..Один.из.
известнейших.инструментов.разработчика.Facebook.так.и.называется.—.Graph.
API.(
https://developers.facebook.com/docs/graph-api
)..В.картографических.приложе-
ниях,.таких.как.Apple.Maps.и.Google.Maps,.графовые.алгоритмы.задействуются.
для.указания.направлений.и.расчета.времени.в.пути.
Несколько.популярных.видеоигр.также.явно.используют.графовые.алгоритмы..
MiniMetro.и.Ticket.to.Ride.—.лишь.два.примера.игр,.моделирующих.задачи,.ко-
торые.мы.решали.в.этой.главе.
4.7. УПРАЖНЕНИЯ
1.. Добавьте.в.графовую.структуру.возможность.удаления.ребер.и.вершин.
2.. Добавьте.в.графовую.структуру.поддержку.направленных.графов.(диграфов).
3.. Применив.графовую.структуру,.описанную.в.этой.главе,.докажите.или.опро-
вергните.классическую.задачу.о.кёнигсбергских.мостах,.описанную.в.«Вики-
педии»:.
ru.wikipedia.org/wiki/Seven_Bridges_of_Königsberg
.

---

5
Генетические алгоритмы
Генетические.алгоритмы.не.относятся.к.используемым.для.решения.повседневных.
задач.программирования..Они.нужны.тогда,.когда.традиционных.алгоритмиче-
ских.подходов.недостаточно.для.решения.проблемы.в.разумные.сроки..Другими.
словами,.генетические.алгоритмы.обычно.приберегают.для.сложных.задач,.не.
имеющих.простых.решений..Если.вы.хотите.понять,.что.представляют.собой.
некоторые.из.этих.сложных.проблем,.не.стесняйтесь.обратиться.к.разделу.5.7,.
прежде.чем.продолжить.чтение.книги..Вот.только.один.интересный.пример:.
построение.соединений.белка.и.лиганда.и.разработка.лекарств..Специалисты.
в.области.вычислительной.биологии.разрабатывают.молекулы,.которые.будут.
связываться.с.рецепторами,.чтобы.доставить.лекарства..Для.конструирования.
конкретной.молекулы.может.не.существовать.очевидного.алгоритма,.но.как.вы.
увидите,.иногда.генетические.алгоритмы.позволяют.дать.ответ,.не.имея.четкого.
определения.цели.поставленной.задачи.