Comments 30
Кому-то проще в уме решить, а у кого-то есть конпелятор си и несколько часов свободного времени. Классический холивар между P и NP :-)
50 ходов в уме? Увы, это за гранью моих возможностей.
Зашел почитать про автоматизированное прохождение текстовых квестов. А тут прохождение «пятнашек».
Простые оптимизации, которые должны заметно ускорить процесс:
1. Можно завести set, в котором хранить вообще все позиции, в которых мы побывали. Но тогда надо уверенность в том, что в каждую позицию мы приходим за минимальное число ходов, поэтому придется поиск в глубину заменить на поиск в ширину. Как вариант, можно set заменить на map, который отображает позицию в ее глубину, тогда надо идти в рекурсию только если новая найденная глубина меньше старой.
2. Я не очень понял, зачем перенумеровывать фишки. Вроде бы без перенумерации задача сильно проще. А если в endPos хранится правильно заполненное поле, то алгоритм не будет смотреть, какую из одинаковых фишек он помещает на подходящее поле и проблемы не возникнет.
1. Можно завести set, в котором хранить вообще все позиции, в которых мы побывали. Но тогда надо уверенность в том, что в каждую позицию мы приходим за минимальное число ходов, поэтому придется поиск в глубину заменить на поиск в ширину. Как вариант, можно set заменить на map, который отображает позицию в ее глубину, тогда надо идти в рекурсию только если новая найденная глубина меньше старой.
2. Я не очень понял, зачем перенумеровывать фишки. Вроде бы без перенумерации задача сильно проще. А если в endPos хранится правильно заполненное поле, то алгоритм не будет смотреть, какую из одинаковых фишек он помещает на подходящее поле и проблемы не возникнет.
1. Я думал об этом, но не хотелось сильно жрать память
2. Возможно я не прав, но без перенумерации, по моему, не получится (в статье я объяснял почему).
Оба эти вопроса достаточно сложны и неоднозначны. Требуется время, чтобы разобраться (а выходные кончились)
2. Возможно я не прав, но без перенумерации, по моему, не получится (в статье я объяснял почему).
Оба эти вопроса достаточно сложны и неоднозначны. Требуется время, чтобы разобраться (а выходные кончились)
1. Можно текущий путь хранить в setе, а не в массиве, уже должно неплохо помочь.
2. Я вижу такую строчку: «Таким образом, если мы начнем двигать одну из парных фишек не на свое место, мы, скорее всего, не сможем решить головоломку». Единственная проблема — в подсчете расстояния до ответа, т.к. непонятно, до какого места считать расстояние. Можно в качестве оценки считать до ближайшего (тогда придется каждый раз пересчитывать расстояние заново), либо вообще забить. Итак, мы теряем отсечение по расстоянию. Посмотрим на то, что мы получим взамен. В оригинальных пятнашках позиций 16!=2.09×10¹³. В нашей игре — 16!/2⁷ =1.63×10¹¹. Получается, что действительно неочевидно, какой подход лучше, хотя чисто интуитивно мне кажется, что этот способ таки немного ускорит решение.
2. Я вижу такую строчку: «Таким образом, если мы начнем двигать одну из парных фишек не на свое место, мы, скорее всего, не сможем решить головоломку». Единственная проблема — в подсчете расстояния до ответа, т.к. непонятно, до какого места считать расстояние. Можно в качестве оценки считать до ближайшего (тогда придется каждый раз пересчитывать расстояние заново), либо вообще забить. Итак, мы теряем отсечение по расстоянию. Посмотрим на то, что мы получим взамен. В оригинальных пятнашках позиций 16!=2.09×10¹³. В нашей игре — 16!/2⁷ =1.63×10¹¹. Получается, что действительно неочевидно, какой подход лучше, хотя чисто интуитивно мне кажется, что этот способ таки немного ускорит решение.
В том-то и дело что от расстояния отказываться не хочется. Можно правда вести одновременно 64 расстояния.
Я тоже говорил про set. Кроме того, у меня нет уверенности, что позиции будут часто повторяться в параллельных ветвях поиска (почему-то кажется, что повторяться они будут редко, что снизит эффективность хранения всех просмотренных позиций). Тоже требуется отдельное изучение.
Помню, когда проходил «Рейнджеров», держал под рукой толстенький блокнот. К концу игры блокнот был напрочь исписан различными пометками по решению многочисленных текстовых головоломок. Грандиозная игрушка!
У меня была целая тетрадь для этих квестов!
Хороший пример к этому посту habrahabr.ru/post/179495/ про стремление айтишников усложнять задачи :)
А в чем Вы видите усложнение задачи?
Вероятно, BlackFlyingCat умеет решать пятнашки сам, поэтому программа ему не нужна.
Аррр, прошу прощения, для кубик-рубика есть алгоритм сбора, пятнашки — NP полная задача.
Но всё равно, по моим личным ощущениям, удовлетворение от задачи будет когда решил её сам. Тут да, отличаюсь от автора. Так что в моей системе ценностей будет усложнее. Соотношение удовольствие/затраченные усилия в случае написания программы будет меньшим.
Но всё равно, по моим личным ощущениям, удовлетворение от задачи будет когда решил её сам. Тут да, отличаюсь от автора. Так что в моей системе ценностей будет усложнее. Соотношение удовольствие/затраченные усилия в случае написания программы будет меньшим.
Для пятнашек тоже есть алгоритм. Только он не учитывает ограничение на число ходов и «парные» пятнашки.
И да, для меня нет разницы решил ли я головоломку сам или при помощи компьютера. Компьютер — просто инструмент.
И да, для меня нет разницы решил ли я головоломку сам или при помощи компьютера. Компьютер — просто инструмент.
Вы меня опередили)
Алгоритм: ipuzzles.ru/15s/15s-solve-algorithm/
NP-полная задача — кратчайший путь в пятнашках :)
Таке решается за 5 минут гугления и 10 минут прогонки алоритма. Получается быстрее, чем писать программу, а на мой взгляд ещё спортивнее и познавательнее, покуда переборными алгоритма мой мозг уже сыт :)
Алгоритм: ipuzzles.ru/15s/15s-solve-algorithm/
NP-полная задача — кратчайший путь в пятнашках :)
Таке решается за 5 минут гугления и 10 минут прогонки алоритма. Получается быстрее, чем писать программу, а на мой взгляд ещё спортивнее и познавательнее, покуда переборными алгоритма мой мозг уже сыт :)
А по моим личным ощущением закодить такую задачу куда приятнее, чем решать вручную. Так что мне подход автора больше по душе. Тем более, что я бы такую задачу вручную решал бы в целом перебором, а не придумывал какой-нибудь хитрый алгоритм.
Жду алгоритма прохождения холодильника из колобков (Братьев пилотов).
это?
Sign up to leave a comment.
Дело о малокском сейфе