Форум программистов, компьютерный форум, киберфорум
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
Inside1995
3 / 3 / 1
Регистрация: 04.04.2017
Сообщений: 23
#1

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++

04.04.2017, 18:43. Просмотров 442. Ответов 1

Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка).
Определение. Перестано́вочные головоло́мки — головоломки, состоящие из множества подвижных элементов, которые могут занимать определённые места в головоломке и переводиться с места на место по определённым правилам. Подвижными элементами могут быть разноцветные шарики, кубики, фишки с буквами или цифрами, диски(ссылка из Википедии).
В общем на вход дается матрица:
Например: 8 4 3
5 0 6
1 2 7
где 0- это пустая клетка.
На выходе необходимо получить матрицу вида:
1 2 3
4 5 6
7 8 0

Насколько я понял в качестве эвристической функции необходимо использовать так называемый метод Манхеттена, где для каждого диска необходимо вычислить расстояние до его "настоящего" места.
Этот метод я смог реализовать, но так и не могу понять как реализовать сам алгоритм. Где начальная точка и что вообще нужно делать. Почитал разные статьи про этот алгоритм, но там в основном описывают этот метод на примере поиска кратчайшего пути в лабиринте (как он работает в этом примере, я разобрался), а вот как его перенести на эту задачу, понять не могу.
Заранее спасибо!
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2017, 18:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) (C++):

Алгоритм поиска пути A* - C++
использую библиотеку SFML только для окна пытался сделать алгоритм поиска пути от одной до другой точки(левая и правая кнопка мыши) окно...

Алгоритм шифрования - C++
Доброго времени суток. Имеется программа, которая шифрует данные собственным алгоритмом. Есть пример зашифрованных данных (вместе с...

Алгоритм Эрли - C++
Народ, спасите мне жизнь!!!! С лабораторки нужно написать программу "Алгоритм Эрли", а моих знаний об етом алгоритме оочень мало!!!...

алгоритм IDEA - C++
Есть бинарный 16 байтный файл ключа.Надо разбить его на восемь 16 битных ключей,затем выполнить циклический сдвиг на 25 разрядов влево и...

Подскажите алгоритм - C++
Добрый вечер. Стоит такая задача: проверить входит ли точка в произвольный многоугольник. Все координаты вершин многоугольника и координаты...

Какой алгоритм выбрать? - C++
Господа, у меня такой вопрос. Имеется задание на курсовую (про которую даже нельзя сказать, что её собака съела) однако я даже не знаю с...

1
Inside1995
3 / 3 / 1
Регистрация: 04.04.2017
Сообщений: 23
07.04.2017, 22:51  [ТС] #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Если кому-то может понадобиться эта информация, я смог определить метод по которому должен строиться алгоритм в этом случае.
Может я допущу какие- либо ошибки, так как это лишь мое понимание и может кому- то оно должно быть полезно.
Первым делом стоит определить что из себя представляет сам алгоритм А*. На самом деле это нечто схожее с алгоритмом Дейкстры, но добавлено еще некоторое условие, а именно эвристическая функция(f()). f() = g + h, где g - это стоимость достижения текущего узла, а h - это расстояние от текущего узла до нашей конечной цели.
за h в этом примере принято использовать метод манхеттена.
Метод Манхеттена. В этом методе необходимо найти каждую цифру, стоящую не на своем месте, посчитать сколько шагов нужно найти для достижения ее конечной позиции, и сложить все получившиеся результаты (результаты каждой цифры стоящей не на своем месте).
Например.
1 2 3
4 5 6
8 7 0
Если наш конечный результат должен выглядеть так:
1 2 3
4 5 6
7 8 0, то g у нас равно 2. Так как 7 у нас находится не на своем месте и 8 находится не на своем месте. 1 + 1 = 2.
Когда мы научились находить g для какой - либо расстановки возникает вопрос интерпретации самой доски, т.е. как доску хранить и всю информацию которая касается текущей доски.
Предлагается хранить все это в классе или структуре, где поля будут иметь следующий вид:
доска - может иметь вид матрицы или обычного массива
переменная g - для каждой промежуточной доски будет иметь свое значение
переменная h - аналогично с g
переменная f - хранит значение, возвращаемое функцией
переменная, которая хранит местоположение нуля в текущей таблице. Это важно, чуть ниже опишу почему.
указатель на родителя - необходимо для отслеживания конечного пути до цели.

Надеюсь пока все понятно.
Теперь собственно к самому алгоритму.
Алгоритм подразумевает хранение двух контейнеров:
openset - в книгах по ИИ это то, что называется переферией. То есть узлы, до которых можно дойти из текущего узла. В нашем случае узлы - это доски.
closedset - это узлы которые мы уже посетили.
openset советуется хранить в priorityqueue, так как начинать перебирать узлы нужно с узла, имеющего самый низкий показатель эвристической функции. А это ни что иное, как minheap.

Теперь нужно разобраться с тем, что же представляют из себя промежуточные доски.
Давайте представим следующую картину.
Наша входящая доска имеет вид
1 4 6
8 0 5
2 3 7
Какие варианты досок мы можем получить из текущей доски? Ответ очевиден. Это 4 разных доски, где нуль меняется с числом стоящим справа от него, слева от него, снизу от него и сверху от него. Выходит что в openset у нас попадают все "дети" текущей доски. А сама текущая доска помечается как посещенная(т.е. добавляется в closedset)
Это как раз тот случай, когда нам необходимо знать, где находится нуль. К слову если бы нуль находился в правом верхнем углу, то имелось бы всего два ребенка этой доски, так как нуль может поменяться местами лишь с числами стоящими слева от него и снизу от него.

Алгоритм А*
1)В openset помещается стартовая доска.
2)Начинаем цикл, который будет работать до тех пор, пока в openset есть какие-либо объекты
3)Извлекаем из openset элемент и сравниваем его с нашей целью. Если совпал, то отлично. Нет? Идем дальше
4)Помечаем текущую доску, как посещенную
5)Находим всех "детей" этой доски и помещаем их в openset, конечно если такой доски нет в closedset
6)Переходим к пункту 2

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

Надеюсь хоть кому-то это будет полезно. Еще раз повторюсь- это лишь мое понимание этого алгоритма и возможно я допустил какие-либо ошибки в самом алгоритме или еще в чем-то. НО, я реализовал этот алгоритма и он выдавал верные решения.

P.S.S. В этой задаче могут попасться доски, для которых НЕТ РЕШЕНИЯ. В самом коде можно предусмотреть этот факт и сразу вывести ответ.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2017, 22:51
Привет! Вот еще темы с ответами:

Алгоритм с константной асимптотикой - C++
Нужно за О(1) давать ответ сколько элементов элементов последовательности установлено в 1 (первоначально - все обнулены), до определенного...

Объясните алгоритм хэширования: ГОСТ Р 34.11-94 - C++
Доброго времени суток) Объясните, пожалуйста, алгоритм хэширования госта р 34.11-94) И очень приятным дополнением была бы готовая...

Алгоритм игры Быки -коровы в С++ - C++
сложно ли реализовать алгоритм игры Быки -коровы в С++

Разработка ВОЛЬТ-АМПЕРМЕТРА алгоритм работы на С ++ - C++
Как примерно будет выглядеть алгоритм или программа которая будет реализовать ВОЛЬТ-АМПЕРМЕТР,суть которого будет вывод на дисплей...


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

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

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