Dmitrii (_dmitrii) wrote,
Dmitrii
_dmitrii

Математикам

Товарищи математики, вопрос к вам профессиональный.

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



Как вот это лучше обходить?
Пока что ничего кроме эвристического оббегания (каждый раз случайно выбирается поворот) придумать у меня не получается. Понятно что таким образом я никогда не смогу обсчитать все маршруты, расчеты будут только по принципу "как повезет". Может быть есть алгоритм, который позволит перебрать все альтернативы? Или число таких вариантов слишком велико для полного перебора? Реальный допустимый срок расчета на компьютере - порядка недели.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments