crossplatform.ru

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

> Intelligent scissors
wiz29
  опции профиля:
сообщение 20.8.2010, 16:06
Сообщение #1


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

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

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




Репутация:   12  


Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
 
Начать новую тему
Ответов
ufna
  опции профиля:
сообщение 27.8.2010, 15:37
Сообщение #2


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

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

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




Репутация:   5  


а теперь поподробнее про ньюанс. В чем конкретно он выражается, если веса просчитаны? Что-то еще влияет на маршрут?

если учавствуют всего две вершины, то путь находится куда быстрее именно алгоритмом A*, тем более на больших полях где число точек глобально. Я его использую на гпс навигаторах для прокладки маршрута по десяткам тысяч точек и работает - секунды, на компе - менее полсекунды на самых диких атласах. Могу скинуть код-схему алгоритма.

ну если отставить пути, то что занимает большее количество времени? Какая часть? Как я понял, основные части:

1. просчет весов графа
2. построение путей
3. что-то дальше

какие пропорции по временным затратам?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Сообщений в этой теме
- wiz29   Intelligent scissors   20.8.2010, 16:06
- - Алексей1153   Какой алгоритм ?   20.8.2010, 16:32
|- - kibsoft   Цитата(Алексей1153 @ 20.8.2010, 17:32) Ка...   20.8.2010, 18:59
- - Алексей1153   ааа, вона чего... То есть выбор произвольной замкн...   20.8.2010, 19:19
|- - wiz29   Цитата(Алексей1153 @ 20.8.2010, 20:19) аа...   27.8.2010, 13:09
- - ufna   приведи код реализации, посмотрим.   27.8.2010, 13:10
- - wiz29   Раскрывающийся текстnamespace liveware { //solve ...   27.8.2010, 13:17
- - ufna   оберни плз в тег code, чтобы читабельность сохрани...   27.8.2010, 13:20
- - Алексей1153   в zip-архиве можно )   27.8.2010, 13:26
- - wiz29   CODE#ifndef LWSOLVE_H #define LWSOLVE_H #include ...   27.8.2010, 13:57
- - Алексей1153   блин, интересно, конечно, но сейчас вапще некогда ...   27.8.2010, 14:02
- - ufna   И покажи код где ты этот алгоритм запускаешь и как...   27.8.2010, 14:02
- - wiz29   Здесь именно вычисляется маршрут от SeedNode до вс...   27.8.2010, 14:29
- - ufna   а SeedNode всегда одна? т.е. можно увидеть как пр...   27.8.2010, 14:30
- - wiz29   Сейчас, расскажу как на практике, всю задачу как т...   27.8.2010, 14:49
- - ufna   а что происходит после того, как кратчайшие пути п...   27.8.2010, 15:04
- - wiz29   Если ты видел в фотошопе магнетик лассо, то он осн...   27.8.2010, 15:12
- - ufna   ну вот смотри, промелькнуло название "заданна...   27.8.2010, 15:29
- - wiz29   1. в алгоритме участвует 1 заданная вершина (затра...   27.8.2010, 15:32
- - ufna   а теперь поподробнее про ньюанс. В чем конкретно о...   27.8.2010, 15:37
- - wiz29   переход и вершины "а" в вершину "b...   27.8.2010, 15:39
- - ufna   с Флойдом сразу "отпало" как только речь...   27.8.2010, 15:41
- - wiz29   Самая критичная операция именно решение дейкстры, ...   27.8.2010, 15:41
- - ufna   А просчет дейкстры - это как раз часть прокладки м...   27.8.2010, 15:44
- - wiz29   А можешь сказать временную сложность?   27.8.2010, 15:45
- - ufna   Вся суть сего алгоритма - в правильном задании эвр...   27.8.2010, 15:50
- - wiz29   ну у меня количиства измеряются через 1М+ порядка ...   27.8.2010, 15:56
- - ufna   ну по атласам у меня тоже миллионные значения идут...   27.8.2010, 16:00
- - wiz29   Если положить h(x) = 0 для всех вершин, то мы полу...   27.8.2010, 16:03
- - ufna   Если h(x) = 0 (а это и есть эвристическая функция)...   27.8.2010, 16:43
- - Nik92   Цитата(wiz29 @ 20.8.2010, 16:06) Реализов...   1.3.2011, 17:51


Быстрый ответОтветить в данную темуНачать новую тему
Теги
Нет тегов для показа


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




RSS Текстовая версия Сейчас: 11.12.2024, 2:38