TSP (жадный nearest‑neighbor). Контрпример (можно сделать отношение сколь угодно большим). Пусть города: центр $C$ и листья $L_1,\dots ,L_k$. Расстояния задаём
$$d(C,L_i)=1,d(L_i,L_j)=M(i\ne j),$$ где $M\gg 1$. Начинаем в $C$. Алгоритм «ближайший сосед» из $C$ идёт в какой‑то $L_i$ (стоимость $1$), из $L_i$ ближайший — обратно $C$ (стоимость $1$), затем в следующий лист и т.д. Получаем тур стоимостью примерно $2k$. Но можно сконструировать оптимальный тур, который посещает листья в другом порядке и делает один длинный переход вместо многих (в не‑метрическом варианте можно сделать оптимум порядка $M+k$ малым по отношению к жадному, или наоборот — подобрать параметры, чтобы жадный был хуже в $O(M)$ раз). Это показывает, что локально минимальный выбор («самый близкий город сейчас») может привести к обязательному очень дорогому ребру позже — жадность не учитывает глобальную структуру.
0/1‑рюкзак (жадный по плотности value/weight). Классический простой контрпример:
вместимость $W=10$. Товары:
- $A$: вес $6$, ценность $31$ (плотность $31/6\approx 5.167$);
- $B$, $C$: по весу $5$, ценности $25$ (плотность $25/5=5$).
Жадный по плотности возьмёт сначала $A$ (самая большая плотность), после этого остаётся место $4$ — ни $B$, ни $C$ уже не поместятся, итоговая ценность $31$. Но оптимум — взять товары $B$ и $C$ (вместимость $5+5=10$), ценность $25+25=50$. Отношение $31/50$ существенно хуже. Можно варьировать числа, чтобы разрыв был ещё больше.
Почему требуется ДП или другие методы:
- Жадные правила принимают локально оптимальное решение (например, наибольшая плотность или ближайший сосед), но задачи TSP и 0/1‑рюкзак имеют «глобальные» ограничения: выбор сейчас влияет на доступность хороших вариантов позже.
- Динамическое программирование эксплуатирует принцип оптимальности Беллмана: оптимальный ответ для всей задачи строится из оптимальных ответов для подзадач (пересекающиеся подзадачи + оптимальная подструктура). Для рюкзака ДП по весу/предметам даёт точный оптимум за псевдополиномиальное время $O(nW)$. Для TSP точный алгоритм (Held–Karp) использует ДП по подмножествам и вершине за $O(n^2{2}^n)$.
- Для приближённых алгоритмов применяют: для TSP — специальные эвристики и приближённые алгоритмы (например, для метрического TSP есть 2‑приближение через минимальное остовное дерево и обход), для рюкзака — FPTAS (сжатие ценностей) даёт приближение $1-\epsilon$ за полиномиальное время в $n$ и $1/\epsilon$.
Вывод: жадный подход прост и часто эффективен, но для задач с глобальными ограничениями (TSP, 0/1‑рюкзак) он может давать существенно худшие решения; для гарантированно хорошего (или точного) результата нужны ДП или более сложные алгоритмы/эвристики с доказанными оценками.