Алгоритмизация. Найти оптимальный путь из А в В по минимумум затрат
/движение возможно по горизонтали, вертикали и диагонали/

Теория


Изобразить:
Изобразить:
Изобразить:
S = -??-

Из точки А (левый нижний угол) до точки В (правый верхний угол), двигаясь по гризонтали, вертикали или диагонали, требуется пройти путь так, чтобы ссуммарный расход был минимальный.
Решение:
1) По методу безусловной оптмизации Богданова-Белмана, можно заполнить узлы сетки ячеек (начиная с первой) минимальными числами (с учетом в ней заполненных узлов) числами, Добрашись до конечного узла (любого), вы до него получите минимальный, например, по расходу топлива.
Организвать вычисления и заполнить узлы - найти оптимальный путь - не сложно. Сложнее этот путь изобразить. Визуально на сетке - когда узлы заполнены оптимальными числами - проследить этот путь можно. В скрипте формализовать это и отсюда показать непонятно как это сделать.
Можно предложить идти случайно: если выпала 1, двигаться горизонтально, 2 - вертикально, 3 - по диагонали.
На каком-то варианте прохождения пути от начала до конца, можно наткнуться на оптимальный. Это произойдет, когда расходы случайного прохождения пути совпадут с минимальными (вычисленными ранее в узлах сетки).
На таком принципе можно предложить игру, кто пройдет первый уровень, например, сетку 5х5, допускается на следующий уровень (6х6), где опять ищет оптимальный путь и получает свои очки Итак до любого уровня.
Можно разнообразить задачу: каждое ребра задает количество букв какого-то слова, которые при прохождении маршрута должны дать искомое предложение. Можно усложнить задачу: совместив первый вариант со вторым.