Форум программистов, компьютерный форум, киберфорум
Геометрия
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
 Аватар для Garpedonapt
162 / 7 / 0
Регистрация: 13.04.2026
Сообщений: 32

Найти кратчайший маршрут между двумя маяками

05.06.2026, 22:26. Показов 4912. Ответов 47
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Представьте, что вы картограф, которому поручено нанести на карту кратчайший маршрут между двумя маяками М и N, расположенными на поверхности планеты в системе тау Кита. Планета необычная - в форме конуса (прямого и усеченного). Она имеет определенные размеры, которые указаны на рисунке. Маяки расположены на расстоянии MN по прямой лини (не по поверхности) и на разном удалении от края нижнего основания.
Как, используя только информацию о форме планеты и расположении маяков, вы сможете проложить самый короткий путь между ними и вычислить его длину, который не будет пролегать сквозь саму "толщу" планеты, а только по ее внешней стороне?
Миниатюры
Найти кратчайший маршрут между двумя маяками  
1
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
05.06.2026, 22:26
Ответы с готовыми решениями:

Определить кратчайший маршрут в графе, используя алгоритм Дейкстры.
Разработать и реализовать в виде программы алгоритм Дейкстры для графа заданного матрицей весовых...

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

С алгоритмом Дейкстра найти кратчайший путь в графе между парой вершин
С помощью алгоритма Дейкстра найти кратчайший путь в графе между парой вершин V0 и V* .

47
90 / 73 / 28
Регистрация: 07.12.2024
Сообщений: 142
16.06.2026, 20:03
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Nacuott Посмотреть сообщение
kitonum, в задаче тоебуется проложить самый короткий путь между маяками.Тот, что указали Вы не есть самый короткий.
Спасибо! Я ошибочно считал, что если отрезок, соединяющий 2 точки на развёртке, находится в пределах этой развёртки, то он и даёт кратчайший путь. Ошибочность особенно ясно видна на следующем примере. 2 диаметрально противоположные точки А и В лежат на поверхности цилиндра, каждая на расстоянии h от верхнего основания. Понятно, что если h достаточно мало, то зелёный путь короче красного.
Миниатюры
Найти кратчайший маршрут между двумя маяками  
1
122 / 51 / 11
Регистрация: 17.11.2021
Сообщений: 259
17.06.2026, 07:57
По моему изображение начального задания вводит в заблуждение, оно должно выглядеть примерно так:

возможно точки М и N вообще на диаметре находятся, хотя нет, вычисления показали что от оси до М ~ 4,732 и до N ~ 4,465, что вместе дает 9,197 соответственно диагональ между ними будет еще больше, а из условия расстояние между ними равно 9, но все таки должно быть очень близко к диаметру.
Пусть условно это так, тогда длина половины окружности для точки N будет ~ 14,019 (длина MN по поверхности точно больше).
Путь через "верх" - (3,736-2) + 8 + (3,736-1) = 12,473
Путь через "низ" - 2 + 10 + 1 = 13
Вывод: Путь через "верх" самый короткий.
Притянуто за уши, но вроде не очень сильно.
0
1860 / 1050 / 194
Регистрация: 24.02.2013
Сообщений: 3,173
Записей в блоге: 12
17.06.2026, 09:38
Цитата Сообщение от ura-ura Посмотреть сообщение
По моему изображение начального задания вводит в заблуждение, оно должно выглядеть примерно так:
Изображение корректно и не вводит в заблуждение.
Это что-то Вы блуждаете.
0
122 / 51 / 11
Регистрация: 17.11.2021
Сообщений: 259
17.06.2026, 12:12
Ну смотрите отрезок АВ на этом изображении однозначно равен 9,

а на начальном ну максимум 6, скажете искажение за счет изометрии, но точки М и N представлены на мой взгляд на равном удалении от наблюдателя, в следствии чего искажения быть не должно.

Кстати за счет того что это не цилиндр а конус, то самый короткий маршрут вполне может быть таким
0
1860 / 1050 / 194
Регистрация: 24.02.2013
Сообщений: 3,173
Записей в блоге: 12
17.06.2026, 14:48
ura-ura, рисунок можно нарисовать любой, важны числа , которые приложены к рисунку.
По чиcлам вы сами должны простроить точный рисунок в 3d.
Если вам это неясно, то браться за задачу не стоит.
0
76 / 385 / 63
Регистрация: 09.06.2015
Сообщений: 1,526
17.06.2026, 21:05
А, здесь типа хитрость, что вся поверхность состоит из трёх частей - составная, где две плоские части не отражаются на развёртке конической составляющей. Так это совсем школьная задачка.
0
122 / 51 / 11
Регистрация: 17.11.2021
Сообщений: 259
18.06.2026, 09:47
вычисления показали что по поверхности конуса все таки путь короче, чем через его сечения
0
1860 / 1050 / 194
Регистрация: 24.02.2013
Сообщений: 3,173
Записей в блоге: 12
18.06.2026, 10:46
Цитата Сообщение от ura-ura Посмотреть сообщение
вычисления показали что по поверхности конуса все таки путь короче, чем через его сечения
Но можно двигаться и так. И двмгаться нужно не по сечению. а по кратчайшей кпивоц-геодезической.
См картинку (левую)

Или так.
См.картинку (правую)
Миниатюры
Найти кратчайший маршрут между двумя маяками   Найти кратчайший маршрут между двумя маяками  
1
90 / 73 / 28
Регистрация: 07.12.2024
Сообщений: 142
18.06.2026, 21:40
Удалось полностью разобраться в этой задаче. Пока привожу полученные результаты. Двигаться надо через нижнее основание: сначала по геодезической на поверхности конуса до точки P (угол N1OP=11.56011178 градуса), затем по хорде нижнего основания PQ (угол N1OQ=117.2239796 градуса), затем по геодезической QM. Общее пройденное расстояние будет 11.44892542.
На первый взгляд это противоречит интуиции, т.к. конус сужается сверху и кажется, что выгоднее двигаться через верхнее основание. Но дело в том , что в совокупности точки M и N ближе к нижнему основанию и этот фактор оказывается более существенным.
Будет побольше свободного времени - оформлю код со всеми вычислениями и рисунок.
1
1860 / 1050 / 194
Регистрация: 24.02.2013
Сообщений: 3,173
Записей в блоге: 12
19.06.2026, 08:39
Цитата Сообщение от kitonum Посмотреть сообщение
Будет побольше свободного времени - оформлю код со всеми вычислениями и рисунок.
Ясно, ждем.
0
23 / 23 / 2
Регистрация: 31.05.2026
Сообщений: 26
21.06.2026, 23:55
По моим расчетам, длина геодезической при ее прохождении через нижнее основание Lg= 12.593468705206349290624,
что больше длины геодезической, проходящей только по боковой поверхности конуса Lgc= 12.076998118505042854015.
Хорошо, что хоть по Lgc мнение единое, по крайней мере, по нескольким начальным знакам.
То есть путь через нижнее основание не кратчайший.

Lg состоит из кусков следующей длины:
2.1528082016445345902 (по конусу от N до P на основании);
9.3690846549046458326 (хорда PQ окружности основания);
1.0715758486571688678 (по конусу от Q до M).

Угол под которым геодезическая пересекает окружность основания равен 69.538690986113603376508
(уже писал в теме, что со стороны основания и со стороны боковой поверхности угол пересечения равный).
2
1725 / 1163 / 302
Регистрация: 05.10.2014
Сообщений: 5,668
22.06.2026, 00:18
Цитата Сообщение от Li6-D Посмотреть сообщение
со стороны основания и со стороны боковой поверхности угол пересечения равный
Тоже догадался про это, и даже подумал как бы это почище доказать.
Но подверждение со стороны мастера сняло желание это доказывать)
0
90 / 73 / 28
Регистрация: 07.12.2024
Сообщений: 142
22.06.2026, 00:31
Да, движение с заходом на нижнее основание не самое короткое. Нашёл ошибку в своих вычислениях. Самый короткий путь будет с заходом на верхнее основание и его длина равна примерно 12.0465417, т.е всего на 0.03 короче, чем движение по геодезической на поверхности конуса.
Ниже - полный код вычислений в Maple, где разобраны все 3 варианта движения. Рисунок построен в точности по результатам вычислений.

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
restart;
M1:=[5*cos(phi),5*sin(phi),0]: N1:=[5,0,0]: S:=[0,0,18]:
# Длина образующей полного конуса 
l:=sqrt(349):
# Отношения, в которых точки N и M делят образующую 
lambda1:=2/(l-2): lambda2:=1/(l-1):
# Функции расстояний в R^3 и в R2 
dist1:=(X,Y)->sqrt((X[1]-Y[1])^2+(X[2]-Y[2])^2+(X[3]-Y[3])^2):
dist2:=(X,Y)->sqrt((X[1]-Y[1])^2+(X[2]-Y[2])^2):
N:=simplify((N1+~lambda1*~S)/~(1+lambda1));
M:=simplify((M1+~lambda2*~S)/~(1+lambda2));
# Расстояние между M и N в R^3
d:=simplify(dist1(M,N));
# Значение угла phi в радианах
phi:=solve(d=9);
# Тот же угол phi в градусах
evalf(180*%/Pi);
# Угол между N1S и M1S на развёртке
alpha:=5*phi/l;
# Тот же угол в градусах
evalf(180*%/Pi);
# Координаты точек N и M на развёртке
N:=[l-2,0]: M:=[(l-1)*cos(alpha),(l-1)*sin(alpha)]:
# Точное (символьное) значение расстояния по геодезической конуса и его приближённое значени с 20 значащими цифрами 
simplify(dist2(N,M));
`Длина пути по геодезической усечённого конуса`=evalf[20](%);
 
# Длина N2S
l1:=sqrt(4^2+(18-3.6)^2);
 
# Движение через верхнее основание
 
# Углы s=N2O1P и t=N2O1Q в R^3
P:=[4*cos(s),4*sin(s),3.6]: Q:=[4*cos(t),4*sin(t),3.6]:
# Те же углы на развёртке
s1:=4*s/l1: t1:=4*t/l1:
# Точки P и Q на развёртке
P1:=[l1*cos(s1),l1*sin(s1)]: Q1:=[l1*cos(t1),l1*sin(t1)]:
# Целевая функция (общее расстояние)
F:=dist2(N,P1)+dist1(P,Q)+dist2(Q1,M):
# График F
plot3d(F, s=0..phi,t=s..phi,  axes=normal); 
L:=Optimization:-Minimize(F, {s>=0,s<=phi,t>=s,t<=phi},initialpoint={s=0.2,t=2});
`Длина пути через верхнее основание`=L[1];
# Углы s и t в градусах
s=eval(s*180/Pi,L[2])^o; t=eval(t*180/Pi,L[2])^o; 
 
# Движение через нижнее основание
 
# Углы s=N1O1P и t=N1O1Q в R^3
P:=[5*cos(s),5*sin(s),0]: Q:=[5*cos(t),5*sin(t),0]:
# Те же углы на развёртке
s1:=5*s/l: t1:=5*t/l:
# Точки P и Q на развёртке
P1:=[l*cos(s1),l*sin(s1)]: Q1:=[l*cos(t1),l*sin(t1)]:
# Целевая функция (общее расстояние)
F:=dist2(N,P1)+dist1(P,Q)+dist2(Q1,M):
# График F
plot3d(F, s=0..phi,t=s..phi,  axes=normal); 
Optimization:-Minimize(F, {s>=0,s<=phi,t>=s,t<=phi},initialpoint={s=0.1,t=2.4});
`Длина пути через нижнее основание`=%[1];
Миниатюры
Найти кратчайший маршрут между двумя маяками   Найти кратчайший маршрут между двумя маяками   Найти кратчайший маршрут между двумя маяками  

3
23 / 23 / 2
Регистрация: 31.05.2026
Сообщений: 26
22.06.2026, 10:55
Да, через верхнее основание путь немного короче.
Такая распечатка для верхнего основания:
Code
1
2
3
4
5
6
7
8
9
10
Длина геодезической только по конусу Lgc=
12.076998118505042854014738050457339440878321503798
Угол пересечения основания в градусах xº=
62.3948681324413550591376897686796979862332580073
Длины первого, второго участков по конусу и длина среднего участка по основанию
Lg1= 3.0250215836862859361474627548811158088984959378176
Lg2= 1.9322234860239374422901608246917857346366856705269
Lgm= 7.0892966334710640405113776854836550026257596954593
Общая длина геодезической
Lg= 12.046541703181287418949001265056556546160941303804
Для нижнего:
Code
1
2
3
4
5
6
7
8
9
10
Длина геодезической только по конусу Lgc=
12.076998118505042854014738050457339440878321503798
Угол пересечения основания в градусах xº=
69.538690986113603376507943120961011300183363510552
Длины первого, второго участков по конусу и длина среднего участка по основанию
Lg1= 1.0715758486571688677955649015848165387910289317378
Lg2= 2.1528082016445345901870919921570426670392763862362
Lgm= 9.3690846549046458326413543175601694232712698846677
Общая длина геодезической
Lg= 12.593468705206349290624011211302028629101575202642
Прога:
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
r1=4;
r2=5;
h=3.6;
dl1=1;
dl2=2;
d=9;
sgn=1;          /*Через какое основание считать геодезическую (верхнее "1", нижнее "-1")*/
sa=1/sqrt((h/(r2-r1))^2+1);
r=if(sgn==1,r1,r2);
l=r/sa;
l1=r2/sa-dl1;
l2=r2/sa-dl2;
gm=sa*asin(sqrt((d^2-(l2-l1)^2)/l1/l2)/2/sa);
print"Длина геодезической только по конусу Lgc=";
print Lgc=sqrt(l1^2+l2^2-2*l1*l2*cos(2*gm));
x=gm/2+pi/4;        /*Начальное значение угла пересечения x для метода Ньютона*/
z=10;           /*Число итераций для метода Ньютона*/
y=x-acos(l/l1*cos x)/2-acos(l/l2*cos x)/2+sgn*(gm-sa*x);
py=1-sin x/sqrt((l1/l)^2-(cos x)^2)/2-sin x/sqrt((l2/l)^2-(cos x)^2)/2-sgn*sa;
x=x-y/py;
if(z--,gotor-3,0);  /*Конец итераций*/
print"Угол пересечения основания в градусах xº=";
print x*180/pi;
print"Длины первого, второго участков по конусу и длина среднего участка по основанию";
print"Lg1=",Lg1=sgn*(sqrt(l1^2-(l*cos x)^2)-l*sin x);
print"Lg2=",Lg2=sgn*(sqrt(l2^2-(l*cos x)^2)-l*sin x);
print"Lgm=",Lgm=2*sin x*r;
print"Общая длина геодезической через основание";
print"Lg=",Lg=Lg1+Lgm+Lg2;
1
1860 / 1050 / 194
Регистрация: 24.02.2013
Сообщений: 3,173
Записей в блоге: 12
23.06.2026, 11:12
kitonum, мне непонятно, что записано в вашем коде для 2d случая.
Не могли бы Вы напмсать выражение для длины пути по хорде верхнего основания планеты., которое входит в выражение для фунуции суммарного расстояния всего пути.
Как я уже писал выше, в постановке задачи требуется проложить кратчайший путь т.е. должны бвть приведены уравнения геодезичиских и отобпажены участки геодезических не прямыми линиями, а именно геодезичемкими.
Это нербходимо, - если планетяне захотят построить дорогу между маяками.
0
 Аватар для Garpedonapt
162 / 7 / 0
Регистрация: 13.04.2026
Сообщений: 32
23.06.2026, 11:23  [ТС]
Nacuott, kitonum, Li6-D, весьма благодарен вам за проявленный интерес к задаче и вычисление длин маршрутов по усеченному конусу. Я ждал несколько другой вариант решения, который оговорен в условии. Сначала проложить кротчайший путь на карте необычной планеты (на развертке, исходя из геометрических соображений), затем на основании этого получить уравнение для вычисления протяженности. Надеюсь, что эта версия решения не останется без внимания.
0
1860 / 1050 / 194
Регистрация: 24.02.2013
Сообщений: 3,173
Записей в блоге: 12
23.06.2026, 13:14
Garpedonapt, Вы имеете в виду- найти кратчайший путь используя только циркуль и линейку ?
0
1860 / 1050 / 194
Регистрация: 24.02.2013
Сообщений: 3,173
Записей в блоге: 12
23.06.2026, 13:31
kitonum, имелось в виду, что окончательно картинка должна быть похожа на такую (хорошо видны геодезические)
Миниатюры
Найти кратчайший маршрут между двумя маяками  
0
 Аватар для Garpedonapt
162 / 7 / 0
Регистрация: 13.04.2026
Сообщений: 32
23.06.2026, 15:58  [ТС]
Nacuott, нет, здесь не идет речь о построении кратчайшего пути только циркулем и линейкой (это не возможно, ну если рисовать схему на бумаге, то, пожалуйста). Вот проложить маршрут на развертке, исходя из геометрии, можно и от руки, дабы была понятна суть решения.
0
23 / 23 / 2
Регистрация: 31.05.2026
Сообщений: 26
23.06.2026, 22:53
Garpedonapt, рисунок для прокладки геодезической через верхнее основание Вложение 1535654 (почему коряво вставился )

Сверху развертка поверхности конуса, окружность снизу - исходное верхнее основание.
На рисунке развертки есть вспомогательная окружность cx радиуса rx, который изначально неизвестен.
К ней проведены из точек M и N две касательные.
Эти касательные пересекают развертку верхнего основания под одним и тем же углом x навстречу, что и нужно для геодезической.
Причем на самом верхнем основании длина дуги PQ, равная длине дуги на развертке, должна иметь угол 2x.
Циркулем и линейкой rx или x не построить - в моем коде выше решается тригонометрическое уравнение y(x)=0 методом Ньютона.
Уравнение и составлено из описанных геометрических соображений, главное правильно углы подсчитать.
В коде рассчитывается и используется в уравнении переменная gm (гамма) - это половина угла MON на развертке.
Кроме того, sa - синус угла полураствора конуса.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
23.06.2026, 22:53

Граф-цикл. Найти кратчайший путь
Доброго времени суток господа. Имеется граф цикл с вершинами 0, 1, 2, 3, 4 -&gt; 0, 1, 2, 3, 4... и...

Найти кратчайший путь обхода всех вершин графа
Доброго времени суток, форумчане! К сути самой задачи: имеется комната, по ней разбросаны синие и...

Найти кратчайший путь в орграфе
Надо, например, найти кратчайший путь, на отрезках указана длина. Как решать подобные задачи или...

Найти кратчайший путь с помощью алгоритма Дейкстры

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Модель по догадкам
anaschu 25.08.2026
Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
Запись в регистр сведений независимо от заполненности табличной части
Maks 25.08.2026
Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .
Ноутбук Альфария
kumehtar 24.08.2026
Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?
Мастера простых решений
DevAlt 23.08.2026
В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .
Цена ошибки
DevAlt 23.08.2026
Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .
Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины.
zorxor 22.08.2026
Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .
Жизня: рисунок укладки багажа, сделанный клодом
anaschu 21.08.2026
Сделал 15 снимков, он по снимкам сделал схему.
Был там один разговор по поводу свободы в материальном мире.
kumehtar 19.08.2026
Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru