Являются ли Алгоритм Дейкстры и Поиск в ширину жадными алгоритмами? Если да, то почему?
-
А что такое жадные алгоритмы? Применяется ли принцип выбора, свойственный жадным алгоритмам, при реализации Дейкстры и BFS?– MBo18 июн 2020 в 15:18
-
Жадный алгоритм - алгоритм, который каждый шаг ищет самый оптимальный вариант (определение не дословное). Принцип применяется. С алгоритмом Дейкстры все понятно. Там выбирается сосед с наименьшим весом. Но как проявляется оптимальность в каждом шаге в BFS? (Поправьте, если я неправ)– winter_king418 июн 2020 в 17:25
1 ответ
Жадный выбирает вариант, являющийся оптимальным в данный момент (локальная оптимальность). Для определённых систем такой выбор приводит к глобальному оптимуму.
Да, Дейкстра - жадный алгоритм.
А вот поиск в ширину ничего не выбирает, а просто перебирает все доступные рёбра, и является, таким образом, разновидностью brute-force search (неинформированный поиск)