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

Теория



Изобразить:
Изобразить:
Номер (0-12) пути
n:
Затраты ...
Оптимальные затраты ...

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