Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
3 / 3 / 1
Регистрация: 04.04.2017
Сообщений: 56
1

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

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

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

Насколько я понял в качестве эвристической функции необходимо использовать так называемый метод Манхеттена, где для каждого диска необходимо вычислить расстояние до его "настоящего" места.
Этот метод я смог реализовать, но так и не могу понять как реализовать сам алгоритм. Где начальная точка и что вообще нужно делать. Почитал разные статьи про этот алгоритм, но там в основном описывают этот метод на примере поиска кратчайшего пути в лабиринте (как он работает в этом примере, я разобрался), а вот как его перенести на эту задачу, понять не могу.
Заранее спасибо!
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.04.2017, 18:43
Ответы с готовыми решениями:

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab...

Волновой алгоритм поиска пути
Добрый день. Реализую всем известный алгоритм поиска кратчайшего пути. Но не могу понять одну...

Алгоритм А* (А стар)
Хочу создать консольную игру (пишу с использованием библиотеки iostream) и мне надо реализовать...

Волновой алгоритм (алгоритм Ли)
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что...

1
3 / 3 / 1
Регистрация: 04.04.2017
Сообщений: 56
07.04.2017, 22:51  [ТС] 2
Лучший ответ Сообщение было отмечено SatanaXIII как решение

Решение

Если кому-то может понадобиться эта информация, я смог определить метод по которому должен строиться алгоритм в этом случае.
Может я допущу какие- либо ошибки, так как это лишь мое понимание и может кому- то оно должно быть полезно.
Первым делом стоит определить что из себя представляет сам алгоритм А*. На самом деле это нечто схожее с алгоритмом Дейкстры, но добавлено еще некоторое условие, а именно эвристическая функция(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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.04.2017, 22:51

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

Волновой алгоритм
Нужно найти кратчайший путь в лабиринте размерностью 10х10 , и выводить ответ. Помогите

Волновой алгоритм
Скажите почему программа зацикливается. #include<bits/stdc++.h> using namespace std; int a =...

Волновой алгоритм
Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 20*20, причем координаты начала...

Волновой алгоритм
Доброго времени суток, дорогие форумчане. Никак не додумаю волновой алгоритм, помогите, кто чем...

Волновой алгоритм
Подскажите пожалуйста, на сколько сложно изготовить из матрицы 0000 0000 0000 напр.4345 3234...

Волновой алгоритм
Здравствуйте, очень прошу помочь с реализацией волнового алгоритма только лишь с помощью матрицы...


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

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

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