Математикам
Товарищи математики, вопрос к вам профессиональный.
Есть некое поле 7*7, движение в котором начинается от центра.
Каждый квадратик поля имеет свой вес. Задача такая - выйдя из центра и перемещаясь только по вертикали и горизонтали змейкой нарисовать максимально возможное число маршрутов, потом подсчитать "вес" каждого маршрута и определить наиболее выгодный. Задача осложняется тем, что сумма ходов (т.е. сколько клеточек можно закрасить) - величина переменная, от 0 до 40 (полностью задача состоит из трех таких квадратов, в сумме около 40 ходов).
Как вот это лучше обходить?
Пока что ничего кроме эвристического оббегания (каждый раз случайно выбирается поворот) придумать у меня не получается. Понятно что таким образом я никогда не смогу обсчитать все маршруты, расчеты будут только по принципу "как повезет". Может быть есть алгоритм, который позволит перебрать все альтернативы? Или число таких вариантов слишком велико для полного перебора? Реальный допустимый срок расчета на компьютере - порядка недели.
Есть некое поле 7*7, движение в котором начинается от центра.
Каждый квадратик поля имеет свой вес. Задача такая - выйдя из центра и перемещаясь только по вертикали и горизонтали змейкой нарисовать максимально возможное число маршрутов, потом подсчитать "вес" каждого маршрута и определить наиболее выгодный. Задача осложняется тем, что сумма ходов (т.е. сколько клеточек можно закрасить) - величина переменная, от 0 до 40 (полностью задача состоит из трех таких квадратов, в сумме около 40 ходов).
Как вот это лучше обходить?
Пока что ничего кроме эвристического оббегания (каждый раз случайно выбирается поворот) придумать у меня не получается. Понятно что таким образом я никогда не смогу обсчитать все маршруты, расчеты будут только по принципу "как повезет". Может быть есть алгоритм, который позволит перебрать все альтернативы? Или число таких вариантов слишком велико для полного перебора? Реальный допустимый срок расчета на компьютере - порядка недели.