Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, геометрическая задача коммивояжёра, метрическая задача коммивояжёра, симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Эври́стика — научная область, изучающая специфику созидательной деятельности.
Игра в 15, пятнашки, такен — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов, соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке, добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.
«Разделяй и властвуй» в информатике — схема разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Дерево принятия решений — средство поддержки принятия решений, использующееся в машинном обучении, анализе данных и статистике. Структура дерева представляет собой «листья» и «ветки». На рёбрах («ветках») дерева решения записаны признаки, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — признаки, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение.
Поиск A* — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой.
Эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи. Позволяет ускорить решение задачи в тех случаях, когда точное решение не может быть найдено.
Поиск подстроки в строке — одна из простейших задач поиска информации. Применяется в виде встроенной функции в текстовых редакторах, СУБД, поисковых машинах, языках программирования и т. п.
Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере.
Трассиро́вка печатных плат — один из этапов проектирования радиоэлектронной аппаратуры (РЭА), заключающийся в определении мест расположения проводников на печатной плате вручную или с использованием одной из САПР, предназначенной для проектирования печатных плат.
DPLL — полный алгоритм поиска с возвратом для решения задачи CNF-SAT — определения выполнимости булевых формул, записанных в конъюнктивной нормальной форме.
Роевой интеллект (РИ) описывает коллективное поведение децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. Термин был введён Херардо Бени и Ван Цзином в 1989 году, в контексте системы клеточных роботов. Однако ранее идея подробно рассмотрена Станиславом Лемом в романе «Непобедимый» (1964) и эссе «Системы оружия двадцать первого века, или Эволюция вверх ногами» (1983).
Поиск «лучший — первый» — алгоритм поиска, исследующий граф путём расширения наиболее перспективных узлов, выбираемых в соответствии с указанным правилом.
Gerasim@Home — российский проект добровольных распределенных вычислений на платформе BOINC. Проект стартовал в тестовом режиме в феврале 2008 года. Отличительной особенностью серверной части проекта, разработанной С. Ю. Валяевым, является использование операционной системы Windows Server 2008 и связки Microsoft SQL Server с ASP.NET, в то время как стандартный набор приложений от разработчиков BOINC требует использования операционной системы Linux или Unix. По состоянию на 23 июля 2015 года в проекте приняли участие 1999 пользователей из 62 стран, обеспечивая производительность 1—5 терафлопс. Участвовать в проекте может любой желающий, обладающий компьютером с выходом в Интернет, установив на него программу BOINC Manager.
Информи́рованный по́иск — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами.
По́иск в простра́нстве состоя́ний — группа математических методов, предназначенных для решения задач искусственного интеллекта.
Поиск с запретами или табу-поиск является мета-алгоритмом поиска, использующим методы локального поиска, используемые для математической оптимизации. Алгоритм создал Фред У. Гловер в 1986 и формализовал в 1989
Эври́стика может означать:
- Эвристика — отрасль знания, научная область, изучающая специфику творческой деятельности.
В информатике Лучевой поиск — это эвристический алгоритм поиска, который исследует граф, расширяя перспективные узлы в ограниченном наборе. Лучевой поиск — это оптимизация поиска по первому наилучшему совпадению, которая снижает требования к памяти. Поиск по первому наилучшему совпадению — это поиск по графу, который упорядочивает все частные решения (состояния) в соответствии с некоторой эвристикой. Но при лучевом поиске в качестве кандидатов сохраняется только заранее определённое количество лучших частичных решений. Таким образом, это жадный алгоритм.
Алгоритм поиска D* — это любой из трёх связанных алгоритмов инкрементного поиска:
- Оригинальный алгоритм D* Энтони Стенца — это информированный алгоритм инкрементного поиска.
- Сфокусированный D* — это алгоритм инкрементного эвристического поиска, разработанный Энтони Стенцем, который сочетает в себе идеи A* и оригинального D*. Сфокусированный D* возник в результате дальнейшего развития оригинального D*.
- Облегчённый D* — это алгоритм инкрементального эвристического поиска, созданный Свеном Кёнигом и Максимом Лихачёвым, который основан на LPA*, алгоритме инкрементального эвристического поиска, объединяющем идеи алгоритма поиска A* и динамического SWSF-FP.