@kquick

Правильно ли я понимаю, что приближенный алгоритм - это алгоритм, который всегда дает почти точное решение и его точность доказана, в то время как эвристический - это тоже приближенный, но его точность не доказана и в некоторых случаях могут получаться совершенно не приближенные результаты или даже не оптимальные? В то время как жадный выбирает локально оптимальные решения, и так же может давать точный, приближенный или даже самый не оптимальный результат?

0

iifat

Про жадный — приблизительно так, если я сам понимаю. Насчёт точного, приближённого и т.п. — не совсем. Насколько я знаю, есть задачи, решаемые жадным алгоритмом и не решаемые. Встречал термин только в отношении комбинаторики, там нет приближённых результатов. Либо даёт ответ, либо не даёт.
Эвристический, то, что встречал — неполный, что ли. Вот, например, задача о рюкзаке. Решается полным перебором, но можно ускорить некоторыми приёмами. Иногда условия выполняются и приём работает (ускоряет, в данном случае, перебор). Иногда условия не выполняются и приём неприменим.
Приближённый алгоритм — как термин не встречал. Есть алгоритмы, находящие приближение к результату, но приближёнными их не называют.

1

@Mysterious Light

iifat, я понял, о чём спрашивается в теме!

Под приближенными алгоритмами (решениями) понимаются такие алгоритмы для решения комбинаторных задач, которые возвращают вариант, отличающийся от оптимального не более, чем на определённую погрешность. Например, задачу коммивояжера можно заменить такой: «найти какой-либо гамильтонов цикл, длина которого отличается от длины оптимального гамильтонового цикла не более, чем на m%». Если для данной задачи найдётся алгоритм, который может решить задачу с указанной точностью за меншее время или с лучшей сложностью решения, чем любой алгоритм, находящий точное решение (т.е. m=0), то такой алгоритм будет приближенным.

Кстати, ты точно не встречал подобных алгоритмов?

1

iifat

Подобных — наверняка встречал. Один даже писал. Разбивал .zip-файл на дискеты, многотомных архивов тогда ещё не было. Вот названия «приближённые алгоритмы» в этом смысле не помню. Хотя и не возражаю — название вполне подходит

1

@kquick

Что тогда насчет эвристических и жадных? Чем они отличаются?

Эврестический:
- нет строгого обоснования (не доказан)
- приемлемые результаты в большинстве случаев (но может вобще самый плохой результат)

Жадный:
- нет строго обоснования (не доказан, а может быть и доказан в отличии от эвристического)
- приемлемые результаты в большинстве случаев (самый неоптимальный быть не может, поскольку принимаются локально оптимальные решения)

Правильно ?

Если быть более конкретным. Вот задача коммивояжера. Взято из википедии:
"Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение."

Тогда получается, что всякий жадный алгоритм - это частный случай эвристического?

Вот опять же. Взять тот же алгоритм муравья. Он же жадный? Но в связи с элементом случайности может выдать самый плохой результат (маловероятно, но все же). Получается, что второе утверждение про жадный не верно и он просто эвристический?

0

iifat

Не, вот тут куда-то не туда тебя понесло.
Жадный алгоритм — вполне себе доказан. Собственно, «жадный алгоритм» — это не конкретный алгортм, жадность это свойство алгоритма (принимать оптимальные локальные решения на каждом этапе). Некоторые задачи решаются жадным алгоритмом, некоторые нет. И то, и другое надо доказывать. Задача коммивояжера относится к нерешаемым этим алгоритмом. Как-то жестоко Вот, посмотри Википедию, например. Совсем уж недоказанный алгоритм и применять-то страшно. Нет полного доказательства. Ну вот, к примеру, задача о рюкзаке. Решаем полным перебором; а теперь добавим в начало проверку — соберём всё и посмотрим, не поместится ли в рюкзак. По-моему, этот приём заслуживает названия эвристического. Понятно, что если сработает, то здорово ускорит работу алгоритма; но вот оценить вероятность — безнадёга. Всё, как понимаю, предельно доказано, но вот оценить долю решаемых задач невозможно.

1

@Shamil1

Между жадным, эвристическим и приближенным алгоритмом нет взаимно однозначного соответствия.

Жадный алгоритм - это когда мы выбираем оптимальное решение на каждом шаге. В зависимости от задачи жадный алгоритм может находить лучшее решение или не находить.

Пример 1.
Есть N предметов разного веса и разной стоимости. Нужно выбрать n предметов так, чтобы суммарная стоимость была как можно больше.
Жадный алгоритм (на каждом шаге выбираем самый дорогой предмет) даёт оптимальное решение.

Пример 2.
Есть N предметов разного веса и разной стоимость. Нужно выбрать предметы общим весом не больше G так, чтобы суммарная стоимость была как можно больше.
Жадный алгоритм (на каждом шаге выбираем предмет с самой большой удельной - цена/вес - стоимостью) не даёт оптимальное решение. Более того, получаемое решение может во сколько угодно раз отличаться от оптимального. (Суммарный вес X, предметы: {вес 1, цена 1}, {вес X, цена X/2}. Жадным алгоритмом получаем суммарную цену 1.)

Приближенный алгоритм гарантирует, что найденное решение будет отличаться от оптимального не более, чем на сколько-то процентов. Приближенный алгоритм может быть жадным, а может не быть.

Эвристический алгоритм использует некую эвристическую функцию для оценки промежуточных результатов. Эвристический алгоритм может быть жадным, а может не быть. Эвристический алгоритм может давать точное решение, а может не давать. Эвристический алгоритм может давать приближенное решение заданной точностью, а может не давать.

Пример 3.
Найти кратчайший путь между двумя точками (на графе).
Жадный алгоритм (на каждом шаге выбираем узел, который ближе всего к цели).
Жадный эвристический алгоритм (на каждом шаге выбираем узел так, чтобы минимизировать эвристическую функцию).
Пусть, например, граф состоит из 4х точек S, A, B, F и 4х рёбер: [SA] = 1, [SB] = 100, [AF] = 5, [BF] = 1. Предложенный жадный алгоритм на первом шаге выбирет точку B, так как она ближе к цели. Итоговый путь 101.
Если в качестве эвристики взять пройденный путь + расстояние по прямой до цели, то жадный эвристический алгоритм выберет на первом шаге точку A, так как эвристика (1+5 < 100 + 1).
Можно использовать поиск в ширину и найти точное решение. При этом можно использовать описанную выше эвристическую функцию для задания приоритета на каждом шаге. У нас будет эвристический алгоритм, находящий точное решение, но работающий быстрее, чем просто поиск в ширину.

1