Локальный поиск
В этой главе рассматривается третья и последняя тема, относящаяся к этой области: разработка алгоритмов локального поиска.
Локальный поиск — чрезвычайно универсальный прием; этим термином описываются любые алгоритмы, которые последовательно «исследуют» пространство возможных решений, перемещаясь за один шаг от текущего решения к другому, «ближнему».
Общность и гибкость этого метода имеют свои преимущества: алгоритм на базе локального поиска можно без особых трудностей разработать почти для любой вычислительно сложной задачи; с другой стороны, часто бывает очень трудно сказать что-нибудь конкретное или доказуемое о качестве решений, находимых алгоритмом локального поиска, и, соответственно, очень сложно определить, хороший или плохой алгоритм локального поиска используется в каждом конкретном случае.
Полезная интуитивно понятная аналогия существует в принципе минимизации энергии в физике, поэтому мы сначала исследуем этот вопрос. Стиль изложения в этой главе несколько отличается от того, что был в книге до настоящего момента; мы представим некоторые алгоритмы, обсудим их на качественном уровне, но честно признаем, что мало что из этого мы можем доказать.
Впрочем, в отдельных случаях нам удастся доказать некоторые свойства алгоритмов локального поиска и связать их производительность с оптимальным решением.
Эта тема займет центральное место в завершающей части этой главы: мы начнем с рассмотрения случая (динамики нейронных сетей Хопфилда), в котором локальный поиск предоставляет естественную точку зрения на поведение сложного процесса; затем мы сосредоточим внимание на NP-сложных задачах, для которых локальный поиск помогает разработать эффективные алгоритмы с доказуемыми гарантиями аппроксимации.
Глава завершается обсуждением других типов локального поиска: динамикой наилучших ответов и равновесиями Нэша, естественным образом встречающимися при изучении систем с множеством взаимодействующих агентов.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу