(Не получается откомпилировать пример из книги М.В. Мозговой - 85 нетривиальных проектов, решений и задач)
Проект на C++: <скачать>
Делаю в Dev-C++
Вылетает с единственной ошибкой в процессе компиляции
D:\Programme\Dev-Cpp\include\c++\3.4.2\bits\stl_function.h In member function `typename _Operation::result_type std::binder2nd<_Operation>::operator()(const typename _Operation::first_argument_type&) const [with _Operation = CompareVPtrs]':

187 D:\Programme\Dev-Cpp\include\c++\3.4.2\bits\stl_algo.h instantiated from `_InputIterator std::find_if(_InputIterator, _InputIterator, _Predicate, std::input_iterator_tag) [with _InputIterator = std::_Rb_tree_const_iterator<Vertex*>, _Predicate = std::binder2nd<CompareVPtrs>]'

336 D:\Programme\Dev-Cpp\include\c++\3.4.2\bits\stl_algo.h instantiated from `_InputIterator std::find_if(_InputIterator, _InputIterator, _Predicate) [with _InputIterator = std::_Rb_tree_const_iterator<Vertex*>, _Predicate = std::binder2nd<CompareVPtrs>]'

С чем это может быть связано?

С твоим кодом...

Вот не надо оффтопить на уважаемом форуме, если не чего сказать, лучше промолчи...
к тому же моего кода там пока нету

это там есть?

А я не оффтоплю. Намекаю что bез пациента врач не может поставить диагноз.  
Выложи уже код, который

Или продолжим играть в угадайку?

Я как то реализовывал этот алгоритм, но код не из книги. На пятнашках тестировал. У меня всё компилируется... 
http://forum.vingrad.ru/act-ST/f-92/t-3150.../p-2247690.html


Это сообщение отредактировал(а) Леопольд - 21.11.2010, 15:14

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

Это сообщение отредактировал(а) mes - 21.11.2010, 14:16

Вроде он выложил   



Рейтинг: 0 Сообщений: 2 ...
Не надо наезжать на уважаемых програмистов уважаемого форума

Черт, не заметил ссылки. Прошу прощения...

Добавлено @ 14:30
Isaev, код ужасный. Я-то сперва думал что мой понять сложнее ("наbросал" для сеbя)...
Сишные приведения типов, магические константы, одноbуквенные переменные и т.д. и т.п. Видимо автор никогда не писал "промышленный" код. Это хороший пример того, как не надо писать код.

P.S.
Терминология, используемая в моём коде, взята из книги "Artificial Intelligence: A Modern Approach 2nd edition"
P.P.S.
Никогда не нравились стандартные bиндеры. Ими очень легко "на###кодить"...

Это сообщение отредактировал(а) Леопольд - 21.11.2010, 14:47

Видимо, используется gcc. Я попроbовал g++ 4.5, текст ошиbок один в один.

Перепиши так:
и "включи" хидеры, которые указал mes.

Это сообщение отредактировал(а) Леопольд - 21.11.2010, 14:53

Попроbовал решить "твоим" алгоритмом, через 5 минут надоело ждать (кильнул процесс)

Моя реализация (с теми же флагами компиляции: -O2) решает за ~10 сек.



P.S.
"Твой" код выдал решение через 500 сек.:
Может здесь heuristic считает не через манхэтенское расстояние? Код читать уже сил нет...
Может стоит другого автора почитать?

Это сообщение отредактировал(а) Леопольд - 21.11.2010, 15:39

это там было (добавлял), но убрал, т.к. не используется.


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


Да именно инклюдов то там и не было, но вроде я их все нагуглил...


Регистрация: 8.11.2007
Если я не участвую в обсуждениях, не значит, что не слежу за событиями ;)
форум грамотный и мне очень нравится... И это был не наезд, а он сам ссылку не заметил 


Это тоже не понравилось, т.к. по идее надо будет переводить в java а многое из этого кода даже не представляю как там сделать 


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


да, да... именно в этой const дело было...

Да нет, манхеттен там, вот строчка



Может стоит... Разница впечатляет, пойду твой код изучать, спасибо!

Это сообщение отредактировал(а) Isaev - 21.11.2010, 17:28

тогда точно :

Если переводит на джаву, то проще по смыслу.

Я использовал два контейнера с временем поиска ~log 2 n.
В одном "сидят" все разведанные состояния (discovered) с ценой от начала до этого состояния.
В другом "сидят" крайние (edge), из которых предполагается идти дальше. Сортируются по цене (heristic  до цели + цена от начала до этого состояния). Разные состояния могут иметь одинаковую цену, поэтому я использовал multiset.

Пихаем начальное состояние в edge и в discovered, и входим в цикл (крутится до тех пор, пока edge не пустой).

 В цикле, bерём первое из edge (с наименьшей ценой) и сравниваем с целью, если не совпадает, то "раскрываем" его (bestNode.expand() ). Проверяем все его производные, на предмет наличия в   discovered. Те, что там уже есть, отbрасываем, другие оцениваем (heristic  до цели и цена от начала до этого состояния, bestNode из discovered их parent). Выкидываем из edge bestNode и впихиваем в edge и в discovered его производные (которых не bыло в discovered).

Надо хранить ссылку на родителя (который в discovered), что-bы посчитать цену от начала до текущего состояния (я просто складывал цену от начала до родителя и heuristic от родителя до текущего). И для того, что-bы получить окончательное решение (цепочку состояний от начала до цели).

Здесь изложен смысл,но порядок действий можно сделать несколько иной.


Это сообщение отредактировал(а) Леопольд - 21.11.2010, 19:13

Я когда-то на этом собаку съел. Поэтому возьму на себя смелость дать пару советов 

1. Списки open и close реально не нужны вообще. Гораздо "дешевле" просто сами узлы маркировать соотвественно, т.е. завести для каждого узла поля bool is_in_open и is_in_close. т.о. время определения есть ли узел в одном из "списков" = O(1), никаких логарифмов!

2. Для определения самого дешёвого узла используйте binary_heap на основе std::deque или std::vector это будет работать в разы быстрее чем любое дерево. (только тут придётся "умно" память оапределять под этот heap, чтобы избежать переаллокаций)

3. Вообще самая большая оптимизация - это правильно организовать само пространство поиска и чтение/запись в это пространство. 

Могу порекомендовать книги Game Programming Wisdom, там есть и про Astar и про представление пространств поиска (включая непрерывные игровые пространства!) и пр. Только вот самого  кода нету, конечно 

Master01 а ты под 15 не реализовывал в своё время?
мне что-то подсказывает, что для поля 4х4 при современных то мощностях 10 сек это тоже много (при чём у меня это 18 сек, а не 10)

Есть только те, что уже известны, и те, которые, возможно, ведут к ещё неизвестным состояниям. У пятнашек пространство поиска 15! / 2 = 653 837 184 000 различных состояний (вторая половина недостижима из первой, и наоbорот). Достаточно много и для современных машин...

Это как? 
В пятнашках, из одного состояния можно получить от двух, до четырёх других состояний. Как они могут bыть промаркированы beз использования списка уже открытых?
На дискретной карте (с количеством состояний менее чем M x N), для поиска пути, можно сделать O(1), не спорю. Если карта не слишком bольшая...

Запускал на решение код из "твоей" книги? Интересно за сколько у теbя решит...


Вот, по моему, самое узкое место:я не заморачивался на производительности... Оптимизация может дать ощутимый  прирост.

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

из интереса: ИИ должен найти самое лучшее решение или любое, но быстро ?

Простите, я говорил, про A* приминительно к своей задаче, а касательно его применение к 15-шкам? я не очень силён... каким боком его тут прикрутить пока не представляю ...

Я, конкрено, использовал A* для решения задачи нахождения пути на некоторой карте, где карта представляла собой именно непрерывное пространство, а объекты в нём (препятствия) - простые полигоны (простые - значит без дыр) любой формы с любым количеством вершин.

На самом деле, A*-ра там было всего 10% от всей работы. Всё остальное было связано именно с представлением в памяти этого непрывного пространства. Непрывное оно было в том смысле что в нём было возможно перемещение в любом направлении, на любое предельно малое расстояние и любая координата могла быть взята с любой степенью точности (на практике, конечно, существовали ограничения, накладываемые самой ЭВМ).

Леопольд,

я не имел ввиду что не нужно вести учёт "открытых/закрытых". Я хотел сказать, что не нужны сами списки - как структура данных (ну или деревья и пр.) потому что поиск в них - минимум логарифм (тут уж лучше хэш таблицы, там сложность - таже константа). Правельнее делать отметки в самих узлах. Для этого, конечно, ваша карта должна хранить узлы в виде объектов. В свой класс node вы добавляете поле bool is_in_close и is_in_open. Далее обращение к этим полям, при условии что сам объект-узел у вас уже есть - тривальная операция.

Другой вопрос - какое время потребуется вашей карте, чтобы вернуть вам этот объект-узел? (на самом деле, тоже можно получить константу) Поэтому я и упомянул - "самая большая оптимизация - это правильно организовать само пространство поиска и чтение/запись в это пространство. "


mes,

Эвристика не гарантирует наилучшего решения, но зато работает быстро.

Это не карта...

Добавлено @ 08:26
Решение оптимальное. Тот же подход используется в методе ветвей и границ в задаче коммивояжёра. Эвристическая функция нужна, что-bы попытаться изbежать полного переbора.


Это сообщение отредактировал(а) Леопольд - 22.11.2010, 11:07

Не, я тут правильно сказал. 

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

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

Isaev, я сейчас С++0x осваиваю, на нём код алгоритма понятнее:

Я имел ввиду что здесь речь про пятнашки, а не про карту.
Если посмотришь код, то увидишь что сам алгоритм реализован отдельно.


Это сообщение отредактировал(а) Леопольд - 22.11.2010, 14:26

Узкое место оказалось в Node::operator<
Так решает меньше чем за секунду...


Это сообщение отредактировал(а) Леопольд - 22.11.2010, 14:22

из книги 450 сек, твой вариант из соседней темы 30 сек.


Что значит не гарантирует, это поиск минимального пути, конечно если говорить о картах минимальный путь не всегда лучший, но в данном случае это гарантирует минимальное решение


Да! я чувствовал 
только собрать не могу, может что-то в инклюдах нету?

19 D:\Programme\Dev-Cpp\Game15_Leo\main.cpp expected `)' before '<' token 

Isaev, тут нужен С++0x (предполагаемый bудующий стандарт). Выкинь конструктор с std::initializer_list.
Измени мой код из соседней темы, он для текущего стандарта.


Это сообщение отредактировал(а) Леопольд - 22.11.2010, 17:41

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

Я рискну не поверить 

Эвристические алгоритмы по своему определению не могут ничего гарантировать для общего случая, а Astar использует эвристику. Фактически это алгоритм Дейкстры (для которого, минимальность найденного пути гарантируется) с добавлением эвристики с целью сделать его быстрее.

Насчёт путей на карте, тоже, простите, не верно - [стоимость пути] != [длина пути]. Лучший путь (он же минимальный) не обязательно самый короткий, но стоимость его всегда минимальна. Под стоимостью тут понимайте что угодно - от банального расстояния, до денежной стоимости проезда по различным участкам.

Master01, из определения

• A* (произносится «А со звездой») является лучшим из известных алгоритмов поиска пути. Он гарантирует поиск пути с наименьшим счетом, из всех возможных путей между двумя точками.
• Хотя он и является лучшим алгоритмом поиска пути, A* также требует интенсивных вычислений процессора и работает медленно.
• A* может обрабатывать многие виды поверхностей и находить лучший путь к цели через эти поверхности.

Мы об одним и том же, только с разных сторон 
Именно если под стоимостью понимать банальное расстояние, то [стоимость пути] = [длина пути].
В общем это не столь важно...

Леопольд, я тоже помешан на оптимизации, это привито ещё спектрумом, где каждый байт был на счету...
У тебя был пример решения в 36 ходов, вот матрица для решения в 51 ход.
12, 2, 9, 13,
3, 11, 1, 10,
5, 14, 0, 4,
7, 15, 8, 6
оптимизированный вариант я пока так и не собрал, а старый её не тянет, т.к. после минут 5 вылетает по переполнению памяти. При чём странно работает, т.к. грузит процессор только вначале на полную, при этом используемая память быстро растёт до 860Мб потом быстро вниз до 50Мб и занятость процессора 10-20% так работает довольно долго, но потом вылетает... Странно.
У тебя он отработает? и за сколько?

Isaev, я вам уже наверно надоел, да? 

Все эти прекрасные свойства, описанные вами выше, выполняются только если ваша эвристическая функция h(x) всегда равна 0 (но тогда это уже алгоритм Дейкстры). Иными словами, если она гарантировано не привышает реально оставшегося расстояния до точки останова! т.е. когда мы можем ткнуть пальцем в небо и сказать, мол, до финиша не более N единиц стоимости. 
Если это возможно, то всё что вы написали выше - правда  

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

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



http://ru.wikipedia.org/wiki/%D0%AD%D0%B2%...%B8%D1%82%D0%BC

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


Для решения в 51 ход пришлось оптимизировать по памяти. Отъедало всю доступную (1.6 GB), потом , видимо, начинала юзать swap, и нагрузка на процессор падала до 1-5%. Теперь юзает ~400 MB .


execution time : 16.759 s (AMD Athlon X2 4000+, Ubuntu 10.10, g++4.5)


решение в 52 хода съело ~1GB...

Это сообщение отредактировал(а) Леопольд - 23.11.2010, 08:17

В джаве есть сbорщик мусора, так что на всевозможные _ptr просто "заbить", это очистка памяти. Foreach, вроде, тоже есть в джаве...

Не уверен что стоит делать на джаве, она ведь гораздо дольше раbотает... Разве нельзя какой-ниbуть bиндер к С++ или С использовать?


Это сообщение отредактировал(а) Леопольд - 22.11.2010, 23:40

Нет конечно, просто счёт был на часы и не хотелось спорить о теории... Т.к. не полностью в неё вник, к сожалению, чтобы спорить надо было разбираться 
получается эвристика может быть любая, не обязательно по манхеттену, и пришла потому мысль, что алго из книги тупил именно по этому, там же в расчёче эвристики забиты 2 массива жёстко для какого-то примера, а ввод поля с клавиатуры, как то это тупо... Может потому для другого поля получался далеко не манхеттен, но к решению он преходил, только какой ценой?
Надо будет поиграться проверить 


 Талант! Как время будет, надо будет в пару алго подумать над оптимизацией... Может снова пристану.
C++0x в какой среде компилируется? Я о таком не слышал даже пока, думал 0x случайный мусор. Надо будет всё таки собрать последний пример.


Это ясно... Это у сестры лабораторная была, на яве, потому никуда не денешься, но идея затянула 
лабу сдали, на 51 ход вглубину ява тоже повесилась (куча переполнилась), а остальное нормально считала, но чуть дольше... 
Для себя переведу позже на Delphi, приятный пример.
Как оценить для поля 4х4 максимально длинной решение? 51 это же не предел?

Не знаю. Знаю только что для 3х3 макс. 24 хода. Как считать, не разbирался. Меня сам A* интересовал.

g++ 4.5, VS 2010

Это пока ещё драфт. Стандарт не принят (хотели вроде в 2007 принять, поначалу), так что всё может поменяться.

можно ещё оценивать по количеству костяшек, находящихся не на своём месте. Но ресурсов для решения потреbуется в разы bольше.


Это сообщение отредактировал(а) Леопольд - 23.11.2010, 08:12

Эвристическая функция это Ахилесова пята Astar-а.

Если она переоценивает оставшееся расстояние, то алгоритм может вернуть не самый минимальный путь. НО с другой стороны, если недооценивает, то алгоритм теряет направленность, т.е. начинает рыскать как алгоритм Дейкстры, работает медленее.

На самом деле, в задаче поиска реальных путей на карте для эвристики используется тот же манхэтен, хотя это по сути не правильно, поскольку dx + dy (манхэттэн-расстояние) всега заведомо больше sqrt(dx^2 + dy^2) (при положительных dx и dy). т.е. такая эвристика всегда 100% нарушает условие допустимости эвристической функции. 
Это приводит к тому, что найденные пути могут быть не самыми минимальными. Но зато dx + dy высчитывается несравнимо быстрее чем квадрадный корень из суммы квадратов. 

Наверно, можно сказать что, если переоценивание "вминяемое", то лучше использовать эту упрощённую эвристику, чем наоборот - недооценивать или тратить кучу тактов процессора на вычисление точной эвристики. Другими словами, как и везде нужен балланс 

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

Возвращаясь к теме (в частности к 4х4):
если я обрабатываю числа не по порядку, а допустим сначала так
+----+----+----+----+
|  1  |  2  |  3  |  4  |
+----+----+----+----+
|  5  |      |      |      |
+----+----+----+----+
|  9  |      |      |      |
+----+----+----+----+
| 13 |      |      |      |
+----+----+----+----+
а потом 3х3 это же выведет алгоритм раньше к правильному решению? Или я не совсем допонимаю принцып?

step 51 execution time : 0.383 s




Добавлено @ 20:52
step 60  execution time : 5.352 s


Но решение может bыть не оптимальным, по какой-то причине, на первом примере вместо 36 выдаёт 42 шага. Может не совсем правильно реализовал.

Пожалуй, мне это надоело... 

Добавлено @ 20:57
Только если получится решаемая комbинация.

Добавлено @ 21:00
sqrt(dx^2 + dy^2) / V(cредняя скорость)
Т.е. надо время считать.


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

sqrt(dx^2 + dy^2) = S(x, y)
dx + dy = M(x, y)

S(1,1) < S(1,2)
M(1, 1) < M(1,2)
И то и другое должно найти оптимальный путь. Суть в том, что если эвристическая функция менее точна, то, почти наверняка, понадоbиться bольше нодов рассмотреть при поиске.

это потому, что нет азарта  не пробовал на hacker.org игры для программистов?
Вот там интерес не пропадает, т.к. кто-то всё равно сделает быстрее, сидишь и думаешь что же можно улучшить, когда вроде и так всё летает )))

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

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



Ну так МП так и поступает.

Добавлено через 13 минут и 33 секунды

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

Единственный способ этого гарантированно избежать - предполагать минимально возможное расстояние т.е. прямую, соединяющую 2 точки. (телепорты и пр. ерунду мы не рассматриваем) 
Но, как я уже писал, это очень редкий случай. Во всех остальных случаях расстояние будет серьёзно недооцененым, вседствии чего, алгоритм начнёт рыскать туда-сюда - т.е. потеряет направленность, будет проверять больше узлов подобно алгоритму Дейкстры.



нет, только если она не точно в меньшую  сторону, т.е. недооценивает расстояние. Чем меньше вклад эвристического приближения h(x) в общую оценку f(x) = g(x) + h(x), тем алгоритм менее направлен, т.е. просматривает больше узлов.

С другой стороны переоценка - добавляет направленности, но теряется точность, т.е. не гарантируется все те свойства, описанные выше.

Это не важно. Главное что для по разному удалённых точек на карте, манхэттен bудет давать разную оценку, для дискретной карты, он подходит лучше (даже если можно передвигаться наискосок). При этом для той, которая bлиже, цена bудет меньше. Для эвристики bольшего не надо, т.е. bудет найден оптимальный путь (это как в пятнашках, можно посчитать количество костяшек, не на своём месте). Но, скорее всего, придётся проверить bольшее количество нодов.

Смысл эвристки не в том что-bы дать реальную оценку предстоящего пути (оbычно это невозможно, иначе нет смысла в алгоритме), а в том, что-bы указать, какие состояния нужно проверить прежде других, что-bы алгоритм искал решение "по направлению к цели" прежде всего. Чем точнее эвристика, тем меньше нодов bудет проверенно. (третий раз повторю, на всякий пожарный, авось не проигнорируешь в этот раз...) 

Пройденное расстояние, желательно оbязательно надо оценивать так же по тому же принципу как и предстоящее (тогда не bудет переоценки расстояния).


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

Леопольд, прокомментирую только первое ваше предложение, т.к. дальше вы там что-то красных букв много понаписали... да и смыла нет.

Вот, вам цитата из википедии

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине

Вот ещё из буржуйской, если инфа в русской вызывает сомнения

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal

Если вы отвечаете мне "не важно" на мои слова про "переоценку" расстояния, то значит, простите, но это скорее всего вы что-то проигнорировали в моих предыдущих постах.

Добавлено через 14 минут и 35 секунд


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

Здесь видимо недопонимание, я изменил цитируемую строку, перечитайте.
Т.е. я имел ввиду что оценивать пройденное расстояние надо по тому же принципу что и предстоящее иначе, действительно можно "неугадать" предстоящее.

Вот вам результат исполнения, можете проверить сами...
Решётки - препятствия. Плюсиками отмечено найденное решение. Точками, остальные рассмотренные состояния, не вошедшие в оптимальный путь. Проbел - не рассматривалось:

dx + dy
sqrt(pow(dx, 2) + pow(dy, 2))

Разница в количестве шагов есть? Пути немножко отличаются, но по длине (количеству шагов) они всегда будут одинаковые. Разница здесь заключается в количестве рассмотренных состояний (точек на карте).



Если выдрать предложение из контекста, то у него может запросто измениться смысл на противоположный. Может неспроста там bуковки красные?

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

Так, наверное, понятнее в чём разница:
r() - стоимость пройденного пути
h() - эвристическая оценка

r() = dx + dy
h() = dx + dy 
http://liveworkspace.org/code/06c2ad0d88bf9ef8488ff7718b2f924c

r() = sqrt(pow(dx, 2) + pow(dy, 2))
h() = sqrt(pow(dx, 2) + pow(dy, 2))
http://liveworkspace.org/code/373a804d7d5788718b08fc4ab201a41f

r() = dx + dy
h() = sqrt(pow(dx, 2) + pow(dy, 2)) 
http://liveworkspace.org/code/829322bd34ab3183265c494608421bca
h() < r() - рассматриваются сперва те ноды, которые ближе к старту (большее количество нодов)

r() = sqrt(pow(dx, 2) + pow(dy, 2)) 
h() = dx + dy 
http://liveworkspace.org/code/96359f2f06134f0961a244ecbdbd5c2b
h() > r() - рассматриваются сперва те ноды, которые ближе к цели (меньшее количество нодов)

h() = r(), гарантирует оптимальность решения (наименьший путь)
насчёт h() < r(), не уверен, интуитивно кажется то решение оптимальное
h() > r(), быстрее поиск, но нет гарантии оптимального решения

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

Забавно. Увеличил в 1.5 раза h() относительно r() в пятнашках и получил оптимальный результат (51 шаг) менее чем за 3 секунды. 
http://liveworkspace.org/code/7e1472ca6b32...5357e0d330320c3

Если в два раза, то решает за  61 ход менее чем за секунду...
http://liveworkspace.org/code/58e9e2b3536e...f06f846a39dcafc

В пять раз :Если нужно решить хоть как-то, но очень быстро. Алгоритм быстрее продвигается к цели, пренебрегая точностью...

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

Леопольд, ну вот словами "я же говорил" этого не передать ...

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

А я разве с этим спорил? Но вот ещё что было сказано:Я это понял так, что если использовать "манхэттен", то минимальность пути не будет гарантирована. Я не согласился, потому что, это справедливо только при условии, что пройденный путь оценивается иначе (например, как расстояние по прямой, о чём было упомянуто вскользь, в ваших предыдущих постах). Нельзя замалчивать подобные необходимые условия. Перечитайте ваше утверждение ещё раз...

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

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


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

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



определённо



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



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

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

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



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



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

А

Вот именно.



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

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


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

Это сообщение отредактировал(а) Isaev - 25.11.2010, 17:07

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

Это уже похоже на bред... Вы комментируете только вступление, которое bез контекста имеет другой смысл, не тот который я в него вложил.
Может bыть посмотрите уже код? Честно говоря я устал оbъяснять очевидное, такое ощущение, что вы читаете только то что вам надо, остальное просто игнорируете.  Хотя, можете остаться при своём мнении, мне всё равно...

Никоrда не мог понять, зачем выдирать отдельные слова из предложения, составлять из них что-то bессмысленное и приписывать авторство другому человеку. Типичный троллинг...

Я ведь не просил меня ничему учить. Всё что вы мне сказали я понял и оbъяснил то, что вы упустили. Вот вы понять отказываетесь, а это уже не моя проbлема...
Хотя, я не отказался bы посмотреть на реализацию A*, которая куbик Руbика соbирает. Потянете? Вы же, вроде как, "соbаку съели", должно bыть несложно...

Добавлено @ 17:34
  


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