crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )


  Ответ в Intelligent scissors
Введите ваше имя
Подтвердите код

Введите в поле код из 6 символов, отображенных в виде изображения. Если вы не можете прочитать код с изображения, нажмите на изображение для генерации нового кода.
Теги
Выровнять по центру
Ссылка на тему
Ссылка на сообщение
Скрытый текст
Сокращение
Код с подсветкой
Offtopic
 
Удалить форматирование
Спец. элементы
Шрифт
Размер
 
Цвет шрифта
 
Отменить ввод
Вернуть ввод
Полужирный
Курсив
Подчеркнутый
 
 
Смайлики
Вставить изображение
Вставить адрес электронной почты
Цитата
Код
Раскрывающийся текст
 
Увеличить отступ
По левому краю
По центру
По правому краю
Вставить список
Вставить список

Опции сообщения
 Включить смайлы?
Иконки сообщения
(Опционально)
                                
                                
  [ Без иконки ]
 


Последние 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.
Просмотр темы полностью (откроется в новом окне)
RSS Рейтинг@Mail.ru Текстовая версия Сейчас: 10.7.2025, 2:15