tag:blogger.com,1999:blog-7407396207758383724.post1100584796154863304..comments2022-11-21T05:23:30.129+03:00Comments on Заметки программистера: Интеллектуальные системы. Алгоритм A* и игра "Пятнашки"Vladimir Popovhttp://www.blogger.com/profile/10396640252599430444noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-7407396207758383724.post-91685528797477110042016-05-23T22:25:56.092+03:002016-05-23T22:25:56.092+03:00Подскажите, почему алгоритм зацикливается на таком...Подскажите, почему алгоритм зацикливается на таком начальном состоянии:<br />9,13,4,2,10,7,6,11,15,5,12,1,14,8,3,0 и при этом проверку на решение проходит.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-78727630007009737472016-04-18T00:01:55.380+03:002016-04-18T00:01:55.380+03:00Во-первых спасибо. Благодаря Вам я заметил что пот...Во-первых спасибо. Благодаря Вам я заметил что потерял файл с помощью в выложенном примере :) Но по поводу вашего вопроса ответить не могу, тк не понимаю что именно не получается сделать? Что конкретно происходит?Vladimir Popovhttps://www.blogger.com/profile/10396640252599430444noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-34275667560586638952016-04-17T19:50:46.487+03:002016-04-17T19:50:46.487+03:00Как ввести числа в вашу программу,копируя ваш прим...Как ввести числа в вашу программу,копируя ваш пример ,все работает и изменяя ваш пример аналогично все работает,а если вводить сразу так с клавиатуры ничего не работает ,почему так ? Anonimhttps://www.blogger.com/profile/10706269055354112991noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-61439904510385044962015-06-14T12:26:36.352+03:002015-06-14T12:26:36.352+03:00спасибо большое за замечание. исправил.спасибо большое за замечание. исправил.Vladimir Popovhttps://www.blogger.com/profile/10396640252599430444noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-44821809492600764572015-05-23T22:14:26.237+03:002015-05-23T22:14:26.237+03:00Вообще, применяет для поиска, еще не означает что ...Вообще, применяет для поиска, еще не означает что результат будет ожидаемым. С помощью А* я именно _ищу_ кратчайший путь. Не первый попавшийся, а именно кратчайший. То, что результат может отличаться от моих ожиданий, их, ожиданий, не отменяет :)Vladimir Popovhttps://www.blogger.com/profile/10396640252599430444noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-4394253421487386322015-04-16T12:06:09.983+03:002015-04-16T12:06:09.983+03:00в исходниках ошибка разбора командной строки.в исходниках ошибка разбора командной строки.Alex Gorjaynoffnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-76592670093182001062015-01-21T13:14:31.706+03:002015-01-21T13:14:31.706+03:00"... Его главный недостаток - он не всегда на..."... Его главный недостаток - он не всегда находит кратчайшее решение, хотя как правило оно довольно близко к нему..."<br /><br />Ну, алгоритм приведенный тут, тоже не находит кратчайший путь. Точнее найденный им путь не обязательно будет кратчайшим, хоть автор и заявляет обратное ("Применяет алгоритм А* для поиска _крадчайшего_ пути до терминального * состояния от указанного).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-51203269526004660892015-01-14T23:18:37.952+03:002015-01-14T23:18:37.952+03:00"...Полагаться на волю случая мне не по душе,..."...Полагаться на волю случая мне не по душе, но выбирать тот или иной подход вам."<br /><br />В смысле, полагаться на волю случая? Если расположение шашек на поле не валидно, просто поворачиваете поле "набок" (транспонирование матрицы) и получаете валидное состояние. Так что вполне себе нормальный подход ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-22110035264267484772014-12-15T00:02:27.025+03:002014-12-15T00:02:27.025+03:00Попробуйте вместо G нолик вставить. У меня в закры...Попробуйте вместо G нолик вставить. У меня в закрытом и открытом списках получается, <br />где-то, по 150 - 300 записей, в среднем. Если следующее состояние есть в закрытом или открытом списке, просто его игнорирую. И да, H рассчитываю как сумму расстояний, пройденных каждой костью к своему месту. Бот щелкает головоломку за две секунды :DAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-89609444554605346822014-12-08T20:24:24.368+03:002014-12-08T20:24:24.368+03:00да, спасибо, разобрался.да, спасибо, разобрался.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-22479160055441585222014-12-08T10:19:10.828+03:002014-12-08T10:19:10.828+03:00Кажется, помощь уже не нужна? =)Кажется, помощь уже не нужна? =)Vladimir Popovhttps://www.blogger.com/profile/10396640252599430444noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-64356524920060692632014-12-07T00:32:28.076+03:002014-12-07T00:32:28.076+03:00лол, сам бы никогда не додумался до такого колдунс...лол, сам бы никогда не додумался до такого колдунства. хотя...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-87129840452018192892014-12-07T00:21:16.112+03:002014-12-07T00:21:16.112+03:00Вродебы нашел в вашем коде. Это оно:
if ((action =...Вродебы нашел в вашем коде. Это оно:<br />if ((action == 1) && ((zero + 1) % sideSize == 0)) { return null; } <br />if ((action == -1) && ((zero + 1) % sideSize == 1)) { return null; } <br />?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-42610352050327979222014-12-06T23:50:40.608+03:002014-12-06T23:50:40.608+03:00Комент испортился, т.е. вот так:
1 2 _
3 4 5
6 7 ...Комент испортился, т.е. вот так: <br />1 2 _<br />3 4 5<br />6 7 8<br /><br />1 2 3<br />_ 4 5<br />6 7 8Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-21665972644892743402014-12-06T23:48:09.117+03:002014-12-06T23:48:09.117+03:00Скажите пожалуйста, а как не допустить перемещения...Скажите пожалуйста, а как не допустить перемещения шашки с четвертой позиции на третью? Т.е. <br />1 2 <br />3 4 5<br />6 7 8<br /><br />1 2 3<br /> 4 5<br />6 7 8 Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-33196128838485639082013-12-23T18:14:20.473+04:002013-12-23T18:14:20.473+04:00Скажите мне пожалуйста, а вы вообще пробовали испо...Скажите мне пожалуйста, а вы вообще пробовали использовать ваш алгоритм на традиционном размере доски, то есть 4х4? Потому что я написал алгоритм А*, используя эвристику не просто "количества костяшек не на своих местах" а совокупный анализ манхэттенского расстояния и линейного конфликта (https://sites.google.com/site/killgamesh666/alghorytms/tag15), и всё равно результаты были неутешительными. При количестве перестановок больше 3-х, программа зависала на полминуты, после чего выдавала сообщение о том, что массив закрытых вершин переполнен (и это при том, что он состоит из 10000 элементов).<br />К счастью, решение проблемы имеется - использовать вместо А* IDA*. Суть в том, что это тот же А*, но использующий метод итеративного углубления, реализуемый рекурсивной функцией поиска и постепенно растущим оценочным порогом. Его главное преимущество - массивы открытых и закрытых вершин ему вообще не нужны, а потому он щёлкает пятнашки 4х4 как орехи до тех пор, пока перестановки находятся в районе 30-50. Его главный недостаток - он не всегда находит кратчайшее решение, хотя как правило оно довольно близко к нему. Дело в том, что обычно А* используют на двумерных картах, в то время как пятнашки - аналог девятимерной (в вашем случае) и шестнацатимерной (в моём) карт, и количество рассматриваемых вершин быстро достигает астрономических величин в таких размерностях. IDA* же не рассматривает и не оценивает вершины, а просто их пробегает, пока не споткнётся о порог своей оценки.<br />Почитать об IDA* можно в википедии http://ru.wikipedia.org/wiki/IDA*#IDA.2A<br />Кстати, хоть и чуть-чуть, но ваша статья мне помогла. Именно вы подсказали мне метод генерации карты, основанный на перестановках, а не на чистом рандоме, благодаря чему теперь я могу регулировать сложность =)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-36042493661325341752013-11-07T18:18:08.161+04:002013-11-07T18:18:08.161+04:00Реализация на С++ https://gist.github.com/sunlover...Реализация на С++ https://gist.github.com/sunloverz/7338003Anonymoushttps://www.blogger.com/profile/13913209992059675119noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-66002531282087577592013-10-12T18:30:19.133+04:002013-10-12T18:30:19.133+04:00Спасибо за комментарий и за то, что поделились со...Спасибо за комментарий и за то, что поделились собственными достижениями. К сожалению пока не имею возможности опробовать Ваш вариант решения, но результат впечатляет. Отличный наглядный пример важности выбора эвристической функции.Vladimir Popovhttps://www.blogger.com/profile/10396640252599430444noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-18401251512945732592013-10-11T15:20:17.555+04:002013-10-11T15:20:17.555+04:00Извините, ошибся, H=12. Я не посчитал пустую костя...Извините, ошибся, H=12. Я не посчитал пустую костяшку, которой идти два шага до своего места в правом нижнем углу.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-51366990405074341522013-10-11T15:16:35.239+04:002013-10-11T15:16:35.239+04:00Попробуйте другой критерий определения веса вершин...Попробуйте другой критерий определения веса вершины. Не количество костяшек, находящихся не на своих местах, а суммарный путь, который нужно пройти каждой костяшке до своего места. (Для первой вершины из вашего примера H=10) Я устраивал соревнования своего и вашего алгоритмов, разница в числе вершин, которые надо обработать, доходила до порядка. Пятнашка 4x4, тридцать ходов перемешивания (да, я тоже перемешивал случайными ходами):<br />мой алгоритм <br />Открытый список - 1668<br />Закрытый список - 1753<br />ваш алгоритм<br />Открытый список - 22317<br />Закрытый список - 22452Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-64142050871620389142013-05-09T20:29:04.670+04:002013-05-09T20:29:04.670+04:00Этот комментарий был удален автором.Ninochkahttps://www.blogger.com/profile/14358046467639258923noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-64990591397620448772013-01-20T20:33:30.748+04:002013-01-20T20:33:30.748+04:00Как на картинке где G=2 H=4 F=6 !!!
Как на картинке где G=2 H=4 F=6 !!!<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-91658021274805296142013-01-20T20:32:23.935+04:002013-01-20T20:32:23.935+04:00А может быть и ветвление на три подальших расматри...А может быть и ветвление на три подальших расматриваемых вариантов ? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-62438761141346379362013-01-06T14:09:38.155+04:002013-01-06T14:09:38.155+04:00Потому, что не на своих местах находятся костяшки ...Потому, что не на своих местах находятся костяшки 3, 4, 5, 7 и 0. Считать ли 0 за костяшку, на мой взгляд дело каждого, на конечный результат это сказаться не должно.Vladimir Popovhttps://www.blogger.com/profile/10396640252599430444noreply@blogger.comtag:blogger.com,1999:blog-7407396207758383724.post-80389293848091462332012-12-16T19:00:00.123+04:002012-12-16T19:00:00.123+04:00Можно узнать, почему картинке в первом состоянии, ...Можно узнать, почему картинке в первом состоянии, когда не сделано ни одно перемещение(G = 0), H = 5? Anonymousnoreply@blogger.com