Минимизация времени в пути

Question

[Обновления внизу (, включая исходный код решения )]

У меня сложная бизнес-проблема, которую компьютер может помочь решить.

По горному региону течетдлинная извилистая река с сильным течением.Вдоль определенных частей реки расположены участки экологически чувствительной земли, пригодной для выращивания особого вида редких фруктов, которые пользуются очень высоким спросом.Как только полевые рабочие собирают фрукты, начинают тикать часы, чтобы доставить фрукты на завод по переработке.Это очень дорого, чтобы попытаться отправить фрукты вверх по течению или по суше или по воздуху.Безусловно, наиболее экономически эффективным механизмом их доставки на завод является поток в контейнерах, питаемых исключительно постоянным течением реки.У нас есть возможность построить 10 перерабатывающих заводов, и мы должны расположить их вдоль реки, чтобы минимизировать общее время, которое фрукты проводят в пути.Однако плоды могут занять много времени, прежде чем они достигнут ближайшего нижестоящего растения, но это напрямую влияет на цену, по которой они могут быть проданы.По сути, мы хотим минимизировать сумму расстояний до ближайшего соответствующего нижестоящего предприятия.Растение может быть расположено всего в 0 метрах ниже по течению от точки доступа к фруктам.

Вопрос заключается в следующем: чтобы максимизировать прибыль, как далеко вверх по реке мы должны построить 10 перерабатывающих заводов, если мы нашли 32районы плодоводства, где расстояния до верховья реки от основания (в метрах): 10, 40, 90, 160, 250, 360, 490, ... (n ^ 2) * 10 ... 9000, 9610, 10320?

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

ОБНОВЛЕНИЯ

---

Обновление 1: забыл добавить: я верюэтот вопрос является частным случаем этого .

Update2: один алгоритм, который я написал, дает ответ за доли секунды, и я считаю, что rвсе хорошо (но это еще не стабильно по значениям выборки).Я дам более подробную информацию позже, но суть в следующем.Разместите растения на равных расстояниях.Переберите все внутренние заводы, где на каждом заводе вы пересчитываете его положение, проверяя каждое местоположение между двумя соседями, пока проблема не будет решена в этом пространстве (жадный алгоритм).Таким образом, вы оптимизируете завод 2, удерживая 1 и 3 фиксированными.Затем установка 3 удерживает 2 и 4 фиксированными ... Когда вы достигаете конца, вы возвращаетесь назад и повторяете, пока не пройдете полный цикл, в котором пересчитанное положение каждого перерабатывающего завода перестает меняться ... также в конце каждого цикла вы пытаетесь двигатьсяперерабатывающие заводы, которые переполнены рядом друг с другом и находятся рядом с фруктовыми отвалами друг друга в регионе, где фруктовые отсеки находятся далеко.Есть много способов изменить детали и, следовательно, точный ответ.У меня есть другие подходящие алгоритмы, но у всех есть глюки.[Я опубликую код позже.] Так же, как Майк Данлавей упоминал ниже, мы, вероятно, просто хотим «достаточно хорошо».

Чтобы дать представление о том, что может быть «достаточно хорошим» результатом:

10010 total length of travel from 32 locations to plants at 
{10,490,1210,1960,2890,4000,5290,6760,8410,9610}

Обновление 3: mhum сначала дал правильное точное решение, но (пока) не опубликовал программу или алгоритм, поэтому я написал одно, которое выдает те же значения.

/************************************************************
This program can be compiled and run (eg, on Linux):
$ gcc -std=c99 processing-plants.c -o processing-plants
$ ./processing-plants
************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//a: Data set of values. Add extra large number at the end

int a[]={
10,40,90,160,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240,99999
};

//numofa: size of data set

int numofa=sizeof(a)/sizeof(int);

//a2: will hold (pt to) unique data from a and in sorted order.

int *a2;

//max: size of a2

int max;

//num_fixed_loc: at 10 gives the solution for 10 plants

int num_fixed_loc;

//xx: holds index values of a2 from the lowest error winner of each cycle memoized. accessed via memoized offset value. Winner is based off lowest error sum from left boundary upto right ending boundary.
//FIX: to be dynamically sized.

int xx[1000000];

//xx_last: how much of xx has been used up

int xx_last=0;

//SavedBundle: data type to "hold" memoized values needed (total traval distance and plant locations) 

typedef struct _SavedBundle {
    long e;
    int xx_offset;
} SavedBundle;

//sb: (pts to) lookup table of all calculated values memoized

SavedBundle *sb;  //holds winning values being memoized

//Sort in increasing order.

int sortfunc (const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

/****************************
Most interesting code in here
****************************/

long full_memh(int l, int n) {
    long e;
    long e_min=-1;
    int ti;

    if (sb[l*max+n].e) {
        return sb[l*max+n].e;  //convenience passing
    }
    for (int i=l+1; i<max-1; i++) {
        e=0;
        //sum first part
        for (int j=l+1; j<i; j++) {
            e+=a2[j]-a2[l];
        }
        //sum second part
        if (n!=1) //general case, recursively
            e+=full_memh(i, n-1);
        else      //base case, iteratively
            for (int j=i+1; j<max-1; j++) {
                e+=a2[j]-a2[i];
            }
        if (e_min==-1) {
            e_min=e;
            ti=i;
        }
        if (e<e_min) {
            e_min=e;
            ti=i;
        }
    }
    sb[l*max+n].e=e_min;
    sb[l*max+n].xx_offset=xx_last;
    xx[xx_last]=ti;      //later add a test or a realloc, etc, if approp
    for (int i=0; i<n-1; i++) {
        xx[xx_last+(i+1)]=xx[sb[ti*max+(n-1)].xx_offset+i];
    }
    xx_last+=n;
    return e_min;
}

/*************************************************************
Call to calculate and print results for given number of plants
*************************************************************/

int full_memoization(int num_fixed_loc) {
    char *str;
    long errorsum;  //for convenience

    //Call recursive workhorse
    errorsum=full_memh(0, num_fixed_loc-2);
    //Now print
    str=(char *) malloc(num_fixed_loc*20+100);
    sprintf (str,"\n%4d %6d {%d,",num_fixed_loc-1,errorsum,a2[0]);
    for (int i=0; i<num_fixed_loc-2; i++)
        sprintf (str+strlen(str),"%d%c",a2[ xx[ sb[0*max+(num_fixed_loc-2)].xx_offset+i ] ], (i<num_fixed_loc-3)?',':'}');
    printf ("%s",str);
    return 0;
}

/**************************************************
Initialize and call for plant numbers of many sizes
**************************************************/

int main (int x, char **y) {
    int t;
    int i2;

    qsort(a,numofa,sizeof(int),sortfunc);
    t=1;
    for (int i=1; i<numofa; i++)
        if (a[i]!=a[i-1])
            t++;
    max=t;
    i2=1;
    a2=(int *)malloc(sizeof(int)*t);
    a2[0]=a[0];
    for (int i=1; i<numofa; i++)
        if (a[i]!=a[i-1]) {
            a2[i2++]=a[i];
        }
    sb = (SavedBundle *)calloc(sizeof(SavedBundle),max*max);
    for (int i=3; i<=max; i++) {
        full_memoization(i);
    }
    free(sb);
    return 0;
}

Answer 1

Позвольте мне привести простой пример алгоритма Метрополис-Гастингс . Предположим, у вас есть вектор состояния x и функция соответствия качества P (x) , которая может быть любой функцией, которую вы хотите написать.

Предположим, у вас есть случайное распределение Q , которое вы можете использовать для изменения вектора, например x' = x + N(0, 1) * sigma, где N - простое нормальное распределение около 0, а sigma - стандартное отклонение по вашему выбору.

p = P(x);
for (/* a lot of iterations */){
  // add x to a sample array
  // get the next sample
  x' = x + N(0,1) * sigma;
  p' = P(x');
  // if it is better, accept it
  if (p' > p){
    x = x';
    p = p';
  }
  // if it is not better
  else {
    // maybe accept it anyway
    if (Uniform(0,1) < (p' / p)){
      x = x';
      p = p';
    }
  }
}

Обычно это выполняется со временем выгорания, может быть, 1000 циклов, после чего вы начинаете сбор образцов. После еще, может быть, 10 000 циклов, среднее число выборок - это то, что вы берете в качестве ответа.

Требуется диагностика и настройка. Как правило, образцы наносятся на график, и вам нужен «нечеткий гусеничный» график, который стабилен (не сильно перемещается) и имеет высокий коэффициент приема (очень нечеткий). Основным параметром, с которым вы можете играть, является sigma . Если sigma слишком мала, сюжет будет размытым, но он будет блуждать. Если он слишком большой, график не будет размытым - он будет иметь горизонтальные сегменты. Часто начальный вектор x выбирается случайным образом, и часто выбирается несколько начальных векторов, чтобы увидеть, оказываются ли они в одном месте.

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

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

В приложениях, с которыми я знаком, P (x) является мерой вероятности, и обычно она находится в лог-пространстве, поэтому она может варьироваться от 0 до отрицательной бесконечности. Затем для шага «возможно принять» это (exp(logp' - logp))

Answer 2

Если я не допустил ошибку, вот точные решения (полученные с помощью подхода динамического программирования ):

N  Dist  Sites
2  60950 {10,4840}
3  40910 {10,2890,6760}
4  30270 {10,2250,4840,7840}
5  23650 {10,1690,3610,5760,8410}
6  19170 {10,1210,2560,4410,6250,8410}
7  15840 {10,1000,2250,3610,5290,7290,9000}
8  13330 {10,810,1960,3240,4410,5760,7290,9000}
9  11460 {10,810,1690,2890,4000,5290,6760,8410,9610}
10 9850  {10,640,1440,2250,3240,4410,5760,7290,8410,9610}
11 8460  {10,640,1440,2250,3240,4410,5290,6250,7290,8410,9610}
12 7350  {10,490,1210,1960,2890,3610,4410,5290,6250,7290,8410,9610}
13 6470  {10,490,1000,1690,2250,2890,3610,4410,5290,6250,7290,8410,9610}
14 5800  {10,360,810,1440,1960,2560,3240,4000,4840,5760,6760,7840,9000,10240}
15 5190  {10,360,810,1440,1960,2560,3240,4000,4840,5760,6760,7840,9000,9610,10240}
16 4610  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,7290,8410,9000,9610,10240}
17 4060  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,7290,7840,8410,9000,9610,10240}
18 3550  {10,360,810,1210,1690,2250,2890,3610,4410,5290,6250,6760,7290,7840,8410,9000,9610,10240}
19 3080  {10,360,810,1210,1690,2250,2890,3610,4410,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
20 2640  {10,250,640,1000,1440,1960,2560,3240,4000,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
21 2230  {10,250,640,1000,1440,1960,2560,3240,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
22 1860  {10,250,640,1000,1440,1960,2560,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
23 1520  {10,250,490,810,1210,1690,2250,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
24 1210  {10,250,490,810,1210,1690,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
25 940   {10,250,490,810,1210,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
26 710   {10,160,360,640,1000,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
27 500   {10,160,360,640,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
28 330   {10,160,360,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
29 200   {10,160,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
30 100   {10,90,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
31 30    {10,90,160,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}
32 0     {10,40,90,160,250,360,490,640,810,1000,1210,1440,1690,1960,2250,2560,2890,3240,3610,4000,4410,4840,5290,5760,6250,6760,7290,7840,8410,9000,9610,10240}