Жадный Поиск от точки A до точки B на графике

Question

Вопрос в моем учебнике попросил меня рассчитать и найти маршрут из Мехадии в Бухарест через 1) Жадный поиск и 2) Поиск по единой стоимости.

* Теперь я могу полностью проиллюстрировать и решить маршрут путем единообразного поиска стоимости, но мой жадный поиск выглядит очень похожим. Любые идеи о том, как я могу рассчитать маршрут через «жадный» поиск?

UPDATE Я применил грязный жадный algotithm и получил другой маршрут против кратчайшего пути от моей единой цены.

Это маршрут, выданный моим жадным алгоритмом. Алгоритм просто продолжает проверять и выбирать наименьшее локальное значение. Мой НОВЫЙ ВОПРОС для любого: Является ли этот маршрут приемлемым для вывода моего жадного алгоритма? То есть Могло ли мое решение даже считаться законным?

маршрута на основе моего нового алгоритма:

Mehadia -> Лугож -> Тимишоара -> Arad -> Zerind -> Орадя -> Сибиу -> Рымнику Вылча -> Питешти -> Бухарест

Answer 1

When вы используете Поиск по системе Uniform Cost Вы вычисляете кратчайшие пути от Mehadia до всех узлов, поэтому вы можете быть уверены, что путь Mehadia-Bucharest будет оптимальным (этот алгоритм является полным и оптимальным). Однако, если вы используете Жадный алгоритм поиска, он выберет локально наилучшую опцию , отбрасывая остальные для каждого узла. Этот алгоритм не является ни полным, ни оптимальным. Чтобы ответить на ваш вопрос «да», ваше решение считается жадным.

Надеюсь, это поможет.