 Intelligent scissors |
Здравствуйте, гость ( Вход | Регистрация )
wiz29 опции профиля:
|
 20.8.2010, 16:06
Сообщение
#1
|
 Старейший участник  Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация:  12 
 |
Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)
|
 |
  
|
 |
Ответов
|
ufna опции профиля:
|
27.8.2010, 15:50
Сообщение
#2
|
 Активный участник Группа: Участник Сообщений: 362 Регистрация: 24.5.2008 Из: Курган/СПб Пользователь №: 182 Спасибо сказали: 29 раз(а) Репутация: 5
|
Вся суть сего алгоритма - в правильном задании эвристической оценки, здесь нужно подумать. Сокращает работу алгоритма просто в десятки и сотни раз. А если про нее забыть - это будет обычный обход графа в ширину.
На вики есть описание к примеру, ситуация на практике - 70к вершин, 100к ребер. Прокладка из А в Б "обход в ширину" - около 45к итераций, через А* - около 700. Дейкстру использовать на мобильных девайсах предполагается невозможным, поэтому это чисто практика работы с GPS маршрутами. |
|
|
|
Сообщений в этой теме
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 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
|
|
Текстовая версия | Сейчас: 3.6.2023, 7:04 |