Нахождение минимума суммы для массивов (на примере времени)

[SoGuit]

Здравствуйте. Передо мной стоит следующая задача. Определенная производственная установка заключает в себе три вращающиеся детали. Сразу условимся, что вращаются они не одновременно. Пределов вращения нет, а от предыдущего угла к настоящему каждая деталь вращается по наикратчайшему маршруту (т.е. от 350 до 10 градусов движение займет лишь 20 градусов). Каждая деталь также имеет различную скорость вращения. Итак, у нас есть таблица данных для оперирования подобного устройства (как, например:
№ |д. 1|д. 2|д. 3|
----------------------
1 | 20 | 39 | 148|
2 | 174| 22 | 46 |
3 | 317| 9 | 352|
...
и т.д.), где указано, какие углы должны быть у каждой детали в случае каждой операции. Естественно переход от одной позиции к другой занимает время. Задача сводится к тому, чтобы его максимально сократить путем перестановки операций в расписании (представленных в таблице строчками). Т.е. предстоит создать весьма утонченный сортировочный алгоритм.
В случае одной лишь детали задача, как мне кажется, решается довольно просто, т.к. лишь надо на воображаемом круге выбирать всякий раз наименьшую хорду, соединяющую последнее значение с выбираемым. Однако проблема многократно усложняется присутствием двух других элементов. Поделитесь, пожалуйста, своими соображениями.

[Руст]

Правильно я вас понял. У вас есть массив чисел $a_{i,j}, \ i=1,2,...,n, \ j=1,2,3$. Надо найти такую перестановку номеров i, чтобы

$$\sum_j w_j \sum_{i=1}^{n-1} |a_{\sigma(i),j}-a_{\sigma(i+1),j}|$$

, была минимальной. Здесь |a-b| вычисляется по модулю 360, т.е. |a-b|=min (|a-b|,360-|a-b|).

[SoGuit]

В общем, да. Я бы записал:

\[ \sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = 1}^3 {\left( {\left| {a_{i,j} - a_{(i + 1),j} } \right| \cdot \sigma (j)} \right)} } \]

, где

\[ \sigma (j) \]

- функция скорости (а скорость, как я уже говорил, для всех деталей различна), а

\[ {\left| {a_{i,j} - a_{(i + 1),j} } \right|} \]

- по модулю 360. Вот именно этого выражения, если я сам окончательно не запутался, мы и ищем минимум.

[ИСН]

Месье случайно не кристаллограф?

[SoGuit]

Э нет. ) Мсье больше программист с физико-математическим прошлым. Подзабытым, к сожалению, прошлым. Посему и обращаюсь.

[ИСН]

Ну надо же, а формулировка прямо как будто оттуда.
По сути, получается что-то вроде задачи коммивояжёра.

[Руст]

ИСН писал(а):

Ну надо же, а формулировка прямо как будто оттуда.
По сути, получается что-то вроде задачи коммивояжёра.

Нет, в отличии от задачи коммивояжера здесь расстояния не произвольны и она решается полиномиально.

[dmd]

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

Мог бы автор топика привести все числовые данные задачи? Сколько всего будет поворотов, каковы скорости? Мне захотелось ее численно решить. Или задача стоит чисто теоретически и конкретных данных нет?

[SoGuit]

То, что в принципе надо делить, я знаю, но ведь функцию скорости можно представить и как дробь, значение которой будет решать знаменатель. Пример числовых данных:
{13, 105, 90}
{7, 350, 31}
{332, 50, 29}
{192, 145, 0}
{274, 10, 0}
{0, 30, 0}
{60, 170, 0}
{155, 0, 0}
{163, 0, 0}
{177, 5, 0}
{332, 335, 335}
{16, 355, 270}
Читать таблицу следует, как и приведенную ранее. Значения даны в углах. Скорости 1ой, 2ой и 3ей деталей соответственно равны 6, 4.14 и 3.55 гр./сек.

[Руст]

Для такой короткой последовательности несложно и полный перебор прогнать на компьютере. Хотя существует полиномиальный алгоритм, вряд ли целесообразен составлять сложную программу для короткой задачи.

[SoGuit]

Это ведь только пример, операций может быть больше, чем 12. Например, 20! = 2432902008176640000 - именно столько комбинаций придется перебрать, если увеличить количество операций на 8. Да и метод грубой силы - это антинаучно.
Мне кажется, что, если начав с любого номера, вычислять каждый раз, какая следующая операция будет иметь минимальный индекс времени, то получим n (равное общему количеству операций, 12 в данном случае) оптимизированных комбинаций, из которых останется лишь выбрать самую быструю. Единственное - я еще не занялся полным обоснованием данного алгоритма.

[Руст]

Не совсем так. Полиномиальный алгоритм здесь следующий. Вначале вычисляете матрицу расстояний D(1,i,j) от i - ой к j-jой. Потом матрицу расстояний через одного D(2,i,j)=min(D(1,i,k)+D(1,k,j)). Далее D(3,i,j)=min(D(2,i,k)+D(1,k,j)) и т.д. При этом ещё нужно иметь массив K(a,i,j), указывающий через какие а вершины проходит маршрут от i к j . Соответственно при вычислении D(a+1,i,j)=min(D(a,i,k)+D(1,k,j)) надо пробегать только по тем k, которые содержат j в своём маршруте. Минимальный из D(n-1,i,j) и даст оптимальный маршрут.

[SoGuit]

Думаю, что идею я понял, однако обозначения немного сбивают с толку. Можно ли немного пояснить, что Вы обозначаете i, j, k и а? Как мне кажется, предложенный алгоритм есть ни что иное как перебор. А если учесть еще и сложность вычисления матриц по сравнению с простым подсчетом расстояний (углов в данном случае), то выгода компьютерного подсчета весьма сомнительна. Однако, может, я чего-то недопонял.

[Руст]

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

[SoGuit]

Но ведь в матрицы загоняются, фактически, все значения, а далее идет выборка по серии минимумов, что есть то же самое, что я предложил в словесной форме. И все-таки, если не сложно, можно ли описать процедуру чуть детальнее с простейшим численным примером?