Форум на CrossPlatform.RU -> Ответ в Intelligent scissors

Последние 10 сообщений [ в обратном порядке ]

Nik92	Дата 1.3.2011, 17:51
	Цитата(wiz29 @ 20.8.2010, 16:06) Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер) привет! ты не мог бы мне кинуть свою реализацию? nikolas9292@rambler.ru
ufna	Дата 27.8.2010, 16:43
	Если h(x) = 0 (а это и есть эвристическая функция), то мы получим не алгоритм Дейкстры, а обход графа в ширину, это немного разные вещи очередь с приоритетом писал сам, на основе QList для хранения самой очереди и QSet для быстрой отсечки "есть/нет" в очереди. Не факт что оптимально, но для моих целей работает как часы. Список Closed у меня тоже свой, но все основано на QHash - у меня просто стандартизированный под мой проект интерфейс. вот еще ссылочка хорошая, там по некоторым алгоритмам хорошо написано: http://khpi-iip.mipk.kharkiv.edu/library/d...gsu/oglav6.html дядька из КГУ нашего писал, плюс я сам немного лапку для создания некоторых шагов приложил
wiz29	Дата 27.8.2010, 16:03
	Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай — алгоритм Дейкстры. а ты очередь с приоритетом сам писал или заимствовал гдето? (просто я у себя использовал стл вариант а апдейт сделал тупо окучивание всей последовательности, если какойто более производительный вариант?)
ufna	Дата 27.8.2010, 16:00
	ну по атласам у меня тоже миллионные значения идут, но там в моем случае уже идет разбивка на три уровня графов )) вычисление эвристики если у тебя по данной теме - дак тем более здорово должно быть. А дейкстра реально не имеет смысла на таких значениях - 0.8 сек - это слишком много, особенно для декстопа. с эвристикой еще так - чем она выше (т.е. ее роль), тем больше погрешность. Чем ниже - тем точнее. С этим всегда можно играть, добиваясь разнообразных результатов.
wiz29	Дата 27.8.2010, 15:56
	ну у меня количиства измеряются через 1М+ порядка ну или около того это по вершинам. надо попробовать твой алгоритм, тем более что у меня есть статья как вычислять эвристики
ufna	Дата 27.8.2010, 15:50
	Вся суть сего алгоритма - в правильном задании эвристической оценки, здесь нужно подумать. Сокращает работу алгоритма просто в десятки и сотни раз. А если про нее забыть - это будет обычный обход графа в ширину. На вики есть описание к примеру, ситуация на практике - 70к вершин, 100к ребер. Прокладка из А в Б "обход в ширину" - около 45к итераций, через А* - около 700. Дейкстру использовать на мобильных девайсах предполагается невозможным, поэтому это чисто практика работы с GPS маршрутами.
wiz29	Дата 27.8.2010, 15:45
	А можешь сказать временную сложность?
ufna	Дата 27.8.2010, 15:44
	А просчет дейкстры - это как раз часть прокладки маршрута, поэтому я об этом речь и завел. A* - наверное самый популярный алгоритм в геймдеве. Описание ниже. Если нужно, могу скинуть код с классами для Open, Closed и сам алгоритм в Qt. /* приоритетная очередь Open список Closed ПоискАЗвездочка s.g = 0 // s - стартовый узел s.h = ЭвристическаяОценка( s ) s.f = s.g + s.h s.родитель = null добавить s в Open пока очередь Open не пуста извлечь n из Open // n - узел с наименьшей стоимость в Open если n целевой узел сконструировать путь выйти с кодом "успешное завершение" для каждого наследника n' узла n newg = n.g + стоимость(n,n') если n' в Open или Closed, и n'.g <= newg пропустить n' n'.родитель = n n'.g = newg n'.h = ЭвристическаяОценка( n' ) n'.f = n'.g + n'.h если n' в Closed удалить n' из Closed если n' не в Open положить n' в Open положить n в Closed выйти с кодом "путь не найден" */
wiz29	Дата 27.8.2010, 15:41
	Самая критичная операция именно решение дейкстры, на моей машине рассчитывается порядка 0.8 сек (это дороговато) Если могешь, скинь А* просто ничего про него не слышал
ufna	Дата 27.8.2010, 15:41
	с Флойдом сразу "отпало" как только речь зашла о двух вершинах - в таких случаях обычно играют роль алгоритмы более узкого назначения. по весам понял, т.е. путь из b в a может быть не кратчайшим, просто совпадает с из а в b.
Просмотр темы полностью (откроется в новом окне)