crossplatform.ru

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

4 страниц V  < 1 2 3 4 >  
Ответить в данную темуНачать новую тему
> Intelligent scissors
wiz29
  опции профиля:
сообщение 27.8.2010, 15:39
Сообщение #21


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


переход и вершины "а" в вершину "b" стоит не столько же сколькоперехо из "b" в "a" ребра имеют 2 направления
и альго Флойда здесь не совсем подойдет т.к. его сложность O(n^3) тогда как Дейкстра решает задачу за O(n^2 + m) m-число ребер (это самая плохая оценка для Дейкстры)

Хех, круто зато Флойд паралелится:) спс за подсказку:)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 27.8.2010, 15:41
Сообщение #22


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


с Флойдом сразу "отпало" как только речь зашла о двух вершинах - в таких случаях обычно играют роль алгоритмы более узкого назначения.

по весам понял, т.е. путь из b в a может быть не кратчайшим, просто совпадает с из а в b.

Сообщение отредактировал ufna - 27.8.2010, 15:42
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.8.2010, 15:41
Сообщение #23


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


Самая критичная операция именно решение дейкстры, на моей машине рассчитывается порядка 0.8 сек (это дороговато)
Если могешь, скинь А* просто ничего про него не слышал
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 27.8.2010, 15:44
Сообщение #24


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


А просчет дейкстры - это как раз часть прокладки маршрута, поэтому я об этом речь и завел.


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:45
Сообщение #25


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


А можешь сказать временную сложность?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 27.8.2010, 15:50
Сообщение #26


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


Вся суть сего алгоритма - в правильном задании эвристической оценки, здесь нужно подумать. Сокращает работу алгоритма просто в десятки и сотни раз. А если про нее забыть - это будет обычный обход графа в ширину.

На вики есть описание

к примеру, ситуация на практике - 70к вершин, 100к ребер. Прокладка из А в Б "обход в ширину" - около 45к итераций, через А* - около 700. Дейкстру использовать на мобильных девайсах предполагается невозможным, поэтому это чисто практика работы с GPS маршрутами.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.8.2010, 15:56
Сообщение #27


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


ну у меня количиства измеряются через 1М+ порядка:) ну или около того это по вершинам.

надо попробовать твой алгоритм, тем более что у меня есть статья как вычислять эвристики
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 27.8.2010, 16:00
Сообщение #28


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


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


вычисление эвристики если у тебя по данной теме - дак тем более здорово должно быть. А дейкстра реально не имеет смысла на таких значениях - 0.8 сек - это слишком много, особенно для декстопа.

с эвристикой еще так - чем она выше (т.е. ее роль), тем больше погрешность. Чем ниже - тем точнее. С этим всегда можно играть, добиваясь разнообразных результатов.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.8.2010, 16:03
Сообщение #29


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай — алгоритм Дейкстры.

а ты очередь с приоритетом сам писал или заимствовал гдето? (просто я у себя использовал стл вариант а апдейт сделал тупо окучивание всей последовательности, если какойто более производительный вариант?)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 27.8.2010, 16:43
Сообщение #30


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

Спасибо сказали: 29 раз(а)




Репутация:   5  


Если h(x) = 0 (а это и есть эвристическая функция), то мы получим не алгоритм Дейкстры, а обход графа в ширину, это немного разные вещи :)

очередь с приоритетом писал сам, на основе QList для хранения самой очереди и QSet для быстрой отсечки "есть/нет" в очереди. Не факт что оптимально, но для моих целей работает как часы. Список Closed у меня тоже свой, но все основано на QHash - у меня просто стандартизированный под мой проект интерфейс.

вот еще ссылочка хорошая, там по некоторым алгоритмам хорошо написано: http://khpi-iip.mipk.kharkiv.edu/library/d...gsu/oglav6.html

дядька из КГУ нашего писал, плюс я сам немного лапку для создания некоторых шагов приложил :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

4 страниц V  < 1 2 3 4 >
Быстрый ответОтветить в данную темуНачать новую тему
Теги
Нет тегов для показа


2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 2.12.2022, 15:05