19:32 

Волновой алгоритм

Как доказать, что от клетки A до клетки B нельзя дойти за более четырех шагов?

@темы: Головоломки и занимательные задачи

Комментарии
2017-09-23 в 20:09 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Груша Вильямс, а что считается шагом?... если переход в соседнюю клетку, то опять же какой переход разрешён... :upset:
Если по диагонали можно ходить, то три шага получается - минимум... если только в соседние по стороне клетки можно ходить, то минимум шесть шагов ...

2017-09-23 в 20:24 

All_ex, ой, я вообще слишком криво написал. Тут такая ситуация, ходить можно вверх, вниз, влево и вправо (как стрелки на клавиатуре), можно произвольно ставить препятствия, которые надо обходить. И вот всегда максимум получается 5 шагов (я там ошибся, написав более четырех шагов, более пяти не получается придумать). Изначально у меня поле 20x20.

Собственно ищу я этот максимум потому, что пользователь (преподаватель) сам вводит координаты препятствий и начала и конца пути с клавиатуры. Поэтому когда пишу цикл для подсчета волн, надо учесть самый неоптимальный случай, чтобы код не крашился, можно, конечно, сразу написать меньше тыщи скажем, но это неоптимальное использование памяти.
По рисунку, на 189-ом шаге А приходит в квадрат 4x4, то есть клетка, в которой находится А в этом квадрате, имеет номер волны 189.

2017-09-23 в 20:43 

Вот здесь хорошо виден принцип работы алгоритма.

p.s. я тут загуглил ru.wikipedia.org/wiki/Алгоритм_Ли и получается, что у меня по заданию алгоритм с ортогональным путем
p.p.s. было бы круто увидеть общую формулу для максимума для поля `m times n`.

2017-09-23 в 23:20 

Понял, для поворота нам необходимо три клетки в одном направлении, но при таком условии мы уже достигнем клетки B. Иные повороты, например, вниз, а потом вправо (одна клетка в одном направлении) неоптимальны, так как мы можно сказать двигаемся по гипотенузе, а мы должны максимально отклоняться от нужного направления. Итого более пяти шагов не сделать. Тогда для поля 20x20 максимум 189+5=194 шага. Логично или не очень?

2017-09-24 в 04:21 

Вам нужен массив m x n, в нем будут и препятствия и текущая информация о пути.

URL
2017-09-24 в 08:59 

All_ex
Эллипс - это круг, который можно вписать в квадрат 25х40
Груша Вильямс, Вот здесь хорошо виден принцип работы алгоритма.
что-то такое я раньше видел под названием "поиск в ширину"... :upset:
и таки соглашусь с Гостем - массива вполне достаточно...

2017-09-28 в 14:52 

Я там ошибся в подсчетах, +19 первого столбца забыл прибавить, итого 217 вышло.
Формулы тоже вывел, но в частных случаях.
Если матрица `(2n+1) times (2n+1)`, то `k_{max} = 2n^2 + 4n - 1` `forall n in NN \ {1}`.
Если матрица `2n times 2n`, то `k_{max} = 2n^2 + 2n - 3` `forall n in NN`.
Если же сразу `k_{max}` не считать, то чисел на клетки может не хватить и если рандомом заполнять массив, то та же самая проблема. То есть без математики слишком уж уныло выглядит.

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная