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

Поиск:

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


Шустрый
*


Профиль
Группа: Участник
Сообщений: 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>]'

С чем это может быть связано?
PM MAIL ICQ   Вверх
Леопольд
Дата 21.11.2010, 12:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(Isaev @  20.11.2010,  23:35 Найти цитируемый пост)
С чем это может быть связано?
С твоим кодом...



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


Шустрый
*


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

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



Цитата(Леопольд @  21.11.2010,  12:32 Найти цитируемый пост)
С твоим кодом...

Вот не надо оффтопить на уважаемом форуме, если не чего сказать, лучше промолчи...
к тому же моего кода там пока нету
PM MAIL ICQ   Вверх
mes
Дата 21.11.2010, 14:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

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



Код

#include <functional>
#include <algorithm>

это там есть?


--------------------
PM MAIL WWW   Вверх
Леопольд
Дата 21.11.2010, 14:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(Isaev @  21.11.2010,  13:47 Найти цитируемый пост)
Вот не надо оффтопить
А я не оффтоплю. Намекаю что bез пациента врач не может поставить диагноз.  smile
Выложи уже код, который
Цитата(Isaev @  20.11.2010,  23:35 Найти цитируемый пост)
Вылетает с единственной ошибкой в процессе компиляции


Или продолжим играть в угадайку?
Цитата(mes @  21.11.2010,  14:00 Найти цитируемый пост)
это там есть? 


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


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


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


любитель
****


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

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



Цитата(Леопольд @  21.11.2010,  13:10 Найти цитируемый пост)
Выложи уже код, который

Цитата(Isaev @  20.11.2010,  22:35 Найти цитируемый пост)
Проект на C++: <скачать>



Цитата(Леопольд @  21.11.2010,  13:10 Найти цитируемый пост)
Или продолжим играть в угадайку?
мне просто лень скачивать..
 учитывая вышенаписанное, автор не изменял в коде "из  книжки" ничего.. а значит скорей всего либо инклудов не хватает, либо компилятор не подходит.. так что в самом коде пока в принципе и смотреть нечего..
 smile 

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


--------------------
PM MAIL WWW   Вверх
sQu1rr
Дата 21.11.2010, 14:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(Isaev @  20.11.2010,  23:35 Найти цитируемый пост)
Проект на C++: <скачать>


Цитата(Леопольд @  21.11.2010,  14:10 Найти цитируемый пост)
Выложи уже код


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


Цитата(Isaev @  21.11.2010,  13:47 Найти цитируемый пост)
Вот не надо оффтопить на уважаемом форуме, если не чего сказать, лучше промолчи...

Рейтинг: 0 Сообщений: 2 ...
Не надо наезжать на уважаемых програмистов уважаемого форума
PM MAIL Skype GTalk   Вверх
Леопольд
Дата 21.11.2010, 14:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(mes @  21.11.2010,  14:14 Найти цитируемый пост)
мне просто лень скачивать..
Черт, не заметил ссылки. Прошу прощения...

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

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

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


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


Опытный
**


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

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



Цитата(mes @  21.11.2010,  14:14 Найти цитируемый пост)
либо компилятор не подходит
Видимо, используется gcc. Я попроbовал g++ 4.5, текст ошиbок один в один.

Перепиши так:
Код
//функция для сравнения содержимого двух вершин, адресуемых указателями
struct CompareVPtrs:public binary_function<Vertex*,Vertex*,bool>
{
       bool operator()(Vertex *lhs, Vertex *rhs) const
       {
              //сравнить содержимое массивов lhs->State и rhs-State
              return equal((int *)lhs->State, (int *)lhs->State + 16,(int *)rhs->State);
       }
}
CompareVP;
и "включи" хидеры, которые указал mes.

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


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


Опытный
**


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

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



Код

  1 12  3  7
 15  2 14  4
  5  6 10  8
  9 13 11  0


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

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

Код

step 0
  1 12  3  7
 15  2 14  4
  5  6 10  8
  9 13 11   
step 1
  1 12  3  7
 15  2 14  4
  5  6 10  8
  9 13    11
step 2
  1 12  3  7
 15  2 14  4
  5  6     8
  9 13 10 11
step 3
  1 12  3  7
 15  2     4
  5  6 14  8
  9 13 10 11
step 4
  1 12  3  7
 15  2  4   
  5  6 14  8
  9 13 10 11
step 5
  1 12  3   
 15  2  4  7
  5  6 14  8
  9 13 10 11
step 6
  1 12     3
 15  2  4  7
  5  6 14  8
  9 13 10 11
step 7
  1    12  3
 15  2  4  7
  5  6 14  8
  9 13 10 11
step 8
  1  2 12  3
 15     4  7
  5  6 14  8
  9 13 10 11
step 9
  1  2 12  3
    15  4  7
  5  6 14  8
  9 13 10 11
step 10
  1  2 12  3
  5 15  4  7
     6 14  8
  9 13 10 11
step 11
  1  2 12  3
  5 15  4  7
  9  6 14  8
    13 10 11
step 12
  1  2 12  3
  5 15  4  7
  9  6 14  8
 13    10 11
step 13
  1  2 12  3
  5 15  4  7
  9  6 14  8
 13 10    11
step 14
  1  2 12  3
  5 15  4  7
  9  6     8
 13 10 14 11
step 15
  1  2 12  3
  5 15  4  7
  9  6  8   
 13 10 14 11
step 16
  1  2 12  3
  5 15  4   
  9  6  8  7
 13 10 14 11
step 17
  1  2 12  3
  5 15     4
  9  6  8  7
 13 10 14 11
step 18
  1  2     3
  5 15 12  4
  9  6  8  7
 13 10 14 11
step 19
  1  2  3   
  5 15 12  4
  9  6  8  7
 13 10 14 11
step 20
  1  2  3  4
  5 15 12   
  9  6  8  7
 13 10 14 11
step 21
  1  2  3  4
  5 15 12  7
  9  6  8   
 13 10 14 11
step 22
  1  2  3  4
  5 15 12  7
  9  6     8
 13 10 14 11
step 23
  1  2  3  4
  5 15     7
  9  6 12  8
 13 10 14 11
step 24
  1  2  3  4
  5    15  7
  9  6 12  8
 13 10 14 11
step 25
  1  2  3  4
  5  6 15  7
  9    12  8
 13 10 14 11
step 26
  1  2  3  4
  5  6 15  7
  9 10 12  8
 13    14 11
step 27
  1  2  3  4
  5  6 15  7
  9 10 12  8
 13 14    11
step 28
  1  2  3  4
  5  6 15  7
  9 10     8
 13 14 12 11
step 29
  1  2  3  4
  5  6     7
  9 10 15  8
 13 14 12 11
step 30
  1  2  3  4
  5  6  7   
  9 10 15  8
 13 14 12 11
step 31
  1  2  3  4
  5  6  7  8
  9 10 15   
 13 14 12 11
step 32
  1  2  3  4
  5  6  7  8
  9 10 15 11
 13 14 12   
step 33
  1  2  3  4
  5  6  7  8
  9 10 15 11
 13 14    12
step 34
  1  2  3  4
  5  6  7  8
  9 10    11
 13 14 15 12
step 35
  1  2  3  4
  5  6  7  8
  9 10 11   
 13 14 15 12
step 36
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15


P.S.
"Твой" код выдал решение через 500 сек.:
Код

  1 12  3  7
 15  2 14  4
  5  6 10  8
  9 13 11  0

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 0 

1 2 3 4 
5 6 7 8 
9 10 11 0 
13 14 15 12 

1 2 3 4 
5 6 7 8 
9 10 0 11 
13 14 15 12 

1 2 3 4 
5 6 7 8 
9 10 15 11 
13 14 0 12 

1 2 3 4 
5 6 7 8 
9 10 15 11 
13 14 12 0 

1 2 3 4 
5 6 7 8 
9 10 15 0 
13 14 12 11 

1 2 3 4 
5 6 7 0 
9 10 15 8 
13 14 12 11 

1 2 3 0 
5 6 7 4 
9 10 15 8 
13 14 12 11 

1 2 0 3 
5 6 7 4 
9 10 15 8 
13 14 12 11 

1 2 7 3 
5 6 0 4 
9 10 15 8 
13 14 12 11 

1 2 7 3 
5 6 15 4 
9 10 0 8 
13 14 12 11 

1 2 7 3 
5 6 15 4 
9 10 12 8 
13 14 0 11 

1 2 7 3 
5 6 15 4 
9 10 12 8 
13 0 14 11 

1 2 7 3 
5 6 15 4 
9 0 12 8 
13 10 14 11 

1 2 7 3 
5 0 15 4 
9 6 12 8 
13 10 14 11 

1 2 7 3 
5 15 0 4 
9 6 12 8 
13 10 14 11 

1 2 7 3 
5 15 12 4 
9 6 0 8 
13 10 14 11 

1 2 7 3 
5 15 12 4 
9 6 8 0 
13 10 14 11 

1 2 7 3 
5 15 12 0 
9 6 8 4 
13 10 14 11 

1 2 7 0 
5 15 12 3 
9 6 8 4 
13 10 14 11 

1 2 0 7 
5 15 12 3 
9 6 8 4 
13 10 14 11 

1 2 12 7 
5 15 0 3 
9 6 8 4 
13 10 14 11 

1 2 12 7 
5 15 3 0 
9 6 8 4 
13 10 14 11 

1 2 12 7 
5 15 3 4 
9 6 8 0 
13 10 14 11 

1 2 12 7 
5 15 3 4 
9 6 0 8 
13 10 14 11 

1 2 12 7 
5 15 3 4 
9 6 14 8 
13 10 0 11 

1 2 12 7 
5 15 3 4 
9 6 14 8 
13 0 10 11 

1 2 12 7 
5 15 3 4 
9 6 14 8 
0 13 10 11 

1 2 12 7 
5 15 3 4 
0 6 14 8 
9 13 10 11 

1 2 12 7 
0 15 3 4 
5 6 14 8 
9 13 10 11 

1 2 12 7 
15 0 3 4 
5 6 14 8 
9 13 10 11 

1 0 12 7 
15 2 3 4 
5 6 14 8 
9 13 10 11 

1 12 0 7 
15 2 3 4 
5 6 14 8 
9 13 10 11 

1 12 3 7 
15 2 0 4 
5 6 14 8 
9 13 10 11 

1 12 3 7 
15 2 14 4 
5 6 0 8 
9 13 10 11 

1 12 3 7 
15 2 14 4 
5 6 10 8 
9 13 0 11 

1 12 3 7 
15 2 14 4 
5 6 10 8 
9 13 11 0 

42961вершин рассмотрено
Process returned 0 (0x0)   execution time : 504.968 s
Может здесь heuristic считает не через манхэтенское расстояние? Код читать уже сил нет...
Может стоит другого автора почитать?

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


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


Шустрый
*


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

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



Цитата(mes @  21.11.2010,  14:00 Найти цитируемый пост)
это там есть? 

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

Цитата(Леопольд @  21.11.2010,  14:10 Найти цитируемый пост)
 Намекаю что bез пациента врач не может поставить диагноз.

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

Цитата(mes @  21.11.2010,  14:14 Найти цитируемый пост)
а значит скорей всего либо инклудов не хватает, либо компилятор не подходит..

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

Цитата(sQu1rr @  21.11.2010,  14:16 Найти цитируемый пост)
Рейтинг: 0 Сообщений: 2 ...
Не надо наезжать на уважаемых програмистов уважаемого форума 

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

Цитата(Леопольд @  21.11.2010,  14:17 Найти цитируемый пост)
код ужасный. Я-то сперва думал что мой понять сложнее ("наbросал" для сеbя)...
Сишные приведения типов, магические константы, одноbуквенные переменные и т.д. и т.п.

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

Цитата(Леопольд @  21.11.2010,  14:17 Найти цитируемый пост)
Никогда не нравились стандартные bиндеры. Ими очень легко "на###кодить"...

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

Цитата(Леопольд @  21.11.2010,  14:49 Найти цитируемый пост)
Перепиши так:

да, да... именно в этой const дело было...
Цитата(Леопольд @  21.11.2010,  15:11 Найти цитируемый пост)
Может здесь heuristic считает не через манхэтенское расстояние?

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

r+=abs(RowOf[State[i][j]]-i)+abs(ColOf[State[i][j]]-j);


Цитата(Леопольд @  21.11.2010,  15:11 Найти цитируемый пост)
Может стоит другого автора почитать?

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

Это сообщение отредактировал(а) Isaev - 21.11.2010, 17:28
PM MAIL ICQ   Вверх
mes
Дата 21.11.2010, 17:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

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



Цитата(Isaev @  21.11.2010,  16:02 Найти цитируемый пост)
да, да... именно в этой const дело было...

тогда точно :
Цитата(Леопольд @  21.11.2010,  14:11 Найти цитируемый пост)
стоит другого автора почитать




--------------------
PM MAIL WWW   Вверх
Леопольд
Дата 21.11.2010, 19:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(Isaev @  21.11.2010,  17:02 Найти цитируемый пост)
Может стоит... Разница впечатляет, пойду твой код изучать, спасибо!
Если переводит на джаву, то проще по смыслу.

Я использовал два контейнера с временем поиска ~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


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


Шустрый
*


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

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



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

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 и про представление пространств поиска (включая непрерывные игровые пространства!) и пр. Только вот самого  кода нету, конечно smile




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


Шустрый
*


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

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



Master01 а ты под 15 не реализовывал в своё время?
мне что-то подсказывает, что для поля 4х4 при современных то мощностях 10 сек это тоже много (при чём у меня это 18 сек, а не 10)
PM MAIL ICQ   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

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

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

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

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


 




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


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

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