Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
x5reunion
3 / 3 / 1
Регистрация: 25.03.2014
Сообщений: 45
1

АСтар поиск кратчайшего пути

04.02.2015, 11:42. Просмотров 759. Ответов 3
Метки нет (Все метки)

Здравствуйте знаю что подобных тем сотни, но я никак не могу разобраться в двух вещах.

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

Допустим у нас есть массив. Стартовая ячейка [ 0 , 0 ] , а наша цель [ 3 , 0 ].

[ 0 , 0 ] = 1; [ 0 , 1 ] = 1; [ 0 , 2 ] = 1; [ 0 , 3 ] = 1;

[ 1 , 0 ] = 1; [ 1 , 1 ] = 255; [ 1 , 2 ] = 255; [ 1 , 3 ] = 1;

[ 2 , 0 ] = 255; [ 2 , 1 ] = 255; [ 2 , 2 ] = 255; [ 2 , 3 ] = 1;

[ 3 , 0 ] = 1; [ 3 , 1 ] = 1; [ 3 , 2 ] = 1; [ 3 , 3 ] = 1;

1 можно пройти 255 непроходима. 10 единиц я взял за базовую стоимость. По логике алгоритма мы берем две соседние ячейки которые расположены ортогонально.

Это [ 1 , 0 ] = 1; [ 1 , 0 ] = 1; Стоимость при передвижении к ним будет равна 10. Далее вычисляем их примерную стоимость до достижения цели.

У ячейки [ 1 , 0 ] она будет самая низкая равна 20 + 10 = 30;
А у ячейки [ 0 , 1 ] она будет равна 40 + 10 = 50;

Естественно мы берем ячейку [ 1 , 0 ] помещаем ее в закрытый список, а ячейку [ 1 , 0 ] оставляем в открытом.

Далее следующая итерация нас заводит в тупик так как позади ячейка которую мы проверили, слева выход за пределы массива, а справа и снизу путь непроходим.

Вопрос в случае подобной неудачи мы просто возвращаемся к открытому списку и выбираем ячейку с самой низкой базовой стоимостью? И повторяем наш путь по новой?

Следовательно условие завершения алгоритма будет иметь два вывода первый успех точка найдена, а второй когда в открытом списке больше нет ячеек, следовательно путь невозможно найти?


( но я просматривал таблицы стоимости ячеек на разных сайтах и не всегда ячейка, которая находится в открытом списке с самой низкой базовой стоимостью будет вести по правильному пути, если мы зашли в тупик )


Далее мы посчитали стоимость всех ячеек до цели выйдет что то типо.

[ 0 , 0 ] = 0; [ 0 , 1 ] = 10 + 40; [ 0 , 2 ] = 20 + 50; [ 0 , 3 ] = 30 + 60;

[ 1 , 0 ] = 30; [ 1 , 1 ] = 255; [ 1 , 2 ] = 255; [ 1 , 3 ] = 40 + 50;

[ 2 , 0 ] = 255; [ 2 , 1 ] = 255; [ 2 , 2 ] = 255; [ 2 , 3 ] = 50 + 40;

[ 3 , 0 ] = 1; [ 3 , 1 ] = 80 + 10; [ 3 , 2 ] = 70 + 20; [ 3 , 3 ] = 60 + 30;

И все мы дошли до цели.

В закрытом списке у нас будут ячейки

[ 0 , 0 ]
[ 0 , 1 ]
[ 0 , 2 ]
[ 0 , 3 ]
[ 1 , 3 ]
[ 2 , 3 ]
[ 3 , 3 ]
[ 3 , 2 ]
[ 3 , 1 ]

и тупиковая ячейка [ 1 , 0 ].

Вопрос во всех гайдах по алгоритму пишут что надо идти от конечной ячейки до стартовой просто перебирая все в обратном порядке, я никак не могу понять по какой логике отсеиваются тупиковые ячейки? Их может быть и 2 и 3 и сотня и их стоимость ниже других, но они ведут в тупик.
Я никак не могу понять как их исключать, как восстановить полученный путь
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2015, 11:42
Ответы с готовыми решениями:

Поиск кратчайшего пути
Всем доброго времени суток! Скажите, пожалуйста. Есть ли какие-то принципиальные отличия волнового...

Поиск кратчайшего пути лошадью
(p, q)-лошадь - это обобщение обычного шахматного коня. (p, q)-лошадь своим ходом перемещается на p...

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в...

Поиск кратчайшего пути в лабиринте
Добрый день, знаю два алгоритма. 1. А - стар 2. Волновой Нужен какой нибудь 3... Ссылки...

Поиск кратчайшего пути в лабиринте
Пишу программу для нахождения (и вывода) кратчашего пути в лабиринте, заданном в текстовом файле в...

3
raxp
10195 / 6577 / 493
Регистрация: 28.12.2010
Сообщений: 21,166
Записей в блоге: 1
04.02.2015, 12:01 2
A Star. Пространство и алгоритм поиска пути. - ПРОграммист, 2011, №16.
0
x5reunion
3 / 3 / 1
Регистрация: 25.03.2014
Сообщений: 45
05.02.2015, 02:01  [ТС] 3
Благодарю за ссылку на журнал, правда он практически мне ни чем не помог, но я почти решил задачу.
0
raxp
10195 / 6577 / 493
Регистрация: 28.12.2010
Сообщений: 21,166
Записей в блоге: 1
05.02.2015, 07:36 4
...прочитав опыт других ко всем приходит понимание.
0
05.02.2015, 07:36
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2015, 07:36

Двунаправленный поиск кратчайшего пути в графах
Никто не встречал реализованный на c\c++ алгоритм? Добавлено через 17 часов 24 минуты помогите...

Поиск кратчайшего пути в матрице или установка факта, что такового не существует
Всем привет!!!я начал решать задачку и у меня не получается, а не получается у меня самое главное...

Алгоритмы кратчайшего пути
Нужен алгоритм нахождения кратчайшего пути между двумя точками (волновой не подходит). Заранее...


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

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

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