Когда играешь на грунтовом корте в теннис, в конце возникает неприятное обстоятельство — "Корт надо убирать." Более конкретно — подметать шваброй размеченные линии(белые линии на рисунке, кроме средней, которая сетка).
Логичным встает вопрос — "Как это сделать быстрее всего?" Встает довольно простая, но интересная алгоритмическая задача, типа задачи коммивояжера, но не совсем.
Принимая во внимание два обстоятельства:
1. Кратчайший путь можно искать на половине корта;
2. Путь на половине корта должен заканчиваться с краю сетки,
можно теперь построить несколько оптимальных путей со шваброй на одной половине корта, которые будут содержать наименьшее количество паразитических ходов по местам. Эти пути должны заканчиваться(или начинаться) на краю сетки.
Таким образом, если у нас будет все оптимально, надо вначале вычисленный оптимальный путь пройти в таком направлении, чтобы он заканчивался на краю сетки, а потом пройти его же в обратном направлении, чтобы он начинался на краю сетки.
Тупым перебором одного миллиона вариантов, я нарисовал несколько наиболее коротких путей(в гифках), которые все содержат примерно 15 пройденных паразитических метров.
На гифках показаны оптимальные прохождения правой стороны корта, начинающиеся от нижнего края сетки. Если вдруг придумаете алгоритм лучше перебора, пишите. =)))
Ну и вызываются сюда: [id289145|Макс Кошкин] и [id2|Александра Владимирова]
Логичным встает вопрос — "Как это сделать быстрее всего?" Встает довольно простая, но интересная алгоритмическая задача, типа задачи коммивояжера, но не совсем.
Принимая во внимание два обстоятельства:
1. Кратчайший путь можно искать на половине корта;
2. Путь на половине корта должен заканчиваться с краю сетки,
можно теперь построить несколько оптимальных путей со шваброй на одной половине корта, которые будут содержать наименьшее количество паразитических ходов по местам. Эти пути должны заканчиваться(или начинаться) на краю сетки.
Таким образом, если у нас будет все оптимально, надо вначале вычисленный оптимальный путь пройти в таком направлении, чтобы он заканчивался на краю сетки, а потом пройти его же в обратном направлении, чтобы он начинался на краю сетки.
Тупым перебором одного миллиона вариантов, я нарисовал несколько наиболее коротких путей(в гифках), которые все содержат примерно 15 пройденных паразитических метров.
На гифках показаны оптимальные прохождения правой стороны корта, начинающиеся от нижнего края сетки. Если вдруг придумаете алгоритм лучше перебора, пишите. =)))
Ну и вызываются сюда: [id289145|Макс Кошкин] и [id2|Александра Владимирова]
When you play tennis on a clay court, in the end there is an unpleasant circumstance - "The court must be removed." More specifically - to mop up marked lines (white lines in the figure, except for the middle one, which is a grid).
The logical question is - "How to do it the fastest?" A rather simple but interesting algorithmic problem arises, such as a traveling salesman problem, but not quite.
Taking into account two circumstances:
1. The shortest path can be searched on the half of the court;
2. The halfway path must end at the edge of the net,
You can now build several optimal paths with a mop on one half of the court, which will contain the least number of parasitic moves in places. These paths must end (or begin) at the edge of the grid.
Thus, if we have everything optimally, we must first calculate the optimal path in this direction, so that it ends at the edge of the grid, and then pass it in the opposite direction, so that it starts at the edge of the grid.
With a blunt search of one million variants, I drew a few of the shortest paths (in gifs), which all contain about 15 parasitic meters.
The gifs show the optimal passages of the right side of the court, starting from the bottom of the net. If you suddenly come up with an algorithm better than busting, write. =)))
Well, called here: [id289145 | Max Koshkin] and [id2 | Alexander Vladimirov]
The logical question is - "How to do it the fastest?" A rather simple but interesting algorithmic problem arises, such as a traveling salesman problem, but not quite.
Taking into account two circumstances:
1. The shortest path can be searched on the half of the court;
2. The halfway path must end at the edge of the net,
You can now build several optimal paths with a mop on one half of the court, which will contain the least number of parasitic moves in places. These paths must end (or begin) at the edge of the grid.
Thus, if we have everything optimally, we must first calculate the optimal path in this direction, so that it ends at the edge of the grid, and then pass it in the opposite direction, so that it starts at the edge of the grid.
With a blunt search of one million variants, I drew a few of the shortest paths (in gifs), which all contain about 15 parasitic meters.
The gifs show the optimal passages of the right side of the court, starting from the bottom of the net. If you suddenly come up with an algorithm better than busting, write. =)))
Well, called here: [id289145 | Max Koshkin] and [id2 | Alexander Vladimirov]
У записи 6 лайков,
0 репостов,
1075 просмотров.
0 репостов,
1075 просмотров.
Эту запись оставил(а) на своей стене Александр Беспалов
