Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, nikov, Вы писали:
[]
К>Короче говоря.
К>Очень просто находим расположение 37 излучателей — и затем находим расстояние от каждого из них до точки приёмника.
К>Расстояние от точки до конуса — элементарно. Рассматриваем плоскость, образованную осью конуса и точкой. Задача сводится к расстоянию между точкой и углом из двух лучей.

Перечитал, в общем, физическая модель ясна. Правда, не вижу конструктивного решения.

А вот на счет отражения исходной (или конечной точки), я тоже думал. Если показать, что при переходе с грани на грань мы углы не срезаем по воздуху (что так и есть при соотношении скоростей 10 к 1), то можно обложить куб со всех сторон такими же кубами, т.е. рассмотреть конструкцию из 3х3х3 кубов, в которой исходный куб -- центральный. Может даже 5х5х5 кубов, хотя вряд ли. Скорее к конструкции 3х3х3 надо будет добавить еще по кубу к каждому из 6 кубов в центре большой грани 3х3.

Каждый соседний куб с общей гранью -- поворот исходного вокруг одного общего ребра, т.е. идея в том, что когда мы пересекаем общее ребро, то вместо того, чтобы свернуть на другую грань, мы продолжаем движение в этой же плоскости по грани соседнего куба. Тогда конечная точка отразится четыремя разными способами в тот куб. Далее, нам может понадобиться отражение того куба в сторону (это нужно при развертке куба через общую смежную грань) или еще одно отражение дальше в ту же сторону (это может понадобиться, для развертки при путешествии с одной грани на противоположную). Тогда путешествие по граням куба заменяется путешествием в одной плоскости от грани исходного куба до грани одного из кубов отражений, а там уже в соответствующую отраженную конечную точку.

Только, по сути, такая постановка равносильна развертке куба, а с разверткой ее проще описать и понять, какие именно варианты надо рассматривать.

Здравствуйте, vadimcher, Вы писали:

V>Перечитал, в общем, физическая модель ясна. Правда, не вижу конструктивного решения.

Конструктивное решение есть, но оно громоздкое
— найти 36 конусов, соответствующих начальной точке (элементарно, отражения и вращения)
— померять расстояние от них до конечной точки (вот здесь уже чуть сложнее, но всё равно вся тригонометрия сокращается)

V>А вот на счет отражения исходной (или конечной точки), я тоже думал. Если показать, что при переходе с грани на грань мы углы не срезаем по воздуху (что так и есть при соотношении скоростей 10 к 1), то можно обложить куб со всех сторон такими же кубами, т.е. рассмотреть конструкцию из 3х3х3 кубов, в которой исходный куб -- центральный. Может даже 5х5х5 кубов, хотя вряд ли. Скорее к конструкции 3х3х3 надо будет добавить еще по кубу к каждому из 6 кубов в центре большой грани 3х3.

5*5*5. На моей анимации видно, что кое-где (у верхней грани) первой приходит волна от самого дальнего излучателя.

[]
V>Только, по сути, такая постановка равносильна развертке куба, а с разверткой ее проще описать и понять, какие именно варианты надо рассматривать.

С развёртками есть нюанс. Представим себе развёртку не просто двумерную, а с "воздушным пространством" над каждой клеткой.
В одной из этих ячеек парит исходная точка. Траектория косым лучом падает из этой точки на землю...
Так вот, если траектория пересекает границы воздушного пространства клетки, это просто теряет физический смысл.
И хотя кажется очевидным, что такие траектории попросту неоптимальны, и будут отсеяны на стадии сравнения, — сама попытка принять их во внимание сомнительна.


Так что, на правах кулика на своём болоте, — продолжаю нахваливать идею с излучением звука.
Тем более, что излучение звука соответствует простым-и-понятным волновым алгоритмам поиска расстояния на графах.

Здравствуйте, Кодт, Вы писали:
[]
К>С развёртками есть нюанс. Представим себе развёртку не просто двумерную, а с "воздушным пространством" над каждой клеткой.
К>В одной из этих ячеек парит исходная точка. Траектория косым лучом падает из этой точки на землю...
К>Так вот, если траектория пересекает границы воздушного пространства клетки, это просто теряет физический смысл.
К>И хотя кажется очевидным, что такие траектории попросту неоптимальны, и будут отсеяны на стадии сравнения, — сама попытка принять их во внимание сомнительна.

Да, этот вариант я отсеиваю просто по тому, что угол наклона, под которым оптимально двигаться имеет тангенс sqtr(99), т.е. практически вертикальный. В случае, если такой луч пересекат боковую грань, то оптимальнее сразу прыгать на эту грань, а оттуда уже бежать. Это отличает решение на бумаге от программного -- там это надо все учитывать во всяких if-ах.

К>Так что, на правах кулика на своём болоте, — продолжаю нахваливать идею с излучением звука.
К>Тем более, что излучение звука соответствует простым-и-понятным волновым алгоритмам поиска расстояния на графах.

Ну да, за исключением того, что здесь нет конечного графа, а потому, например, получить конкретный угол движения с тангенсом в sqrt(99) проще аналитически. В случае с распространением волны надо как-то получить, что именно это направление даст максимальный выигрыш по времени по сравнению с перпендикулярным движением к грани. Но даже поняв это, остается целая окружность оптимальных точек на грани, в которые стоит изначально лететь, развертка помогает понять, в какую именно точку надо лететь -- в ту, которая пересекает кратчайшую прямую, соединящую два центра таких окружностей на одной из разверток куба.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, nikov, Вы писали:

N>>Имеется деревянный куб со стороной 1 м. Жук может ползти по поверхности деревянного куба со скоростью 10 мм/с, и он может прогрызать его в любом направлении со скоростью 1 мм/с.
N>>Написать программу, которая по начальным и конечным координатам жука (они могут быть как внутри куба, так и на поверхности) определит минимальное время, необходимое для преодоления этой дистанции.

V>В общем случае решение такое: либо напрямую из начальной точки в конечную, либо под углом к грани с тангенсом sqrt(99) летим к одной грани, далее по прямой на одной из разверток куба бежим по граням куба, добегаем до точки, откуда по прямой с таким же тангенсом летим в конечную точку.

V>Сначала список утверждений для решения. А потом решение в общем виде в конце.

V>1) Рассмотрим одну "грань" куба -- бесконечную плоскость. Пусть две точки "висят" на высоте x и y над плоскостью. А расстояние между основаниями опущенных из них на плоскость перпендикуляров равно z. Т.е. "сбоку" вид такой:
V>

V>*
V>|
V>|x       *
V>|        |y
V>----------
V>    z
V>

V>Движение в воздухе со скоростью 1/10. А на плоскости -- 1. Каков оптимальный маршрут из одной точки в другую? Мы можем по прямой спуститься из левой точки на отрезок z на расстояние a от левого перпендикуляра, затем пройти по плоскости, пока расстояние до правого перпендикуляра не будет b, а затем по прямой полететь во вторую точку. Либо, просто напрямую лететь во вторую точку.

V>В первом случае время равно 10sqrt(x^2+a^2)+10sqrt(y^2+b^2)+(z-a-b). Дифференцируем по a. 99a^2=x^2. Получаем, что оптимальнее всего лететь в точку на расстоянии a=x/sqrt(99), что чуть больше 0.1x. Далее, мы двигаемся по плоскости, пока не дойдем до второго перпендикуляра на расстояние y/sqrt(99), а оттуда взлетаем ко второй точке. Здесь есть одно "но": а что, если z меньше, чем (x+y)/sqrt(99). В этом случае, как легко понять, и мы это увидим, надо лететь напрямую. Время, которое нам на это надо, равно 100(x+y)/sqrt(99)+z-(x+y)/sqrt(99)=(x+y)sqrt(99)+z.

V>Во втором случае (летим напрямую), время 10sqrt(z^2+(x-y)^2).

V>Напрямую (не через плоскость) добираться имеет смысл, если (x+y)sqrt(99)+z > 10sqrt(z^2+(x-y)^2)
V>или 99(x+y)^2+z^2+2sqrt(99)(x+y)z > 100(x-y)^2+100z^2
V>или 400xy > x^2+y^2+99z^2-2sqrt(99)(x+y)z+2xy = (x + y — sqrt(99)z)^2.

V>Пусть (x+y)/sqrt(99)>z. Тогда двигаться напрямую -- быстрее, чем лететь в любую точку на отрезке z, а оттуда сразу стартовать в другую точку (очевидно, т.к. все время движемся со скоростью 1/10, но по треугольнику, а не напрямую). С другой стороны, т.к. оптимальнее всего лететь как можно ближе к точке на расстоянии x/sqrt(99), а взлетать из точки на расстоянии y/sqrt(99), и (x+y)/sqrt(99)>z, то любое решение, при котором мы летим на отрезок, затем двигаемся по нему, а затем взлетаем, также будет неоптимальным). Короче, если (x+y)/sqrt(99)>z, то летим напрямую. А сравнение выше рассматриваем только для (x+y)<sqrt(99)z, т.е., когда мы возьмем корень от обеих частей, то справа будет не x+y-sqrt(99)z (отрицательное), а sqrt(99)z-(x+y).

V>Итак, летим напрямую, если sqrt(99)z < x + y + 20sqrt(xy) (***)
V>Во как!

V>2) Рассмотрим теперь движение из одной точки на грани в другую точку на другой грани. Как вариант, можно предположить, что, пересекая общее ребро, мы захотим срезать и пролетим часть внутри куба. Как легко видеть, это не так. В этом случае мы вместо того, чтобы двигаться по стороне куба до ребра, а оттуда до другой точки другой грани (две стороны некоторого треугольника), захотим срезать внутри куба (т.е. полетим по третьей стороне этого треугольника, которая проходит внутри куба). Но эта третья сторона не может быть в 10 раз меньше, чем сумма двух других сторон. Даже если предположить, что мы сначала двигаемся перпендикулярно ребру, что далеко не всегда оптимально, а потом в конечную точку, то для такого прямоугольного треуголька гипотенуза может быть только в sqrt(2) раз меньше суммы катетов. А для оптимального треугольника -- и того меньше. Короче, при переходе с грань на грань мы углы не срезаем. При движении с одной грани на противоположную -- тем более. Пока мы внутри куба летим в 10 раз медленнее, чем по граням, за это время весь куб по периметру можно 2 раза обойти.

V>3) При движении по граням из одной точки в другую оптимальнее всего двигаться по прямой для одной из разверток куба. Например, если исходная точка и конечная точка лежат на смежных гранях, то это может быть развертка через общее ребро, или развертка через общую смежную грань.
V>

V>так: ---  или так:  ---   ---
V>    |  *|          |  *| |   |
V>    |   |          |   | |   |
V>     ---            ---   ---
V>    |   |                |  *|
V>    |  *|                |   |
V>     ---                  ---
V>

V>Как быстрее, так и двигаемся.

V>Собственно, решение такое:
V>а) Рассматриваем 6 перпендикуляров (проекций) на грани для исходной точки и для конечной точки.
V>б) Для различных комбинаций начальной и конечной проекции находим расстояние по граням куба (кратчайшая прямая по одной из разверток куба).
V>в) Рассматривая соответствующую развертку, получаем задачу из пункта 1). Т.е. оптимальное движение будет таким, что мы летим под углом с тангенсом sqrt(99) к грани, далее бежим по той самой прямой до того места, откуда снова под этим же углом попадаем в нужную точку. Кстати, для проверки проекций (исходной и конечной) на одной грани можно сразу воспользоваться формулой (***).
V>г) Сравниваем результаты пункта в) с прямым полетом из начальной точки в конечную.

А куда автор пропал, комментарии будут? Правильно, нет?

Решал сходным образом, но в терминах геометрической оптики. Для того чтобы попасть из заданой точки внутри куба в точку на поверхности луч идет либо по прямой — если цель расположена внутри конуса с раствором равным углу полного внутреннего отражения, либо падает на поверхность под этим углом и далее бежит по поверхности. Соответственно получаем по 6 окружностей-проекций для начальной и конечной точек. Итого (с учетом прямого пути) те же 37 вариантов, часть из которых отсекается:
1. Если проекции начальной и конечно точек пересекаются, их не рассматриваем (по прямой получается быстрее).
2. Если проекция выходит за границу грани, мы ее не рассматриваем (с выходом на любую из соседних граней будет быстрее).