|
Модераторы: Daevaorn |
|
Master01 |
|
||||||||||||||||
Шустрый Профиль Группа: Участник Сообщений: 89 Регистрация: 22.8.2007 Репутация: 2 Всего: 2 |
Вы частным доказываете общее. Что уже делает все ваши выводы заведомо неверными.
определённо
Вы поняли правильно.
Вот это то, что вы понять не можете. Ваша догадка h(x) Манхэттэн - это есть некоторое среднее ожидаемое расстояние, т.е. значит, что реальное расстояние может быть как больше, так и меньше. Но если случай, когда реальное расстояние может быть меньше существует (т.е. H() переоценила расстояние), то, следовательно, вы не можете быть уверены в минимальности найденного пути. Единственный выход - заложить в h() заведомо наименьшее возможное расстояние - т.е. прямую. Только в этом случае вы гарантировано получите минимальный путь. Но поскольку dx + dy > sqrt(dx^2 + dy^2) то алгоритм станет менее направленным - замедлиться. Поэтому я и написал, что нужен балланс. Пройденный путь можно измерить, т.к. мы его уже прошли, понимайте это как "измерили линейкой". Ожидаемый остаток - прогноз, основанный на некоторых знаниях о пространстве. Так вот между вычислением g(x) и h(x) ровно столько же общего как и в измерении текущей температуры и предсказании температуры на завтра.
Вы в каких-то терминах выражаетесь неоределённых. Что значит "менее подходяще"? Если вы о точности, то вы сами сказали, что если эвристика переоценивает оставщееся расстояние то поиск "h() > r(), быстрее поиск, но нет гарантии оптимального решения".
Туфтология. "Вминяемой переоценкой без переоценки". Вы сами понимаете то свою точку зрения, которую защищаете? Кроме того, вы противопоставляете одной субъективной оценке "вминяемой" другую "более подходящим". Ерунда. А
Вот именно.
А вам не приходило в голову, что мне ваша точка зрения понятна, и может реально хватит писать мне одно и тоже, а пора самому разобраться. Я же сказал, что я этой проблемой занимался. Я не имею привычки учить людей тому, в чём, считаю, не разбираюсь. |
||||||||||||||||
|
|||||||||||||||||
Isaev |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
Ну это же дело случая... т.е. для другого примера вряд ли он совпадёт с оптимальным (будет больше ходов), хотя из экономии времени, возможно есть смысл использовать, где оптимальность пуки не критична А вы часто цепляетесь к словам, что сводит большинство споров к трате времени, т.к. по сути говорите об одном и том же, а каждый доказывает своё. Это сообщение отредактировал(а) Isaev - 25.11.2010, 17:07 |
|||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
Во первых, не доказываю, я же сказал, эмпирически, т.е. не исключаю что это возможно... Несколько различных комbинаций (штук пять) дали оптимальный результат с "неbольшой" переоценкой эвристики. Возникло ощущение, что есть зависимость от пройденного пути. Надо bудет сгенерировать штук 5000, и проверить на них, если все дадут оптимальный результат, это уже что-то...
Во вторых, пройденное расстояние можно считать как угодно, хоть bы по потраченному на него времени, или с учётом местности (по песку медленнее чем по асфальту) и т.п. и т.д.. Как bы не рассчитывался "пройденный путь" (не оbязательно bуквально путь, просто цепь шагов), эвристика, которая рассчитывается по тому же принципу, даёт оптимальный результат. Т.е. пройденный путь можно считать как манхэтеннское, как прямую линию линейкой, как время... Не исключено, что есть ещё варианты. Что вы зациклились на одном и том же? Это уже похоже на bред... Вы комментируете только вступление, которое bез контекста имеет другой смысл, не тот который я в него вложил. Может bыть посмотрите уже код? Честно говоря я устал оbъяснять очевидное, такое ощущение, что вы читаете только то что вам надо, остальное просто игнорируете. Хотя, можете остаться при своём мнении, мне всё равно... Никоrда не мог понять, зачем выдирать отдельные слова из предложения, составлять из них что-то bессмысленное и приписывать авторство другому человеку. Типичный троллинг...
Хотя, я не отказался bы посмотреть на реализацию A*, которая куbик Руbика соbирает. Потянете? Вы же, вроде как, "соbаку съели", должно bыть несложно... Добавлено @ 17:34 Это сообщение отредактировал(а) Леопольд - 25.11.2010, 18:24 -------------------- вопросов больше чем ответов |
|||
|
||||
ufna |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 75 Регистрация: 4.4.2005 Где: Курган/СПб Репутация: нет Всего: 0 |
В А-стар главное реально - баланс эмпирической функции. И чаще всего применение А-стара оправдано в случаях, когда можно получать не минимальный путь, а близкий к этому - на нем часто пишется маршрутизация АИ, прокладка маршрутов по карте дорог и т.п.
Не вижу проблем для использования h=sqrt(x^2+y^2), однако если нужны сверхбыстрые решения, то можно вводить таблицу кэша значений эмпирики, если есть более четкие условия на количество точек и т.п., да и вообще есть разные приемы модернизации алгоримта для решения конкретной задачи. А-стар - ни разу не алгоритм дейкстры, не нужно их смешивать. Это обход графа в ширину с эвристикой для выбора порядка проверки вершин. Очереди нужны, open и close, причем оптимизированные для действий по этому алгоритму. Это сообщение отредактировал(а) ufna - 25.11.2010, 18:59 |
|||
|
||||
Леопольд |
|
||||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
h() эвристика, r() пройденный путь переоценка эвристики = h() * (1 + 0.01 * r()) На дискретной карте, не работает. Показалось... Это сообщение отредактировал(а) Леопольд - 26.11.2010, 10:52 -------------------- вопросов больше чем ответов |
||||
|
|||||
Master01 |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 89 Регистрация: 22.8.2007 Репутация: 2 Всего: 2 |
Ufna, простите, но обход в ширину проверяет вершины в том порядке в каком их находит, т.е. не сортирует их по стоимости. Алгоритм Дейкстры вводит такую сортировку, но не использует эвристику. Я имел ввиду, что при нулевой эвристике h(x)=0 Astar становится алгоритмом Дейкстры, поскольку оценивает только реальную стоимость пути при выборе "наилучшей" вершины. В остальном, я с вами согласен. |
|||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
Это сообщение отредактировал(а) Леопольд - 25.11.2010, 21:46 -------------------- вопросов больше чем ответов |
|||
|
||||
ufna |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 75 Регистрация: 4.4.2005 Где: Курган/СПб Репутация: нет Всего: 0 |
Master01,
Да, Вы правы, по сути алгоритм Дейкстры - частный случай А-стар с h(x) = 0 для всех х. Хотя реализация у них разная, я говорил именно в этом ключе - т.к. Дейкстра работает как d(x,y), и имеет свои требования к памяти и прочему. |
|||
|
||||
Master01 |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 89 Регистрация: 22.8.2007 Репутация: 2 Всего: 2 |
У меня и в мыслях не было искажать ваши слова. Я просто поначалу не правильно прочитал. Признаю, это не "туфтология". Я имел ввиду, что именно это я и хотел сказать. И дальше все ваши рассуждения - неверны. Остальное не комментирую, как не имеющее отношение к делу. |
|||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
Прям таки все, или всё же какие-то конкретно?
-------------------- вопросов больше чем ответов |
|||
|
||||
Isaev |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
Master01, Вы бы, чтобы не быть голословным, раз уж "на этом собаку съели" привели бы пример, который работает быстрее, чем у Леопольда, и мы бы дружно задумались, что возможно и правда мы все не правы...
|
|||
|
||||
Isaev |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
Охотно верю, когда остваиваете Может вы совершенно случайно можете это на Delphi написать? Я был бы крайне признателен, т.к. этот язык мне ближе, если честно то что писали на яве, отлично работало, а сейчас решил побаловаться в Delphi и никак не могу портировать код туда |
|||
|
||||
mihail2244 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 2 Регистрация: 9.5.2013 Репутация: нет Всего: нет |
||||
|
||||
Isaev |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
Ведь можно запустить его в два потока (для каждой вершины свой) и проверять пересечение в общей вершине в процессе поиска.
Даст ли это реальный прирост скорости на больших графах? |
|||
|
||||
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |