Алгоритм А* на графах

@greg177 · Регистрация: 14.09.2014

Студворк — интернет-сервис помощи студентам

Стоит задача разработать функцию поиска пути в неориентированном графе методом А*. Проблема: как на графе считается эвристическая функция h(n)? Всё, что мы имеем: названия узлов и веса дуг между ними. И я не могу понять, как применить какую бы то ни было эвристику к вершинам(например, Манхэттенское расстояние). Подскажите.

@Shamil1 · 13.10.2016, 15:59

Сообщение от greg177

Стоит задача разработать функцию поиска пути в неориентированном графе методом А*.

Чтобы использовать стратегию информированного поиска, нужно обладать хоть какой-нибудь информацией. Иначе остаётся только неинформированный поиск - полный перебор.

Сообщение от greg177

Проблема: как на графе считается эвристическая функция h(n)?

h(n) => 0

@greg177 · 13.10.2016, 16:25 **[ТС]**

Сообщение от Shamil1

Чтобы использовать стратегию информированного поиска, нужно обладать хоть какой-нибудь информацией. Иначе остаётся только неинформированный поиск - полный перебор

Это вся информация. За исключением того, что на вход функци мы подаем граф, стартовую вершину и вершину, в которую хотим попасть.

Сообщение от Shamil1

h(n) => 0

Вот у нас есть этап, когда мы берем все соседние вершины к текущей и находим среди них вершину с наименьшим f(n). Но почему-то не понимаю, как найти для каждой вершины h(n).

@Shamil1 · 13.10.2016, 17:42

Сообщение от greg177

Но почему-то не понимаю, как найти для каждой вершины h(n).

Я же написал: для всех вершин h(n) равно нулю.

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

oldnewyear · 14.10.2016, 00:07

Сообщение от Shamil1

Чтобы использовать стратегию информированного поиска, нужно обладать хоть какой-нибудь информацией. Иначе остаётся только неинформированный поиск - полный перебор.

В данном случае имеются веса дуг, этих данных достаточно для информированного поиска. Для А* этих данных недостаточно, А* f(n)=g(n) + h(n) = g(n) + 0 = g(n), получаем информированный uniform cost search

@Shamil1 · 14.10.2016, 09:19

Сообщение от oldnewyear

В данном случае имеются веса дуг, этих данных достаточно для информированного поиска.

Эти данные относятся к условию задачи и нужны только для вычисления стоимости пути. Для информированного поиска нужна какая-то дополнительная информация о состояниях.

Сообщение от oldnewyear

получаем информированный uniform cost search

Поиск по критерию стоимости (метод равных цен, uniform-cost search, UCS) - один из вариантов неинформированного поиска.

Например,
Вам нужно найти носки в шкафу. Всего в шкафу 10 ящиков, и в худшем случае Вам придётся заглянуть в каждый из них. Информация о том, что к одному ящику придётся тянуться, а к другому наклоняться, никак не поможет Вам уменьшить количество открытых ящиков. Вот если бы у Вас была какая-нибудь информация о состояних типа "носки и полотенца не могут быть в соседних ящиках", тогда можно было бы подумать, как оптимизировать поиск.

Подробнее читайте тут:
Неинформированный метод поиска

oldnewyear · 14.10.2016, 09:36

Сообщение от Shamil1

Эти данные относятся к условию задачи и нужны только для вычисления стоимости пути. Для информированного поиска нужна какая-то дополнительная информация о состояниях.

Поиск по критерию стоимости (метод равных цен, uniform-cost search, UCS) - один из вариантов неинформированного поиска.

Например,
Вам нужно найти носки в шкафу. Всего в шкафу 10 ящиков, и в худшем случае Вам придётся заглянуть в каждый из них. Информация о том, что к одному ящику придётся тянуться, а к другому наклоняться, никак не поможет Вам уменьшить количество открытых ящиков. Вот если бы у Вас была какая-нибудь информация о состояних типа "носки и полотенца не могут быть в соседних ящиках", тогда можно было бы подумать, как оптимизировать поиск.

Подробнее читайте тут:
Неинформированный метод поиска

Да, вы правы

Добавлено через 1 минуту
Тем не менее полный перебор не нужен в данном случае

@Shamil1 · 14.10.2016, 13:49

Обход в ширину.
При выполнении некоторого условия (достигли пункта назначения) поиск можно остановить. (Нашли носки уже во втором ящике - остальные можно не проверять). Но в худшем случае (конечная вершина дальше всех от начальной) мы переберём все вершины.

oldnewyear · 14.10.2016, 14:10

Сообщение от Shamil1

Обход в ширину.
При выполнении некоторого условия (достигли пункта назначения) поиск можно остановить. (Нашли носки уже во втором ящике - остальные можно не проверять). Но в худшем случае (конечная вершина дальше всех от начальной) мы переберём все вершины.

Худший случай - все дуги имеют одинаковый вес. Тогда да. А так нет

@Shamil1 · 14.10.2016, 15:38

От весов дуг ничего не зависит (ну, кроме результата).
Возьмите (представьте) какую-нибудь карту. Пусть города будут вершинами, а расстояния между ними будут весами дуг. Если мы возьмём один город в центре, а другой на самом дальнем краю, и будем искать путь от одного до другого методом UCS, то мы посетим все города на карте. Если же мы будем использовать информированный поиск (с эвристикой по расстоянию), то мы посетим только те города, которые лежат примерно на прямой между ними. С учётом того, что между всеми соседними городами обычно есть дороги, если это не какая-нибудь горная или островная местность, то велика вероятность, что при поиске мы посетим только те города, которые лежат на кратчайшем пути.

oldnewyear · 14.10.2016, 16:36

Сообщение от Shamil1

От весов дуг ничего не зависит (ну, кроме результата).
Возьмите (представьте) какую-нибудь карту. Пусть города будут вершинами, а расстояния между ними будут весами дуг. Если мы возьмём один город в центре, а другой на самом дальнем краю, и будем искать путь от одного до другого методом UCS, то мы посетим все города на карте.

Только в том случае, если расстояния между соседними городами одинаковые

@Shamil1 · 14.10.2016, 18:39

Сообщение от oldnewyear

Только в том случае, если расстояния между соседними городами одинаковые

Проверьте. Откройте карту и в уме посчитайте, в каком порядке алгоритм будет посещать города.

@ValeryLaptev · 16.10.2016, 09:25

oldnewyear, а алгоритм Дейкстры? Поиск пути между двумя заданными вершинами на взвешенном графе - классика!
Без всякой эвристики вполне себе ищет кратчайший путь на графе со взвешенными ребрами.
И прекращает работу при достижении заданной вершины.
В худшем случае тоже может перебрать все вершины...

))

oldnewyear · 16.10.2016, 09:42

Сообщение от ValeryLaptev

oldnewyear, а алгоритм Дейкстры?

Это, насколько я понимаю, то же самое, что и uniform cost search.

@ValeryLaptev · 16.10.2016, 09:44

oldnewyear, я такого названия не знаю. А вот алгоритм Дейкстры описан во всех учебниках по графам. И называется везде именно алгоритмом Дейкстры.

oldnewyear · 16.10.2016, 09:50

Сообщение от ValeryLaptev

oldnewyear, я такого названия не знаю. А вот алгоритм Дейкстры описан во всех учебниках по графам. И называется везде именно алгоритмом Дейкстры.

Я к изучению графов только приступил. В учебниках по ИИ рассматривается частный случай алгоритма Дейкстры для поиска пути, я оттуда это название взял

@ValeryLaptev · 16.10.2016, 09:55

Понятно. Тогда еще порекомендую изучить динамическое программирование - часто на графах применяется для поиска оптимального в некотором смысле пути. Еще - метод ветвей и границ - для сокращения полного перебора.
В ИИ эти хорошо известные методы могут иметь свои названия. Особенно, если переводчик неграмотный...

@Shamil1 · 16.10.2016, 16:33

Сообщение от oldnewyear

Это, насколько я понимаю, то же самое, что и uniform cost search.

Поиск по критерию стоимости логически эквивалентен алгоритму Дейкстры. Только в алгоритме Дейкстры все узлы добавляются в очередь при инициализации, а в алгоритме поиска по критерию стоимости узлы добавляются «на лету» во время поиска. Поэтому алгоритм Дейкстры применим только к явно заданным графам, в то время как алгоритм UCS может быть применён как к явным, так и к неявным графам.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@greg177 0 / 0 / 0 Регистрация: 14.09.2014 Сообщений: 32

	Алгоритм А* на графах 13.10.2016, 12:48. Показов 1766. Ответов 17 Метки нет (Все метки) Стоит задача разработать функцию поиска пути в неориентированном графе методом А*. Проблема: как на графе считается эвристическая функция h(n)? Всё, что мы имеем: названия узлов и веса дуг между ними. И я не могу понять, как применить какую бы то ни было эвристику к вершинам(например, Манхэттенское расстояние). Подскажите. 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	14.10.2016, 13:49
	Обход в ширину. При выполнении некоторого условия (достигли пункта назначения) поиск можно остановить. (Нашли носки уже во втором ящике - остальные можно не проверять). Но в худшем случае (конечная вершина дальше всех от начальной) мы переберём все вершины. 1

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	14.10.2016, 15:38
	От весов дуг ничего не зависит (ну, кроме результата). Возьмите (представьте) какую-нибудь карту. Пусть города будут вершинами, а расстояния между ними будут весами дуг. Если мы возьмём один город в центре, а другой на самом дальнем краю, и будем искать путь от одного до другого методом UCS, то мы посетим все города на карте. Если же мы будем использовать информированный поиск (с эвристикой по расстоянию), то мы посетим только те города, которые лежат примерно на прямой между ними. С учётом того, что между всеми соседними городами обычно есть дороги, если это не какая-нибудь горная или островная местность, то велика вероятность, что при поиске мы посетим только те города, которые лежат на кратчайшем пути. 0

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	16.10.2016, 09:25
	oldnewyear, а алгоритм Дейкстры? Поиск пути между двумя заданными вершинами на взвешенном графе - классика! Без всякой эвристики вполне себе ищет кратчайший путь на графе со взвешенными ребрами. И прекращает работу при достижении заданной вершины. В худшем случае тоже может перебрать все вершины... )) 0

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	16.10.2016, 09:44
	oldnewyear, я такого названия не знаю. А вот алгоритм Дейкстры описан во всех учебниках по графам. И называется везде именно алгоритмом Дейкстры. 0

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	16.10.2016, 09:55
	Понятно. Тогда еще порекомендую изучить динамическое программирование - часто на графах применяется для поиска оптимального в некотором смысле пути. Еще - метод ветвей и границ - для сокращения полного перебора. В ИИ эти хорошо известные методы могут иметь свои названия. Особенно, если переводчик неграмотный... 1