#graph-algorithm #a-star
#граф-алгоритм #a-star
Вопрос:
мы доказали в классе, что если A * в поиске по дереву является оптимальным, то h (n) является допустимым (допустимая эвристика). Если использование A * в поиске по графу находит оптимальное решение, то h (n) является согласованным. Мы доказали свойства допустимого и согласованного, если предположить, что A * может найти оптимальное решение. Это указывает на то, что согласованность / допустимость являются необходимыми условиями для оптимальности в поиске по графу / дереву.
Однако я не слишком уверен, как доказать, что они также являются достаточными условиями. Я пытался разобраться в этом, но все еще не мог найти хорошего способа доказать это. Например, я не слишком уверен, как доказать, что допустимость может привести к оптимальности при поиске по дереву с использованием A *? И аналогично, как доказать, что согласованность может привести к оптимальности при поиске по графу с использованием A *? Заранее благодарю вас!
Я впервые задаю вопрос в StackOverflow, извините, если я неправильно формулирую свой вопрос. : ) Заранее благодарю вас!
Комментарии:
1. Почему доказательство поиска по графу не применимо к поиску по дереву (поскольку дерево — это особый вид графа)?
2. Привет, спасибо за ваш комментарий! Я доказал, что допустимые и согласованные являются необходимыми условиями для поиска по дереву / графу. Однако я смущен тем, как мы можем доказать, что они являются достаточными условиями, которые приводят к оптимальности.
3. «мы доказали в классе, что если h (n) допустимо, то использование A * в поиске по дереву является оптимальным» — «Я не слишком уверен, как доказать, что допустимость может привести к оптимальности в поиске по дереву с использованием A *» — ???
4. @BlueRaja-DannyPflughoeft Ооо, извините. Я допустил неосторожную ошибку. Я только что исправил вопрос сейчас. Спасибо, что указали на это. : )
Ответ №1:
Это указывает на то, что согласованность / допустимость являются необходимыми условиями для оптимальности в поиске по графу / дереву.
Нет, это подразумевает, что они являются достаточными условиями. На самом деле обратное неверно — можно найти случаи, когда данная недопустимая эвристика возвращает оптимальный результат для конкретного графика (простой контрпример: дерево с только одним путем вернет оптимальный путь для любой эвристики). Таким образом, они не являются необходимыми условиями.
В качестве примечания «согласованный» подразумевает «допустимый», а деревья являются типом графика, поэтому достаточно доказать случай «допустимый график», и все четыре случая (допустимый / непротиворечивый, дерево / граф) сразу подразумеваются.
Комментарии:
1. Спасибо за ваш ответ! Я думаю, что действительно, они не должны быть необходимыми условиями в соответствии с вашим контрпримером, упомянутым выше. Но мне все еще немного любопытно, и не могли бы вы, пожалуйста, дать мне несколько советов о том, как доказать, что они являются достаточными условиями?
2. Привет, чтобы добавить, я обнаружил небольшой возможный недостаток в контрпримере, упомянутом в ответе. Я думаю, что оптимальность алгоритмов означает, что алгоритм всегда может найти оптимальное решение на любых графах. Однако в упомянутом выше контрпримере он определяет только один тип графа, где неоптимальные алгоритмы, такие как BFS или DFS, также могут найти оптимальный путь в дереве с одним путем, упомянутом выше. Таким образом, я думаю, что это может быть не очень подходящим контрпримером здесь.
3. @Leonard: Да, мы говорим обо всех графах. Однако, чтобы опровергнуть утверждение обо всех графах, вам нужно найти только один контрпример. Утверждение здесь взято из вашего вопроса, «Если использование A * в Graph-Search находит оптимальное решение, то h (n) является согласованным» , что является ложным. Тот факт, что BFS и DFS находят один и тот же путь, не имеет значения.