Каков «лучший» порядок для списка товаров, чтобы минимизировать функцию стоимости, которая зависит от их заказа?

Question

Я пытаюсь спланировать работу с приседаниями / отжиманиями и т. Д. c. Каждое упражнение утомляет мышечную группу на «х». После утомления мышцы эта мышца восстанавливается (для простоты линейно) со скоростью «г» в секунду.

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

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

Answer 1

Если мы говорим о 14 упражнениях, лучшим вариантом, вероятно, будет использование метода branch и bound . Давайте go рекурсивно пройдемся по всем перестановкам. Если наш текущий максимум больше оценки верхней границы, которую мы имели прежде, мы не должны продолжать эту перестановку, потому что она гарантированно будет хуже. Если мы вычислили одну полную перестановку, мы должны обновить верхнюю границу. Общее количество штатов равно
14! = 8e10, но значительное их количество будет отключено.

Это также помогает иметь приличное жадное решение для использования в качестве начальной оценки.

Я также почти уверен, что полиномиального решения не существует, потому что функция, которую мы пытаемся оптимизировать, слишком сложно.