Оптимизация перебора
Здравствуйте всем.
Существует такая задача:
есть путь протяженностью S км. Средняя скорость прохождения этого пути должна быть V км/ч. При этом путь разбивается на N участков с эквивалентным уклоном. Для каждого участка существует минимальная Vi_min и максимальная Vi_max скорость прохождения.
Задача:
найти все возможные значения Vi, где Vi_min <= Vi <= Vi_max, при которых средняя скорость прохождения всего пути равна V. Далее нужно выбрать решение, обеспечивающее минимальный расход энергии на прохождение пути.
Проблема:
возьмем N = 20, V = 40 км/ч. Для простоты возьмем все Vi_min = 2 км/ч, все Vi_max = 90 км/ч. Шаг, с которым будем перебирать возможные значения скорости, возьмем 1 км/ч. Тогда нужно перебрать около 89 в 20й степени значений! Если это делать простым перебором, то можно ждать решения до скончания веков.
Вопрос:
как можно оптимизировать этот процесс?
Существует такая задача:
есть путь протяженностью S км. Средняя скорость прохождения этого пути должна быть V км/ч. При этом путь разбивается на N участков с эквивалентным уклоном. Для каждого участка существует минимальная Vi_min и максимальная Vi_max скорость прохождения.
Задача:
найти все возможные значения Vi, где Vi_min <= Vi <= Vi_max, при которых средняя скорость прохождения всего пути равна V. Далее нужно выбрать решение, обеспечивающее минимальный расход энергии на прохождение пути.
Проблема:
возьмем N = 20, V = 40 км/ч. Для простоты возьмем все Vi_min = 2 км/ч, все Vi_max = 90 км/ч. Шаг, с которым будем перебирать возможные значения скорости, возьмем 1 км/ч. Тогда нужно перебрать около 89 в 20й степени значений! Если это делать простым перебором, то можно ждать решения до скончания веков.
Вопрос:
как можно оптимизировать этот процесс?
Можно поподробнее:
1. "с эквивалентным уклоном" -- к чему в задаче этот уклон?
2. "обеспечивающее минимальный расход энергии" -- какой критерий минимума расхода энергии?
1. "с эквивалентным уклоном" -- к чему в задаче этот уклон?
2. "обеспечивающее минимальный расход энергии" -- какой критерий минимума расхода энергии?
Эта задача, ИМХО, схожа с поиском счастливых билетов в рулоне. Такие задачи можно решить методом приближенной оценки. Нужно запастись книгами по высшей математике и по разработке и анализу алгоритмов.
А я считаю, что нужно тут построить начальное базовое решение, которое будет отвечать критерию энергетической эффективности.
Далее использовать итерационный алгоритм, с помощью которого подведем это решение к критерию средней скорости...
Но этот метод даст нехудшее решение, тогда как в задаче нужно найти всевозможные комбинации скоростей...
Далее использовать итерационный алгоритм, с помощью которого подведем это решение к критерию средней скорости...
Но этот метод даст нехудшее решение, тогда как в задаче нужно найти всевозможные комбинации скоростей...