Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
greg177
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 32
1

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

13.10.2016, 12:48. Просмотров 507. Ответов 17
Метки нет (Все метки)

Стоит задача разработать функцию поиска пути в неориентированном графе методом А*. Проблема: как на графе считается эвристическая функция h(n)? Всё, что мы имеем: названия узлов и веса дуг между ними. И я не могу понять, как применить какую бы то ни было эвристику к вершинам(например, Манхэттенское расстояние). Подскажите.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.10.2016, 12:48
Ответы с готовыми решениями:

Алгоритм на графах
Доброго времени суток, у кого нибудь может быть завалялся алгоритм поиска в глубину на графах, а то...

Алгоритм Прима не работает на неполных графах
Доброго времени суток! Помогите, пожалуйста, с реализацией алгоритма Прима (алгоритм построения...

Алгоритм на графах. Можно ли опосредованно перезнакомить всех между собой
На олимпиаду прибыли N человек. Некоторые из них знакомы между собой. Круг знакомств задан матрицей...

ГА на графах
Здравствуйте. Не могу разобраться как решать эту задачу. Используйте генетический алгоритм (для...

Поиск в графах
Дан массив X*X - матрица смежности для графа с X вершинами, даны точки IZ (точка из которой...

17
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
13.10.2016, 15:59 2
Цитата Сообщение от greg177 Посмотреть сообщение
Стоит задача разработать функцию поиска пути в неориентированном графе методом А*.
Чтобы использовать стратегию информированного поиска, нужно обладать хоть какой-нибудь информацией. Иначе остаётся только неинформированный поиск - полный перебор.

Цитата Сообщение от greg177 Посмотреть сообщение
Проблема: как на графе считается эвристическая функция h(n)?
h(n) => 0
0
greg177
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 32
13.10.2016, 16:25  [ТС] 3
Цитата Сообщение от Shamil1 Посмотреть сообщение
Чтобы использовать стратегию информированного поиска, нужно обладать хоть какой-нибудь информацией. Иначе остаётся только неинформированный поиск - полный перебор
Это вся информация. За исключением того, что на вход функци мы подаем граф, стартовую вершину и вершину, в которую хотим попасть.
Цитата Сообщение от Shamil1 Посмотреть сообщение
h(n) => 0
Вот у нас есть этап, когда мы берем все соседние вершины к текущей и находим среди них вершину с наименьшим f(n). Но почему-то не понимаю, как найти для каждой вершины h(n).
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
13.10.2016, 17:42 4
Цитата Сообщение от greg177 Посмотреть сообщение
Но почему-то не понимаю, как найти для каждой вершины h(n).
Я же написал: для всех вершин h(n) равно нулю.

В результате получается обычный обход в ширину, но без информации лучше быть не может... если не считать того, что можно ещё в глубину обходить. Неинформированный поиск - это всегда перебор.
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
14.10.2016, 00:07 5
Цитата Сообщение от Shamil1 Посмотреть сообщение
Чтобы использовать стратегию информированного поиска, нужно обладать хоть какой-нибудь информацией. Иначе остаётся только неинформированный поиск - полный перебор.
В данном случае имеются веса дуг, этих данных достаточно для информированного поиска. Для А* этих данных недостаточно, А* f(n)=g(n) + h(n) = g(n) + 0 = g(n), получаем информированный uniform cost search
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
14.10.2016, 09:19 6
Цитата Сообщение от oldnewyear Посмотреть сообщение
В данном случае имеются веса дуг, этих данных достаточно для информированного поиска.
Эти данные относятся к условию задачи и нужны только для вычисления стоимости пути. Для информированного поиска нужна какая-то дополнительная информация о состояниях.

Цитата Сообщение от oldnewyear Посмотреть сообщение
получаем информированный uniform cost search
Поиск по критерию стоимости (метод равных цен, uniform-cost search, UCS) - один из вариантов неинформированного поиска.


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

Подробнее читайте тут:
Неинформированный метод поиска
1
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
14.10.2016, 09:36 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Эти данные относятся к условию задачи и нужны только для вычисления стоимости пути. Для информированного поиска нужна какая-то дополнительная информация о состояниях.


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


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

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

Добавлено через 1 минуту
Тем не менее полный перебор не нужен в данном случае
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
14.10.2016, 13:49 8
Обход в ширину.
При выполнении некоторого условия (достигли пункта назначения) поиск можно остановить. (Нашли носки уже во втором ящике - остальные можно не проверять). Но в худшем случае (конечная вершина дальше всех от начальной) мы переберём все вершины.
1
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
14.10.2016, 14:10 9
Цитата Сообщение от Shamil1 Посмотреть сообщение
Обход в ширину.
При выполнении некоторого условия (достигли пункта назначения) поиск можно остановить. (Нашли носки уже во втором ящике - остальные можно не проверять). Но в худшем случае (конечная вершина дальше всех от начальной) мы переберём все вершины.
Худший случай - все дуги имеют одинаковый вес. Тогда да. А так нет
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
14.10.2016, 15:38 10
От весов дуг ничего не зависит (ну, кроме результата).
Возьмите (представьте) какую-нибудь карту. Пусть города будут вершинами, а расстояния между ними будут весами дуг. Если мы возьмём один город в центре, а другой на самом дальнем краю, и будем искать путь от одного до другого методом UCS, то мы посетим все города на карте. Если же мы будем использовать информированный поиск (с эвристикой по расстоянию), то мы посетим только те города, которые лежат примерно на прямой между ними. С учётом того, что между всеми соседними городами обычно есть дороги, если это не какая-нибудь горная или островная местность, то велика вероятность, что при поиске мы посетим только те города, которые лежат на кратчайшем пути.
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
14.10.2016, 16:36 11
Цитата Сообщение от Shamil1 Посмотреть сообщение
От весов дуг ничего не зависит (ну, кроме результата).
Возьмите (представьте) какую-нибудь карту. Пусть города будут вершинами, а расстояния между ними будут весами дуг. Если мы возьмём один город в центре, а другой на самом дальнем краю, и будем искать путь от одного до другого методом UCS, то мы посетим все города на карте.
Только в том случае, если расстояния между соседними городами одинаковые
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
14.10.2016, 18:39 12
Цитата Сообщение от oldnewyear Посмотреть сообщение
Только в том случае, если расстояния между соседними городами одинаковые
Проверьте. Откройте карту и в уме посчитайте, в каком порядке алгоритм будет посещать города.
0
ValeryLaptev
Эксперт С++
1055 / 834 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
16.10.2016, 09:25 13
oldnewyear, а алгоритм Дейкстры? Поиск пути между двумя заданными вершинами на взвешенном графе - классика!
Без всякой эвристики вполне себе ищет кратчайший путь на графе со взвешенными ребрами.
И прекращает работу при достижении заданной вершины.
В худшем случае тоже может перебрать все вершины... ))
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
16.10.2016, 09:42 14
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
oldnewyear, а алгоритм Дейкстры?
Это, насколько я понимаю, то же самое, что и uniform cost search.
0
ValeryLaptev
Эксперт С++
1055 / 834 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
16.10.2016, 09:44 15
oldnewyear, я такого названия не знаю. А вот алгоритм Дейкстры описан во всех учебниках по графам. И называется везде именно алгоритмом Дейкстры.
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
16.10.2016, 09:50 16
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
oldnewyear, я такого названия не знаю. А вот алгоритм Дейкстры описан во всех учебниках по графам. И называется везде именно алгоритмом Дейкстры.
Я к изучению графов только приступил. В учебниках по ИИ рассматривается частный случай алгоритма Дейкстры для поиска пути, я оттуда это название взял
0
ValeryLaptev
Эксперт С++
1055 / 834 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
16.10.2016, 09:55 17
Понятно. Тогда еще порекомендую изучить динамическое программирование - часто на графах применяется для поиска оптимального в некотором смысле пути. Еще - метод ветвей и границ - для сокращения полного перебора.
В ИИ эти хорошо известные методы могут иметь свои названия. Особенно, если переводчик неграмотный...
1
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
16.10.2016, 16:33 18
Цитата Сообщение от oldnewyear Посмотреть сообщение
Это, насколько я понимаю, то же самое, что и uniform cost search.
Поиск по критерию стоимости логически эквивалентен алгоритму Дейкстры. Только в алгоритме Дейкстры все узлы добавляются в очередь при инициализации, а в алгоритме поиска по критерию стоимости узлы добавляются «на лету» во время поиска. Поэтому алгоритм Дейкстры применим только к явно заданным графам, в то время как алгоритм UCS может быть применён как к явным, так и к неявным графам.
2
16.10.2016, 16:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.10.2016, 16:33

Алгоритмы на графах
Задали мне в универе Написать програмку: Существует связный граф, без ребер идущих между...

Вопросы о графах
Всем привет! Появилось несколько вопросов о графах: 1) Как представить граф в C++? 2) Как...

Операции на графах
бывает ли графы с 11 вершинами, степени которых 1,1,1,2,2,2,3,4,4,5,5? Если есть, то, что для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru