Выложил последнюю версию программы по тому же пути:
http://kosshams.ru/Programs/SBP/SBP.zipВ zip архиве лежат 32 и 64 битные версии, но я рекомендую всегда пользоваться 64-битной, так как она быстрее в 1.6 раза и позволяет использовать больше 4ГБ памяти.
1. Добавил в программу встречный перебор вариантов, позволяющий находить кратчайшее решение в задачах, где количество всех позиций не умещается в памяти, например, в пятнашках:
Встречный перебор реализован, когда конечная позиция определена однозначно - на ней стоят все фигурки, и только в случае, когда ход обратим, иначе его реализация была бы для меня слишком трудоемкой. То есть когда обратный ход является обычным ходом. Это не так, если одна фигурка может толкнуть другую не с самого начала хода, когда она может толкать более одной фигурки параллельно, а также в гравитационном случае.
В распределении позиций по слоям перебора буквой S помечены слои, относящиеся к прямому фронту, распространяющемуся от начальной позиции, а буквой E - к обратному фронту от конечной позиции.
2. Для задач типа пятнашек теперь проверяется возможность решения по критерию четности перестановки.
Также хочу отметить одну особенность программы. При нахождении разных кратчайших решений, не в случае встречного перебора, не может быть, чтобы у двух найденных решений некоторая позиция, не являющаяся конечной, была одинаковая, но предшествующие ей позиции различались. В том числе из этого следует, что найденные решения будут отличаться последним ходом. В случае встречного перебора то же самое верно для частей решения, относящихся к прямому и обратному фронту. При этом получается, что достаточно, чтобы у решений отличались позиции, предшествующие схождению прямого и обратного фронта, и это может дать гораздо больше решений, чем без встречного перебора.
