Определение. Эвристические алгоритмы – алгоритмы, которые быстро находят «подходящее» решение на основе анализа небольшого числа случаев (но они не самые оптимальные).
Примерами таких случаев служат жадный алгоритм (они оптимальны на каждом шаге, действуют используя в каждый момент только часть исходных данных, принимая на этой части только лучшее оптимальное решение), алгоритмы, построенные по системе разделяй и властвуй. Первый подход был использован Деикстром и Примом, он основан на рассмотрение вершин графа. Второй подход Крускла он делает упор на рёбра графа.
Первый подход. Рассматриваем с пустого множества ребер и добавляем к нему рёбра в порядке возрастания их весов, пока не получим путь. При этом должны выполняться два условия: ребро принимается, если оно не образует цикла с уже имеющимися рёбрами, и не приводит к появлению вершин со степенью инцидентности 3 и более.
У нас пустое множество ребер, берем ребро FD=1 (меньший вес) AB+2, BE=3? AC=4, AF=5(не берем, т.к. степень 3), CF=6, DG=6,GE=7(замыкаем).
Дано города и расстояния между ними (рис 1). Построим дерево по нашему алгоритму (рис2-гамильтонов цикл) сумма=29-оптимально, достаточно недорогой по времени, но не достаточно лучший.
Мы построили путь, удовлетворяющий всем требованиям жадного алгоритма, однако мы не уверены, что он оптимален, он просто хороший, то есть весьма близкий к оптимальному.
Задача построения телефонной сети
Алгоритм Крускала (с ребрами графа)
Дана плоская страна в ней N городов. Нужно соединить все города так, чтобы общая длина телефонной линии была минимальной. Уточнение: города пренебрежительно малы; подразумевается транзитивность связей (то есть если i связан с j, а j с k, то i и k тоже связаны); нет циклов; если i и j соединены то j и i соединены.
Дан полный взвешенный граф. Построить минимальное остовое дерево.
G1(V,E)-граф, где V- множество вершин, E-множество ребер.
Построение начинается с графа Gi(V, пустое мн-во) пустое множетво ребер состоит из n вершин. Берем только множество вершин связной компонентой будут только вершины. По возрастанию весов добавляем ребра. Главное, чтобы не было циклов.
Здесь степень инцидентности может быть любой и граф не должен быть замкнут.
Назвать его самым оптимальным решением нельзя. Пропишем алгоритм в общем случае: взяли n вершин. Каждая вершина связана лишь с собой. В процессе выполнения имеем набор связных компонент постепенно формируя остовое дерево: при построении связи(ребра) постепенно возрастающие по весу компоненты поочередно проверяются. Если 2 вершины связ. ребром из разных компонент, то его берут, нет отбрасывают. Когда все вершины будут принадлежать одной компоненте, то построение заканчивается.
Остовым деревом называется связный суграф, не имеющий циклов.
Все вершины и часть инцидентных им ребер наз-ся суграфом.
Часть вершин и все инцидентные им ребра наз. подграфом.
Дерево-граф без циклов.
След. задача, кот-ая будет решаться жадным алгоритмом и относящ к алгоритмам на графах:
Задача нахождения кротчайшего расстояния между двумя городами
Эта задача по другому называется – раскраска графа. Возьмём жадный алгоритм:
Во-первых, выбираем произвольную не закрашенную вершину и назначаем ей цвет. Во-вторых, просматриваем список не закрашенных вершин и для каждой из них определяем соединена ли она с уже закрашенной, если не присоединена, то к ней применяем тот же цвет. Когда первый цвет уже нельзя использовать, то выбираем пустую вершину и берём другой цвет.
отображает жадный алгоритм раскраски графа.
Жадный, т.к. каждый цвет применяется к максимально большему числу вершин без возможного пропуска или перекраски
Недостаток такого алгоритма (жадного), в том, что на первый цвет он заливает большинство вершин и это может привести к использованию большего числа цветов.
Построение близкое к оптимальной раскраске столь же сложно, как и решить задачу раскраски графа. Число красок, даваемое полиномиальным алгоритмом более чем в два раза превышает оптимальное решение. Кроме того доказано, что если существует полиномиальный алгоритм, закрашивающий вершины графа числом красок превышающая оптимальное число их не более чем в 2 раза, то существует оптимальный полиномиальный алгоритм. А это значит, что все задачи P=NP.
Существует P (полиномиальный) алгоритм раскраски планарных графов.
Задача раскладки по ящикам
Имеются ящики единичного объёма и набор объектов различных размеров. Задача состоит в том, что нужно для раскладки всех вещей использовать наименьшее число ящиков (аналогичные задачи: запись информации на диск, распределение грузов на корабле, раскрой материалов).
Жадный алгоритм: упаковываем в первый ящик первую вещь, потом ищем первую подходящую вещь, которая ещё поместится в ящик, и т.д. Потом переходим к следующему ящику.
На рис 5 изображена реализация жадного алгоритма. Этот алгоритм можно достаточно хорошо модернизировать. Модифицированный подход состоит только в том, что перед раскладкой по ящикам мы упорядочиваем раскладываемые элементы по убыванию.
Также существуют алгоритмы(если спросят):
Декомпозиции(или разделяй и властвуй)-предполагает такую декомпозицию задачи размером n на более мелкие задачи, что на основе этих более мелких задач можно легко получить решение задачи (в частности к этому методу можно отнести рекурсию-Ханнойская Башня).
Динамическое программирование - часто не удается разбить задачу на подзадачи, объединение решений которых позволит получить решение исходной задачи. Ричард Беллман ввел понятие динамического программирования для хар-ки алгоритмов, действующих в зависимости отизменения ситуации. Ключевым явл. То, что он использует полиномиальн. по времени алгоритм вместо экспотенциального.в динамическом программировании процесс решения задачи, когда на каждом шаге выбирается 1 решение из допустимых, которое оптимизирует данную целевую функцию. (задача распределения оптимальности ресурсов)
Вероятностные алгоритмы (монте-карло, лас-вегас)
Алгоритмы, базирующиеся на поведении биологических объектов(генетические алгоритмы, муравьиные алгоритмы, нейросети)
