Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Гриди-алгоритмы - часть 2


Так что мы получаем длину кратчайшего пути как минимум из длин кратчайшего пути, который не содержит w, и кратчайшего пути, который содержит w в качестве первой внутренней вершины.

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

Работа с задачами большой сложности требует глубокого анализа постановки задачи. Путем упрощения постановки задачи, например через ограничения на область значений параметров, в некоторых случаях можно сделать применимыми менее сложные алгоритмы. Важно также, сколь многочисленны на самом деле входные данные для рассматриваемой задачи. При небольшой размерности могут непосредственно решаться (англ. brute force) даже NP-полные проблемы.




- Начало -  - Назад -  - Вперед -



Книжный магазин