Максимальный объем ящика

Question

Попытка написать простое веб-приложение для решения следующей распространенной проблемы исчисления в JavaScript.

Предположим, вы хотите сделать коробку с открытым верхом из плоского куска картона, которыйимеет длину L и ширину Ш , вырезая квадрат одинакового размера из каждого угла и затем складывая створки, чтобы сформировать коробку, как показано ниже:

Вы хотите узнать, насколько велики размеры вырезанных квадратов, чтобы максимизировать объем коробки.

В идеале я хочу избегать использования какой-либо библиотеки исчислений для решения этой проблемы.

Мое первоначальное наивное решение:

// V = l * w * h
function getBoxVolume(l, w, h) {
  return (l - 2*h)*(w - 2*h)*h;
}

function findMaxVol(l, w) {
  const STEP_SIZE = 0.0001;

  let ideal_h = 0;
  let max_vol = 0;

  for (h = 0; h <= Math.min(l, w) / 2; h = h + STEP_SIZE) {
    const newVol = getBoxVolume(l, w, h);
    if (max_vol <= newVol) {
      ideal_h = h;
      max_vol = newVol;
    } else {
      break;
    }
  }

  return {
    ideal_h,
    max_vol
  }
}

const WIDTH_1 = 20;
const WIDTH_2 = 30;

console.log(findMaxVol(WIDTH_1, WIDTH_2))

// {
//   ideal_h: 3.9237000000038558,
//   max_vol: 1056.3058953402121
// }

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

Answer 1

У вас есть объективная функция : getBoxVolume().Ваша цель состоит в том, чтобы максимизировать значение этой функции.

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

Обратите внимание на что-то в вашей целевой функции: она выпуклая.То есть он начинает расти (когда h = 0, объем равен нулю, затем растет, как h), достигает максимума, затем падает, в конце концов достигает нуля (когда h = min(l,w)/2).

Это означает, что максимальное значение one гарантировано, и вам просто нужно его найти.Это делает эту проблему отличным случаем для бинарного поиска , потому что, учитывая характер функции, вы можете выбрать две точки функции и узнать, в каком направлении лежит максимум относительно этих двухточки.Вы можете использовать это с тремя точками за раз (слева, справа, посередине), чтобы выяснить, находится ли максимум между левым и средним, или средним и правым.Как только эти значения приблизятся друг к другу (они находятся в некотором фиксированном количестве e друг от друга), вы можете вернуть значение функции там.Вы даже можете доказать, что возвращаемое вами значение находится в пределах некоторого значения e' от максимального возможного значения.

Вот псевдокод:

max(double lowerEnd, upperEnd) {

    double midPoint = (upperEnd + lowerEnd) / 2

    double midValue = getBoxVolume(l, w, midpoint)

    double slope = (getBoxVolume(l, w, midpoint + epsilon) - midValue) / epsilon

    if (Math.abs(slope) < epsilon2) { // or, if you choose, if (upperEnd - lowerEnd < epsilon3)
        return midpoint
    }

    if (slope < 0) { // we're on the downslope
        return max(lowerEnd, midPoint)
    }

    else { // we're on the up-slope
        return max(midpoint, upperEnd)
    }
}

Answer 2

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

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

// V = l * w * h
function getBoxVolume(l, w, h) {
  return (l - 2*h)*(w - 2*h)*h;
}

// ax^2 + bx + c = 0
function solveQuad(a, b, c) {
  var x1 = (-1 * b + Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
  var x2 = (-1 * b - Math.sqrt(Math.pow(b, 2) - (4 * a * c))) / (2 * a);
  return { x1, x2 };
}

function findMaxVol(l, w) {    
  // V'(h) = 12h^2-4(l+w)h+l*w - second degree polynomial
  // solve to get the critical numbers
  const result = solveQuad(12, -4*(l + w), l*w)

  const vol1 = getBoxVolume(l, w, result.x1);
  const vol2 = getBoxVolume(l, w, result.x2);

  let ideal_h = 0;
  let max_vol = 0;

  // check for max
  if (vol1 > vol2) {
    ideal_h = result.x1;
    max_vol = vol1;
  } else {
    ideal_h = result.x2;
    max_vol = vol2;
  }

  return {
    ideal_h,
    max_vol
  } 
}

const WIDTH_1 = 20;
const WIDTH_2 = 30;

console.log(findMaxVol(WIDTH_1, WIDTH_2))

// {
//   ideal_h: 3.9237478148923493,
//   max_vol: 1056.30589546119
// }