Веревка

[romka_pomka]

Господа, у меня вопрос в том, насколько эта задача актуальна, имеет ли она готовое решение? Вроде бы решил ее, и думаю - стоит ли решение публикации или эта задача школьного уровня. Стоит публиковать?

Цитата:

Задача:
- между столбами натянута веревка длины L (отрезок)
- на веревке n прищепок (n точек)
- крайние прищепки отодвинуты от столбов на расстояния h и H соответственно (крайний левый отрезок имеет длину h, крайний правый отрезок имеет длину H)
- требуется разместить n-2 точки на L так, чтобы самое большое отношение двух соседних отрезков (учитывая и крайние) было как можно ближе к единице.

[gris]

Интересная задача. Даже для трёх прищепок возникают разные варианты. Может быть её формализовать и провести к разбиению единичного отрезка? Может быть это действительно известная задача? Было бы интересно с ней повозиться.

Вообще, так как для двух отрезков по крайней мере одно из отношений не меньше единицы, то можно просто минимизировать максимум всех отношений.
То есть, например, такая постановка:
Для заданных $a\geqslant b>0$ найти $\min\limits_{x\in (0;1)}\max\left\{\dfrac ax,\dfrac xa,\dfrac x{1-x},\dfrac {1-x}x,\dfrac {x-1}b,\dfrac b{x-1}\right\}$

[romka_pomka]

gris в сообщении #418918 писал(а):

Может быть это действительно известная задача?

Да, у меня тот же вопрос

Кстати, Вы эти штуки (постановку задачи) написали быстрее, чем я.

[Ales]

Отношения: $x_1, ...,x_{n}>0$.
Условие:
$h\cdot x_1 \cdot ... \cdot x_{n} = H>h$,
$h+h\cdot x_1+...+h\cdot x_1 \cdot ... \cdot x_{n}=L$.
Требуется $max(x_i) \to min$.

Или так отрезки: $x_1, ...,x_{n-1}>0$.
Условие: $x_1+ ...+x_{n-1}=L-H-h$.
Требуется: $max(\frac {x_1} h, \frac {x_{i+1}} {x_i},\frac H {x_{n-1}}) \to min$.

[romka_pomka]

Ales в сообщении #418972 писал(а):

Скорее всего, задача решается перебором.

Спорить не стану, очень может быть. Однако подозреваю, что первый пост темы Вы прочитали невнимательно... и второй тоже, раз не избавились сразу от одного параметра.

[Ales]

Задача не тривиальная. Мне кажется, что она не школьного уровня.

-- Ср мар 02, 2011 14:19:26 --

Может быть, она и решается.

Но часто задачи такого типа решаются только перебором. При больших $n$ это невозможно сделать.
Если нет решения, то интересен вопрос об NP-полноте.

[Ales]

Ales в сообщении #418972 писал(а):

Отношения: $x_1, ...,x_{n}>0$.
Условие:
$h\cdot x_1 \cdot ... \cdot x_{n} = H>h$,
$h+h\cdot x_1+...+h\cdot x_1 \cdot ... \cdot x_{n}=L$.
Требуется $max(x_i) \to min$.

Или так отрезки: $x_1, ...,x_{n-1}>0$.
Условие: $x_1+ ...+x_{n-1}=L-H-h$.
Требуется: $max(\frac {x_1} h, \frac {x_{i+1}} {x_i},\frac H {x_{n-1}}) \to min$.

Еще конечно надо добавить и условие на обратные отношения.

[romka_pomka]

Ales в сообщении #418983 писал(а):

часто задачи такого типа решаются только перебором. При больших $n$ это невозможно сделать.
Если нет решения, то интересен вопрос об NP-полноте.

Прошу извинить мою непонятливость, но что именно следует перебирать в этой задаче?
Вопрос о NP-полноте мне тоже интересен (что здесь - алфавит?).

[gris]

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

[Ales]

romka_pomka в сообщении #419010 писал(а):

Прошу извинить мою непонятливость, но что именно следует перебирать в этой задаче?

Разные вершины $n$- мерного линейного выпуклого объема.
Может быть, перебор можно сократить.

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

-- Ср мар 02, 2011 16:35:20 --

Это наверное, задача линейного программирования.

[romka_pomka]

gris в сообщении #419015 писал(а):

Перебирать различные разбиения отрезка, наверное.

Имеется ввиду перебор значений переменной x из второго поста?

Ales в сообщении #419017 писал(а):

Разные вершины $n$- мерного линейного выпуклого объема.

Вы имеете ввиду куб? Тогда не очевидно, что точкой касания будет вершина.

Ales в сообщении #419017 писал(а):

Но ведь Вы решили задачу. Значит, придумали эффективный алгоритм.
Это наверное, задача линейного программирования.

Осталось одно темное место: на настоящий момент я ее кажется решил. Задача возникла из желания оптимизировать одномерную неравномерную сетку для численного расчета.
==========
Господа, благодарю вас. Ход Ваших рассуждений по крайней мере схож с моим. Значит, я хотя бы не перемудрил и задача похожа на нетривиальную.

[Ales]

romka_pomka в сообщении #419021 писал(а):

Вы имеете ввиду куб? Тогда не очевидно, что точкой касания будет вершина.

Не куб, а объем, ограниченный условиями на отношения. Это линейный объект.

[romka_pomka]

Ales в сообщении #419026 писал(а):

romka_pomka в сообщении #419021 писал(а):

Вы имеете ввиду куб? Тогда не очевидно, что точкой касания будет вершина.

Не куб, а объем, ограниченный условиями на отношения. Это линейный объект.

Извиняюсь, это я забежал чуть вперед или совсем не понял Вас. Благодарю.

-- Ср мар 02, 2011 20:15:35 --

gris в сообщении #419015 писал(а):

искомый максимум будет не больше у отсортированного по возрастанию длин частей.
Увы, это не верно.

да, у меня получилось придумать контрпример.

[Ales]

romka_pomka в сообщении #419028 писал(а):

Извиняюсь, это я забежал чуть вперед или совсем не понял Вас. Благодарю.

Условие $x_1+ ...+x_{n-1}=L-H-h$.
Выпуклый линейный объем:
$x_1, ...,x_{n-1}>0 $
$\frac h t \le x_1 \le t \cdot h $
$x_{i+1} \le t \cdot x_i $
$x_i \le t \cdot x_{i+1}$
$\frac H t \le x_{n-1} \le t \cdot H$.
Его вершина - искомая точка. Надо только подобрать такое $t$, чтобы вершина удовлетворяла условию.

Если в тупую - перебором, то выписать порядка $n\cdot 2^n$ уравнений на $t$.
Найти решения. Найти минимальное $t$, по всем уравнениям и решениям.

[romka_pomka]

Ales в сообщении #419036 писал(а):

romka_pomka в сообщении #419028 писал(а):

Извиняюсь, это я забежал чуть вперед или совсем не понял Вас. Благодарю.

Условие $x_1+ ...+x_{n-1}=L-H-h$.
Выпуклый линейный объем:
$x_1, ...,x_{n-1}>0 $
$\frac h t \le x_1 \le t \cdot h $
$x_{i+1} \le t \cdot x_i $
$x_i \le t \cdot x_{i+1}$
$\frac H t \le x_{n-1} \le t \cdot H$.
Его вершина - искомая точка. Надо только подобрать такое $t$, чтобы вершина удовлетворяла условию.

Если в тупую - перебором, то выписать порядка $n\cdot 2^n$ уравнений на $t$.
Найти решения. Найти минимальное $t$, по всем уравнениям и решениям.

Спасибо, теперь понятно.
Если записать этот линейный объект в терминах первой Вашей формулировки, то получится ли куб?