|
Модераторы: Daevaorn |
|
Isaev |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
(Не получается откомпилировать пример из книги М.В. Мозговой - 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>]' С чем это может быть связано? |
|||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
-------------------- вопросов больше чем ответов |
|||
|
||||
Isaev |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
||||
|
||||
mes |
|
|||
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
это там есть? |
|||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
А я не оффтоплю. Намекаю что bез пациента врач не может поставить диагноз.
Выложи уже код, который Или продолжим играть в угадайку? Я как то реализовывал этот алгоритм, но код не из книги. На пятнашках тестировал. У меня всё компилируется... http://forum.vingrad.ru/act-ST/f-92/t-3150.../p-2247690.html Это сообщение отредактировал(а) Леопольд - 21.11.2010, 15:14 -------------------- вопросов больше чем ответов |
|||
|
||||
mes |
|
|||
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
мне просто лень скачивать.. учитывая вышенаписанное, автор не изменял в коде "из книжки" ничего.. а значит скорей всего либо инклудов не хватает, либо компилятор не подходит.. так что в самом коде пока в принципе и смотреть нечего.. Это сообщение отредактировал(а) mes - 21.11.2010, 14:16 |
|||
|
||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
||||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
Черт, не заметил ссылки. Прошу прощения...
Добавлено @ 14:30 Isaev, код ужасный. Я-то сперва думал что мой понять сложнее ("наbросал" для сеbя)... Сишные приведения типов, магические константы, одноbуквенные переменные и т.д. и т.п. Видимо автор никогда не писал "промышленный" код. Это хороший пример того, как не надо писать код. P.S. Терминология, используемая в моём коде, взята из книги "Artificial Intelligence: A Modern Approach 2nd edition" P.P.S. Никогда не нравились стандартные bиндеры. Ими очень легко "на###кодить"... Это сообщение отредактировал(а) Леопольд - 21.11.2010, 14:47 -------------------- вопросов больше чем ответов |
|||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
Видимо, используется gcc. Я попроbовал g++ 4.5, текст ошиbок один в один.
Перепиши так:
Это сообщение отредактировал(а) Леопольд - 21.11.2010, 14:53 -------------------- вопросов больше чем ответов |
|||
|
||||
Леопольд |
|
||||||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
Попроbовал решить "твоим" алгоритмом, через 5 минут надоело ждать (кильнул процесс) Моя реализация (с теми же флагами компиляции: -O2) решает за ~10 сек.
P.S. "Твой" код выдал решение через 500 сек.:
Может стоит другого автора почитать? Это сообщение отредактировал(а) Леопольд - 21.11.2010, 15:39 -------------------- вопросов больше чем ответов |
||||||
|
|||||||
Isaev |
|
||||||||||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
это там было (добавлял), но убрал, т.к. не используется. ну так я ж сразу выложил в первом посте, сам не люблю когда надеются на экстрасенсовские способности
Да именно инклюдов то там и не было, но вроде я их все нагуглил...
Регистрация: 8.11.2007 Если я не участвую в обсуждениях, не значит, что не слежу за событиями ;) форум грамотный и мне очень нравится... И это был не наезд, а он сам ссылку не заметил Это тоже не понравилось, т.к. по идее надо будет переводить в java а многое из этого кода даже не представляю как там сделать
Он у меня только потому стоит, что не требует переустановки, после сноса винды, а на си я обычно под линуксом кодю, а в виндовсе чаще на дельфи да, да... именно в этой const дело было...
Да нет, манхеттен там, вот строчка
Может стоит... Разница впечатляет, пойду твой код изучать, спасибо! Это сообщение отредактировал(а) Isaev - 21.11.2010, 17:28 |
||||||||||
|
|||||||||||
mes |
|
|||
любитель Профиль Группа: Участник Клуба Сообщений: 7954 Регистрация: 14.1.2006 Репутация: 144 Всего: 250 |
тогда точно : |
|||
|
||||
Леопольд |
|
|||
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
Я использовал два контейнера с временем поиска ~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 -------------------- вопросов больше чем ответов |
|||
|
||||
Master01 |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 89 Регистрация: 22.8.2007 Репутация: 2 Всего: 2 |
Я когда-то на этом собаку съел. Поэтому возьму на себя смелость дать пару советов
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 и про представление пространств поиска (включая непрерывные игровые пространства!) и пр. Только вот самого кода нету, конечно |
|||
|
||||
Isaev |
|
|||
Шустрый Профиль Группа: Участник Сообщений: 125 Регистрация: 8.11.2007 Где: Germany Репутация: нет Всего: нет |
Master01 а ты под 15 не реализовывал в своё время?
мне что-то подсказывает, что для поля 4х4 при современных то мощностях 10 сек это тоже много (при чём у меня это 18 сек, а не 10) |
|||
|
||||
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |