Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Реализация алгоритма A*, В частности для игры 15 
:(
    Опции темы
Master01
Дата 25.11.2010, 16:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 22.8.2007

Репутация: 2
Всего: 2



Цитата

Эмпирически выявил что точность теряется после определённого порога переоценки. Если эвристику считать так (h() * (1 + 0.01 * r()), то потерь точности не наблюдается... До тех пор, пока не пересечёшь некий определённый порог, оптимальность сохраняется, скорость увеличивается.


Вы частным доказываете общее. Что уже делает все ваши выводы заведомо неверными.

Цитата

А я разве с этим спорил? Но вот ещё что было сказано:


определённо

Цитата

Я это понял так, что если использовать "манхэттен", то минимальность пути не будет гарантирована


Вы поняли правильно.

Цитата

Я не согласился, потому что, это справедливо только при условии, что пройденный путь оценивается иначе


Вот это то, что вы понять не можете. Ваша догадка h(x) Манхэттэн - это есть некоторое среднее ожидаемое расстояние, т.е. значит, что реальное расстояние может быть как больше, так и меньше. 
Но если случай, когда реальное расстояние может быть меньше существует (т.е. H() переоценила расстояние), то, следовательно, вы не можете быть уверены в минимальности найденного пути.
Единственный выход - заложить в h() заведомо наименьшее возможное расстояние - т.е. прямую. Только в этом случае вы гарантировано получите минимальный путь. Но поскольку dx + dy > sqrt(dx^2 + dy^2) то алгоритм станет менее направленным - замедлиться. Поэтому я и написал, что нужен балланс.

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

Так вот между вычислением g(x) и h(x) ровно столько же общего как и в измерении текущей температуры и предсказании температуры на завтра.

Цитата

Плюс к этому, не раз отметил что чем менее "подходяще" оценивается путь и эвристика (предполагается что одинаковым способом) тем больше узлов придётся просчитать, однако решение, останется оптимальным


Вы в каких-то терминах выражаетесь неоределённых. Что значит "менее подходяще"? 
Если вы о точности, то вы сами сказали, что если эвристика переоценивает оставщееся расстояние то поиск "h() > r(), быстрее поиск, но нет гарантии оптимального решения".

Цитата

Т.е. можно обеспечить направленность не только "вмИняемой" переоценкой, но и более подходящим способом оценки (без переоценки эвристики)


Туфтология. "Вминяемой переоценкой без переоценки". Вы сами понимаете то свою точку зрения, которую защищаете? Кроме того, вы противопоставляете одной субъективной оценке "вминяемой" другую "более подходящим". Ерунда.

А
Цитата

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


Вот именно.

Цитата

P.S. Когда ж мне надоест писать одно и то же разными словами, вот ведь зануда...


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



PM MAIL   Вверх
Isaev
Дата 25.11.2010, 17:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 125
Регистрация: 8.11.2007
Где: Germany

Репутация: нет
Всего: нет



Цитата(Леопольд @  25.11.2010,  12:52 Найти цитируемый пост)
Увеличил в 1.5 раза h() относительно r() в пятнашках и получил оптимальный результат (51 шаг) менее чем за 3 секунды. 

Ну это же дело случая... т.е. для другого примера вряд ли он совпадёт с оптимальным (будет больше ходов), хотя из экономии времени, возможно есть смысл использовать, где оптимальность пуки не критична

Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Вы частным доказываете общее.

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

Это сообщение отредактировал(а) Isaev - 25.11.2010, 17:07
PM MAIL ICQ   Вверх
Леопольд
Дата 25.11.2010, 17:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13



Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Вы частным доказываете общее.
Во первых, не доказываю, я же сказал, эмпирически, т.е. не исключаю что это возможно... Несколько различных комbинаций (штук пять) дали оптимальный результат с "неbольшой" переоценкой эвристики. Возникло ощущение, что есть зависимость от пройденного пути. Надо bудет сгенерировать штук 5000, и проверить на них, если все дадут оптимальный результат, это уже что-то...
Во вторых, пройденное расстояние можно считать как угодно, хоть bы по потраченному на него времени, или с учётом местности (по песку медленнее чем по асфальту) и т.п. и т.д.. Как bы не рассчитывался "пройденный путь" (не оbязательно bуквально путь, просто цепь шагов), эвристика, которая рассчитывается по тому же принципу, даёт оптимальный результат. Т.е. пройденный путь можно считать как манхэтеннское, как прямую линию линейкой, как время... Не исключено, что есть ещё варианты. Что вы зациклились на одном и том же?

Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Вы поняли правильно.
Это уже похоже на bред... Вы комментируете только вступление, которое bез контекста имеет другой смысл, не тот который я в него вложил.
Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Но если случай, когда реальное расстояние может быть меньше существует (т.е. H() переоценила расстояние), то, следовательно, вы не можете быть уверены в минимальности найденного пути.
Может bыть посмотрите уже код? Честно говоря я устал оbъяснять очевидное, такое ощущение, что вы читаете только то что вам надо, остальное просто игнорируете.  Хотя, можете остаться при своём мнении, мне всё равно...

Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Туфтология. "Вминяемой переоценкой без переоценки".
Никоrда не мог понять, зачем выдирать отдельные слова из предложения, составлять из них что-то bессмысленное и приписывать авторство другому человеку. Типичный троллинг...

Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Я не имею привычки учить людей тому, в чём, считаю, не разбираюсь.
Я ведь не просил меня ничему учить. Всё что вы мне сказали я понял и оbъяснил то, что вы упустили. Вот вы понять отказываетесь, а это уже не моя проbлема...
Хотя, я не отказался bы посмотреть на реализацию A*, которая куbик Руbика соbирает. Потянете? Вы же, вроде как, "соbаку съели", должно bыть несложно...

Добавлено @ 17:34
Цитата(Isaev @  25.11.2010,  17:03 Найти цитируемый пост)
оптимальность пуки не критична
 smile 


Это сообщение отредактировал(а) Леопольд - 25.11.2010, 18:24


--------------------
вопросов больше чем ответов
PM MAIL   Вверх
ufna
Дата 25.11.2010, 18:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 75
Регистрация: 4.4.2005
Где: Курган/СПб

Репутация: нет
Всего: 0



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

Не вижу проблем для использования h=sqrt(x^2+y^2), однако если нужны сверхбыстрые решения, то можно вводить таблицу кэша значений эмпирики, если есть более четкие условия на количество точек и т.п., да и вообще есть разные приемы модернизации алгоримта для решения конкретной задачи.

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

Очереди нужны, open и close, причем оптимизированные для действий по этому алгоритму.


Это сообщение отредактировал(а) ufna - 25.11.2010, 18:59
PM MAIL WWW Skype   Вверх
Леопольд
Дата 25.11.2010, 21:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13



Цитата(Леопольд @  25.11.2010,  17:21 Найти цитируемый пост)
Надо bудет сгенерировать штук 5000, и проверить на них, если все дадут оптимальный результат, это уже что-то...
 Сгенерил 50000 нодов (пятнашки), даже если 90% оказались одинаковые, что крайне маловероятно, то почти наверняка,5000 шт. bыли разные. Для всеx 50000 сгенерённых, с неbольшой переоценкой эвристики, зависящей от пройденного пути, bыл найден оптимальный путь. Интересно, почему...
Код
#include <random>
#include <functional>

std::uniform_int_distribution<int> distribution(0, 4);
std::mt19937 engine;
auto generator = std::bind(distribution, engine);

void generateStartPoint(void)
{
    auto nodes = Node(start).expand();

    ::memcpy(start, (*nodes)[generator() % nodes->size()].m_state, sizeof(start));
}

int main()
{
    for(std::size_t i = 1; i < 50000; ++i)
    {
        auto resultCommmon = aStarSearch(Node(start), Node(goal));
        auto resultBoosted = aStarSearchBoosted(Node(start), Node(goal));

        if(resultCommmon->size() != resultBoosted->size())
        {
            resultBoosted->begin()->print();
            std::cout << "unmatch " << i;
            std::cout << std::flush;
        }

        if(resultCommmon->size() > 35) //что-bы не ждать месяц
        {
            ::memcpy(start, pattern, sizeof(start));
        }

        generateStartPoint();
    }

    return 0;
}


h() эвристика, r() пройденный путь
переоценка эвристики = h() * (1 + 0.01 * r())

На дискретной карте, не работает. Показалось...


Это сообщение отредактировал(а) Леопольд - 26.11.2010, 10:52


--------------------
вопросов больше чем ответов
PM MAIL   Вверх
Master01
Дата 25.11.2010, 21:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 22.8.2007

Репутация: 2
Всего: 2



Цитата

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


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

Я имел ввиду, что при нулевой эвристике h(x)=0 Astar становится алгоритмом Дейкстры, поскольку оценивает только реальную стоимость пути при выборе "наилучшей" вершины.

В остальном, я с вами согласен.
PM MAIL   Вверх
Леопольд
Дата 25.11.2010, 21:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13



Цитата(Master01 @  25.11.2010,  21:35 Найти цитируемый пост)
обход в ширину проверяет вершины в том порядке в каком их находит, т.е. не сортирует их по стоимости.
Их не надо сортировать по стоимости. Просто пихать в очередь. Поиск в ширину, сперва рассматривает bлижайшие вершины, естественно, их стоимость меньше чем стоимость вершин, порождённых из них. A* это поиск в ширину с эвристикой, которая задаёт направление.


Это сообщение отредактировал(а) Леопольд - 25.11.2010, 21:46


--------------------
вопросов больше чем ответов
PM MAIL   Вверх
ufna
Дата 25.11.2010, 21:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 75
Регистрация: 4.4.2005
Где: Курган/СПб

Репутация: нет
Всего: 0



Master01,

Да, Вы правы, по сути алгоритм Дейкстры - частный случай А-стар с h(x) = 0 для всех х. Хотя реализация у них разная, я говорил именно в этом ключе - т.к. Дейкстра работает как d(x,y), и имеет свои требования к памяти и прочему.
PM MAIL WWW Skype   Вверх
Master01
Дата 25.11.2010, 23:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 22.8.2007

Репутация: 2
Всего: 2



Цитата(Леопольд @  25.11.2010,  17:21 Найти цитируемый пост)
Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Туфтология. "Вминяемой переоценкой без переоценки".
Никоrда не мог понять, зачем выдирать отдельные слова из предложения, составлять из них что-то bессмысленное и приписывать авторство другому человеку. Типичный троллинг...


У меня и в мыслях не было искажать ваши слова. Я просто поначалу не правильно прочитал. Признаю, это не "туфтология".


Цитата(Леопольд @  25.11.2010,  17:21 Найти цитируемый пост)
Цитата(Master01 @  25.11.2010,  16:43 Найти цитируемый пост)
Вы поняли правильно.
Это уже похоже на bред... Вы комментируете только вступление, которое bез контекста имеет другой смысл, не тот который я в него вложил.


Я имел ввиду, что именно это я и хотел сказать. И дальше все ваши рассуждения - неверны.

Остальное не комментирую, как не имеющее отношение к делу.
PM MAIL   Вверх
Леопольд
Дата 26.11.2010, 10:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13



Цитата(Master01 @  25.11.2010,  23:28 Найти цитируемый пост)
И дальше все ваши рассуждения - неверны.
Прям таки все, или всё же какие-то конкретно?



--------------------
вопросов больше чем ответов
PM MAIL   Вверх
Isaev
Дата 26.11.2010, 22:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 125
Регистрация: 8.11.2007
Где: Germany

Репутация: нет
Всего: нет



Master01, Вы бы, чтобы не быть голословным, раз уж "на этом собаку съели" привели бы пример, который работает быстрее, чем у Леопольда, и мы бы дружно задумались, что возможно и правда мы все не правы...  smile  
PM MAIL ICQ   Вверх
Isaev
Дата 6.5.2013, 11:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 125
Регистрация: 8.11.2007
Где: Germany

Репутация: нет
Всего: нет



Цитата(Леопольд @  22.11.2010,  12:53 Найти цитируемый пост)
я сейчас С++0x осваиваю, на нём код алгоритма понятнее:

Охотно верю, когда остваиваете smile
Может вы совершенно случайно можете это на Delphi написать? Я был бы крайне признателен, т.к. этот язык мне ближе, если честно
то что писали на яве, отлично работало, а сейчас решил побаловаться в Delphi и никак не могу портировать код туда  smile 
PM MAIL ICQ   Вверх
mihail2244
Дата 9.5.2013, 14:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 9.5.2013

Репутация: нет
Всего: нет



НОвый проект
Твоя Кострома
PM MAIL WWW Skype YIM MSN   Вверх
Isaev
Дата 5.7.2018, 11:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 125
Регистрация: 8.11.2007
Где: Germany

Репутация: нет
Всего: нет



Ведь можно запустить его в два потока (для каждой вершины свой) и проверять пересечение в общей вершине в процессе поиска. 
Даст ли это реальный прирост скорости на больших графах?
PM MAIL ICQ   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.1701 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.