Ответ 1
Если вы проверите Conway Game of Life, вы обнаружите, что есть много общего с проблемой расы.
Вот аналогия:
- Начальное состояние (семя системы):
- Игра жизни: начальный шаблон на сетке. Каждая ячейка имеет следующие параметры:
- координата x и y
- ли живая или мертвая ячейка
- Задача расы: n машин, каждый из которых имеет заданные параметры и длину дорожки l. Каждый автомобиль имеет следующие параметры:
- максимальная скорость
- ускорение
- коэффициент обработки
- позиция на треке
- текущая скорость
- Игра жизни: начальный шаблон на сетке. Каждая ячейка имеет следующие параметры:
- Правила применяются в дискретных моментах, которые называются тиками.
- Игра жизни: правила применяются одновременно к каждой ячейке предыдущего поколения, производящему следующее поколение. Каждое поколение является чистой функцией предыдущего.
- Задача расы: правила применяются одновременно к каждому автомобилю из предыдущего состояния, производя следующее состояние. Это происходит каждые 2 секунды. То же, что и в Game of Life, каждый шаг является чистой функцией предыдущего, что означает, что он зависит только от параметров автомобилей от предыдущего состояния.
В отличие от того, что Игра Жизни никогда не заканчивается, тогда как Задача Раса должна заканчиваться, когда текущая позиция каждого автомобиля больше или равна длине дорожки l (Хотя последнее утверждение является спорным: из-за фактора обработки это возможно что в некоторых условиях некоторые машины никогда не достигнут финишной черты).
Ключевым моментом является то, что вычисления выполняются в дискретные моменты, которые отвечают на ваш вопрос:
Но как я могу выяснить, в каком экземпляре я должен выполнить вычисления?
Вы можете воспользоваться этой идеей из раздела Algorithms, чтобы решить эту проблему. Вы должны иметь 2 массива автомобилей: один из которых представляет текущее состояние, а другой - следующий шаг. На каждой итерации вы пересчитываете текущее положение и скорость каждого автомобиля, следуя правилам задания, и проверяете, должен ли цикл прекращаться. Перед следующей итерацией вы меняете роли массива так, чтобы массив преемников в последней итерации становился текущим массивом в следующей итерации.
Псевдокод высокого уровня может выглядеть следующим образом:
n = ..; // initial number of cars
l = ..; // track length
Car[] currentState = initializeState(n, l);
Car[] nextState = clone(currentState);
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
calculateNextState(currentState, nextState, iteration);
swap(currentState, nextState);
if (shouldTerminate(currentState, l) {
break;
}
}
printResultOrClaimNotTerminated(currentState);
Правила применяются в функции calculateNextState (..). В самой наивной реализации вы проверяете каждую пару автомобилей, которые дают вам
O (C(n, 2)) = O (n * (n - 1) / 2) = O (n ^ 2)
сложность для каждой итерации. Однако вы можете подумать о возможных оптимизациях здесь. Например, вы можете сначала отсортировать автомобили по текущему положению (O (n * log(n))), а затем пройти сортированный массив, проверяющий только соседние автомобили (O (2 * n)). Вы можете это сделать, поскольку, если 10-метровое состояние не удовлетворяет для соседних автомобилей, оно не будет удовлетворять для несмежных автомобилей. Это даст вам сложность:
O (n * log(n))
что намного лучше. Сортированный массив автомобилей, естественно, даст вам автомобиль с последней позицией, к которой вам нужно применить правило нитроучета. Возможно, возможны и другие оптимизации. Это отвечает на ваш вопрос:
Для каждого экземпляра я должен проверять все комбинации C (n, 2) каждой пары драйверов и вычислять результат?