Есть 4 города расположенные в вершинах квадрата.
Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
Можно создавать перекрёстки.

А есть алгоритмическое решение такой задачи?

Если есть, то какое?

Диагонали не подходят!

Есть только одна комбонация:
+ . . . . . +
.\ . . . . /
. \ . . . /
. .\_____/
. ./ . . \
. / . . . \
./ . . . . \
+ . . . . . +

Если принять сторону квадрата за 1, то общая длина равна 2.73 (Доказано) (диагональ 2.82)
Осталось доказать:
Является эта конфигурация минимальной?

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

C>Есть 4 города расположенные в вершинах квадрата.
C>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>Можно создавать перекрёстки.

C>А есть алгоритмическое решение такой задачи?

C>Если есть, то какое?

C>Диагонали не подходят!

C>Есть только одна комбонация:
C>+ . . . . . +
C>.\ . . . . /
C>. \ . . . /
C>. .\_____/
C>. ./ . . \
C>. / . . . \
C>./ . . . . \
C>+ . . . . . +

C>Если принять сторону квадрата за 1, то общая длина равна 2.73 (Доказано) (диагональ 2.82)
C>Осталось доказать:
C>Является эта конфигурация минимальной?

Может можно посчитать производную длины дороги(общую) и найти ее корень — это и есть доказательство минимума?

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

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

C>>Есть 4 города расположенные в вершинах квадрата.
C>>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>>Можно создавать перекрёстки.

C>>А есть алгоритмическое решение такой задачи?

C>>Если есть, то какое?

C>>Диагонали не подходят!

C>>Есть только одна комбонация:
C>>+ . . . . . +
C>>.\ . . . . /
C>>. \ . . . /
C>>. .\_____/
C>>. ./ . . \
C>>. / . . . \
C>>./ . . . . \
C>>+ . . . . . +

C>>Если принять сторону квадрата за 1, то общая длина равна 2.73 (Доказано) (диагональ 2.82)
C>>Осталось доказать:
C>>Является эта конфигурация минимальной?

A>Может можно посчитать производную длины дороги(общую) и найти ее корень — это и есть доказательство минимума?
Например?

для этого рисунка минимум доказан через экстремум функции.

Надо узнать: есть ещё меньшие комбинации построения дорог.

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

C>>>Осталось доказать:
C>>>Является эта конфигурация минимальной?

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

Поэтому если и есть перекрёстки не в исходных вершинах, то это знаки мерседеса — схождения 3-х лучей под углом 120 гр.

Отсюда легко показать, что 2 внутренних мерседеса — единственная конфигурация для 4-угольника.
3 мерседеса — для 5 угольника — и это последний случай, когда внутренние перекрёстки позволяют укоротить сеть.
Для правильного 6-угольника в в вершинах уже 120 градусов и введение внутренних перекрёстков не нужно.
Для правильных многоугольников с числом вершин большим 5 кратчайшая сеть — по периметру.
Для неправильных имхо — отрезки по биссектрисе из всех угов острее 120 градусов и замена таким образом слишком острых углов. Далее — по периметру того, что получилось.

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

Например, вот такие квадраты "непрозрачны"

o----------o     o----------o     o         o
|                           |      \       /
|                           |       \_____/
|                    ,'     |       /     \
|                  ,'       |      /       \
o----------o     o'         o     o         o

1. Не понял, за что Pushkin баллы поставил — я же только задачу написал.
2. Ну, разумеется, суммарная длина отрезков должна быть минимальна. Я это как-то упустил в условии.
3. Когда я ее решал года 3-4 назад, я пришел к 3-му варианту и нашел там длины этих отрезков. Но выбор конфигурации был несколько произволен: я просто рассмотрел несколько конфигураций и искал для каждого из них минимум суммарной длины. При этом нет основания считать, что я перебрал ВСЕ возможные конфигурации (а все перебрать и невозможно, там целая бесконечность совершенно нелепых).

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

C>Есть 4 города расположенные в вершинах квадрата.
C>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>Можно создавать перекрёстки.

Данная задача является задачей Штейнера — и в общем виде не имеет решения за какое-либо приемлемое время. Материалов инете на эту тему полно.

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

RS>1. Не понял, за что Pushkin баллы поставил — я же только задачу написал.

Хорошая задача ценнее десяти решений.
Мне очень понравилась.

RS>3. Когда я ее решал года 3-4 назад, я пришел к 3-му варианту и нашел там длины этих отрезков. При этом нет основания считать, что я перебрал ВСЕ возможные конфигурации

Я почти могу доказать.
1) Ясно, что из каждой вершины должна выходить линия. Иначе вершину можно срезать.
2) Делаем как и в предыдущем случае. Рассмотрим какой-то внутренний перекрёсток.
В нём пересекается по меньшей мере две линии. Если угол пересечения меньше 120 градусов, то легко показать, что передвижение точки пересечения внутрь угла по биссектрисе и соединение её отрезком со старой точкой а) уменьшает длину сети б) не изменяет прозрачности (описанный треугольник тот же). Поэтому все перекрёстки внутри должны быть мерседесами.
3) Не могу доказать, что висячих концов быть не должно, а то бы сразу получил твой третий вариант.

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

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

C>>Есть 4 города расположенные в вершинах квадрата.
C>>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>>Можно создавать перекрёстки.

S>Данная задача является задачей Штейнера — и в общем виде не имеет решения за какое-либо приемлемое время.

Для 4-х городов в вершинах квадрата?

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

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

C>>Есть 4 города расположенные в вершинах квадрата.
C>>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>>Можно создавать перекрёстки.

S>Данная задача является задачей Штейнера — и в общем виде не имеет решения за какое-либо приемлемое время. Материалов инете на эту тему полно.

А инет то не халявный!!!!

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

RS>Требуется найти множество отрезков, зеликом размещенных внутри (включая стороны) квадрата, так, чтобы не существовало прямой, пересекающей квадрат и не пересекающей при этом один из внутренних отрезков.
RS>Например, вот такие квадраты "непрозрачны"

RS>

RS>o----------o     o----------o     o         o
RS>|                           |      \       /
RS>|                           |       \_____/
RS>|                    ,'     |       /     \
RS>|                  ,'       |      /       \
RS>o----------o     o'         o     o         o
RS>

После долгих попыток доказать невыгодность "висячих" отрезков (как в варианте 2), неожиданно обнаружил, что они выгодны! Уже вариант 2 даёт чуть меньшую лину, чем вариант 3 (2.71<2.73). Но ведь его можно ещё улучшить, заменив прямой угол на знак мерседеса!

  o         o
    ' ,   ,'
        ''  
      ,   '      
    ,'     ,     
  o'        o

Имеем ряд длин
3.00 — варианта 1 (незавершённый периметр)
2.82 — ненарисованный вариант с пересекающимися диагоналями
2.73 — вариант 3 (оптимальный в задаче о сети дорог)
2.64 — последний вариант (мерседес + висячий отрезок)

Если последний вариант оптимален (а после долгого медитирования я в это сильно верю), то мы имеем забавнейшую картину. Решение задачи о кратчайшей сети дорог разрушила высокую симметрию квадрата — 3 независимых оси отражения — выкинув одну ось — диагональ. (Иными словами существует 2 разных решения, переходящих друг в друга при отражении от диагонали.) Решение похожей, но как выяснилось, совершенно другой задачи о кратчайшей закраске разрушило симметрию ещё сильнее — выкинув уже 2 оси — вертикальную и горизонтальную. (Существует 4 разных равнооптимальных решения, переходящих друг в друга при вертикальных и горизонтальных отражениях).

Далее. Интересно посмотреть, как обстоят дела для старших многоугольников. В задаче о кратчайшей сети уже 6-угольник имел решение в виде незамкнутого периметра, и все высшие тоже. Для кратчайшей же закраски 6-угольника легко найти решение с длиной меньше 5 (мой рекорд — 4.46). С другой стороны, ясно, что окружность никак не сделаешь непрозрачной, не обведя её. Таким образом встаёт вопрос о минимальном количестве вершин правильного многоугольника, при котором кратчайшей закраской становится незамкнутый периметр. Я не знаю ответа.

Кроме того, остаётся много других вопросов:
— можно ли чего-то доказать, кроме того, что три и более дороги сходятся мерседесом?
— можно ли доказать, например, что изломы с углом больше 120 градусов невыгодны?
— можно ли доказать, что отрезки с ДВУМЯ висячими вершинами невыгодны?
— как нибудь можно запрограмить хоть какой-нить перебор?

Замечательная однако задача.
Ни фига не понятно

Здравствуйте, Pushkin.

Так че, висячий+мерседес еще короче? Че-то я упустил, когда решал.
А полный перебор возможен, если вспомнить, что отрезок — это геометрическое место точек. Но это на века.

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

RS>Здравствуйте, Pushkin.

RS>Так че, висячий+мерседес еще короче? Че-то я упустил, когда решал.

Точно короче, почти на целую десятую!

RS>А полный перебор возможен, если вспомнить, что отрезок — это геометрическое место точек. Но это на века.

Если доказать, что невозможны пологие изломы (а на то сильно похоже), то внутри останутся только мерседесы и висячие отрезки. Тогда перебор сводится к постепенному увеличению количества внутренних (добавленных) вершин, их расположению внутри фигуры и разбиению множества всех вершин на пары и тройки для висяков и мерседесов. Несколько внутренних вершин в квадрате 10x10 имхо вполне реально погонять.

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

C>Есть 4 города расположенные в вершинах квадрата.
C>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>Можно создавать перекрёстки.

C>А есть алгоритмическое решение такой задачи?

C>Если есть, то какое?

C>Диагонали не подходят!

C>Есть только одна комбонация:
C>+ . . . . . +
C>.\ . . . . /
C>. \ . . . /
C>. .\_____/
C>. ./ . . \
C>. / . . . \
C>./ . . . . \
C>+ . . . . . +

Так вот, это типичная задача, которая в общем случае, или если быть точным на я зыке теории алгоритмов, называется Геометрическое дерево Штейнера. Полиномиального алгоритма для ее решения не существет, если есть желание могу доказать. А это частный случай этой задачи. Так вот углы между ребрами, которые получиились в следствии выставления допю точек(лежат внутри квадрата), должны составлять угол в 120 градусов.

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

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

C>>Есть 4 города расположенные в вершинах квадрата.
C>>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>>Можно создавать перекрёстки.

S>Данная задача является задачей Штейнера — и в общем виде не имеет решения за какое-либо приемлемое время. Материалов инете на эту тему полно.

Но это смотря что называеть приемлемым решением!!! За полиномиальное нет.