Обзор

Хотя вы явно отметили evolutionary-algorithm, я бы посоветовал вам взглянуть на набор алгоритмов, обобщенных под названием Приближенное динамическое программирование (ADP). На мой взгляд, хорошей вводной книгой является книга Уоррена Б. Пауэлла. Он содержит множество таких задач распределения ресурсов, а также несколько других практически важных вещей, которые часто называют оптимальным управлением (пример: управление автотранспортной компанией, имеющей несколько тысяч грузовиков).

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

Одним из ключей к применению АДП является правильное математическое моделирование данной проблемы. Центральное значение имеет state системы, actions, которые можно принять в заданном состоянии, а также cost, которые требуются для этих действий и которые нужно минимизировать — ваши затраты здесь определяются продолжительностью теста. После построения подходящей модели задача состоит в том, чтобы (приблизительно) решить уравнение Беллмана, для которого существует несколько алгоритмов.

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

Моделирование состояния одной батареи

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

• Одно состояние: Как вы написали, одна батарея определяется состоянием

  S = {SoC, Relax}      where SoC   \in {UNKNOWN, 0%, 25%, 50%, 75%, 100%}
                        and   Relax \in {UNKNOWN, 0m, 5m, 15m, 30m, 1h, 2h, 6h, 24h}
  

  Я добавил 0% и 0m для удобства, хотя здесь они, возможно, и не нужны.

  Обратите внимание, что здесь я уже сделал большое упрощение, так как, например, состояние заряда также может быть 79%. Предположение, которое оправдывает это, следующее: как только вы начинаете свой эксперимент в первый раз (или также заново через долгое время), все батареи разумно находятся в состоянии {UNKNOWN,UNKNOWN}. Тогда, согласно вашему описанию, первое, что нужно сделать, это сделать полную перезарядку, которая устанавливает все в состояние {100%,0m} (и которая стоит 2,5h). Отсюда выполняются только квалифицированные изменения состояния — разрядка выполняется только для определенных SoC, а перезарядка — только для 100% (это я предположил на основании вашего описания). Обратите внимание, что это становится сложнее в более естественной стохастической структуре, где, например, батарея SoC ведет себя не так хорошо.

• Действия и затраты: для конкретных состояний с одной батареей связан набор возможных действий (плюс соответствующие затраты). Соберем их в следующем:

  State                  Possible Actions                       Cost
  -------------------------------------------------------------------------------
  {UNKNOWN, Relax}  ->   RECHARGE TO {100%,0m}                  2,5h
  
  {SoC, 0m}         ->   RELAX TO {SoC,5m},                     5m          
  
  {SoC, Relax}      ->   RECHARGE TO {100%,0m},                 2,5h           
                         DISCARGE TO {SoC-1},                   C(SoC, SoC-1)
                         DISCHARGE-MEASURE TO {SoC-1},          C(SoC, SoC-1)
                         RELAX TO {SoC, RELAX+1}                C(Relax, Relax+1)
  
  {SoC, UNKNOWN}    ->   RECHARGE TO {100%,0m},                 2,5h
                         DISCARGE TO {SOC-1,0m},                C(SoC,SoC-1)   
                         RELAX {SoC, 24h}                       24h
  

  SoC-1 здесь означает следующее возможное состояние, тогда как C(SoC, SoC-1) означает «время перехода от SoC к SoC-1, например, с 75% до 50%. Теперь ваша очередь проверить эту таблицу, соответствует ли она вашей модели. Если нет, у вас есть исправить или расширить его.

  Обратите внимание, что я снова сделал упрощение, разрешив только переходы в следующее возможное состояние SoC-1 (например, с 75% до 50%). Это разумно, так как стоимость считается дополнительной. Например, переход от 75 % к 25 % занимает столько же времени, сколько переход сначала к 50 %, а затем к 25 %.

  Кроме того, все действия RECHARGE и DISCHARGE осуществимы только в рабочие часы, которые не учитывались в приведенной выше таблице (но должны быть включены в модель позже).

Объедините вышеперечисленное в модель полной системы

Теперь предположим, что у вас есть батареи N, зарядные устройства M и разрядники K (где мы можем предположить M<=N и K<=N), все они идентичны. Далее, допустим, цель состоит в том, чтобы выполнить каждый тест только один раз.

• Состояние теста. Состояние теста Test представляет собой вектор размерности 4*7 из 0 и 1, содержащий информацию о том, был ли уже выполнен конкретный тест. Обратите внимание, что это соответствует 2^28 возможным состояниям, поэтому здесь определенно нужно ввести приближение.

• Состояние нескольких батарей. Суммарное состояние всех батарей B является декартовым произведением состояния одной батареи, т. е. находится в пространстве {SoC,Relax}^N. Это просто означает, что нужно учитывать N состояния одной батареи.

  B={SoC_1, Relax_1}, ..., {SoC_N, Relax_N}
  

  Опять же, размер этого пространства будет очень большим для средних чисел N.

• Время работы. Кроме того, нам нужно указать время суток T. Делая это точно, мы получаем 24*60m / 5m = 288 возможных пятиминутных слотов.

• Многобатарейные действия. Точно так же многобатарейные действия задаются N-мерным декартовым произведением одномерных действий. RECHARGE и DISCHARGE возможно только для T в рабочее время и при наличии достаточного количества Re- и Dischargers (сумма всех RECHARGE/ DISCHARGE не должна превышать M/K).

Подводя итог, полное состояние S задается комбинацией

S = {Test, T, B}

Размерность пространства состояний составляет около 2^28 * (6*9)^N * 288, что быстро становится огромным.

Далее, для каждого состояния есть соответствующий набор разрешенных действий, который уже должен быть ясен.

Итак, теперь, когда модель системы более или менее определена (исправьте ее, если нужно!), мы можем продолжить ее решение.

Уравнение Беллмана

Уравнение Беллмана является центральным уравнением (приближенного) динамического программирования. В качестве хорошего введения взгляните на книгу Саттона и Барто, которая находится в свободном доступе в сети.

Идея довольно проста: для каждого возможного состояния введите функцию значения V(S), которая говорит вам, насколько хорошо находиться в состоянии S. Эта функция значения в принципе содержит время, необходимое для завершения тестов, когда вы находитесь в состоянии S. В Чтобы определить это значение для задачи с конечным горизонтом, как она есть, нужно начинать с конечного состояния и возвращаться к началу, то есть, по крайней мере, если это позволяет размер задачи. Но давайте сделаем это схематично в следующем и посмотрим:

Конечное состояние — это состояние, в котором Test содержит только единицы, т. е. все 28 проверки выполнены. Установите V(S)=0 для всех этих состояний (независимо от T и состояния нескольких батарей), так как вам больше не нужно время.

Шаг назад. Теперь рассмотрим все состояния, в которых Test содержит только 27 единиц и один ноль, т. е. еще нужно выполнить один тест. Для каждого возможного состояния нескольких батарей B и момента времени T можно автоматически определить самую быструю альтернативу. Установите V(S) равным этой стоимости.

Еще один шаг назад. Далее рассматриваются все состояния, в которых Test содержит только 26 единиц и два нуля (предстоит провести еще два теста). Теперь для каждого возможного состояния B с несколькими батареями и момента времени T выбирают действие a таким образом, чтобы минимизировать стоимость действия плюс значение состояния, к которому приводит действие. С точки зрения, вы должны выбрать a так, чтобы минимизировать C(a) + V(S'), где a ведет от S к S'. Если вы нашли это действие, установите состояние равным V(S) = C(a) + V(S').

И так далее. Это делается для всех возможных состояний и сохраняется каждое оптимальное значение V(S), полученное таким образом - для небольшого количества батарей N это может быть даже осуществимо на практике.

Как только вы будете готовы к этому, вы получите оптимальное действие в каждом состоянии. Для этого, если кто-то находится в состоянии S, он следует тому же рецепту, что и выше, и всегда выбирает действие a, которое минимизирует C(a) + V(S'). Это также можно сделать только один раз, когда сохраняется лучшее действие для каждого состояния.

И тогда все готово — вы полностью решили свою проблему. Или скажем, по крайней мере теоретически, потому что на практике размер задачи требует слишком много усилий и памяти, чтобы выполнить вышеупомянутую обратную рекурсию и сохранить ее в таблице (для задачи, как указано выше, я бы сказал, что этот режим начинается, когда N~3 и больше ). Поэтому необходимо ввести приближения.

приближения

При использовании приближений обычно жертвуют «оптимальным решением» в пользу «хорошо работающего решения». Поскольку это можно сделать несколькими способами, именно здесь начинается искусство. Или, цитируя Пауэлла, глава 15.7: «Успешный алгоритм ADP для важного класса задач, по нашему мнению, является патентоспособным изобретением». В связи с этим я только набросаю некоторые возможные шаги, которые можно сделать здесь.

• Один класс методов аппроксимации, называемый агрегированием, использует упрощенную модель переменной состояния. Например, вместо того, чтобы включать время T в 5m фрагментах в переменной состояния (288 состояний), можно использовать 1h фрагментов или даже логическое значение, указывающее, является ли это рабочим временем. Или вы можете использовать 5m чанков только в рабочее время плюс одно состояние вне рабочего времени. И так далее... масса возможностей. Здесь всегда получается меньшее табличное представление

• Другой класс методов аппроксимации использует параметризованное представление функции ценности, например модель линейной регрессии или нейронную сеть. В приведенной выше итерационной схеме функции значений не хранятся в таблице, а скорее используются в качестве входных данных для подбора параметров. Это заменяет часто огромное табличное представление гораздо меньшим количеством параметров, но недостатком является то, что процедура подбора обычно является более сложной. (Обратите внимание, что на этом этапе естественно могут применяться эволюционные алгоритмы).

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

• Далее, вместо того, чтобы пытаться выполнить полную итерацию по всем состояниям, можно использовать методы Монте-Карло для случайного исследования многих, но не всех возможных состояний. Это тем эффективнее, чем лучше существуют эвристики, которые позволяют алгоритму исследовать значимые состояния.

Другие идеи, а также их практическое применение можно найти в упомянутых выше книгах.

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

Поскольку это StackOverflow, и поскольку вы собираетесь потратить fkn 500 своих с трудом заработанных баллов, и поскольку я сам очень заинтересован в этом, я написал вам пример кода, который реализует рецепт, который я представил несколько дней назад. Хотя это игрушечная модель, которая там решается, она содержит большинство вопросов вашей исходной проблемы и — при наличии достаточной мощности компьютера — может быть легко расширена для решения последней.

Модельная проблема

Рассмотрим следующую модельную задачу:

• N=2 аккумуляторы, M=2 зарядные устройства, K=1 разрядник.

• Время T продолжается кратно 6 часам: 0:00, 6:00, 12:00, 18:00. Часы работы все кроме 0:00 ночи.

• Состояния батареи:

  • SoC in {0%,50%,100%}
  • Relax in {0h,6h,12h,18h,24h}

  Аккумуляторы изначально находятся в состоянии {0%,0h}, т.е. незаряжены на момент начала проведения теста (Расслабление не имеет значения, так как все равно сначала нужно подзарядить).

• Доступные действия:

  • RELAX: do nothing. Increases Relax by 6 hours.
  • RECHARGE: увеличивает SoC до следующего состояния и устанавливает Relax в 0h.
  • MEASURE: уменьшает SoC до предыдущего состояния, а также устанавливает Relax в 0h.

  Каждое действие «стоит» 6 часов.

  Обратите внимание, что MEASURE ведет себя почти так же, как то, что вы назвали DISCHARGE. В частности, если ИЗМЕРЕНИЕ применяется к состоянию батареи, которое не является тестовым случаем, это просто РАЗРЯДКА. Однако, и это единственная разница, когда MEASURE применяется к одному из тестовых случаев, также обновляется состояние Test.

• Батареи необходимо измерять один раз для каждого состояния {SoC,Relax} в {{50%,6h},{100%,6h},{50%,24h},{100%,24h}}. Таким образом, получается вектор Test размерности четыре, содержащий либо нули, либо единицы.

Как только вы ознакомитесь с приведенной ниже реализацией, вы сможете легко изменить все эти варианты.

Описание модели

Я собираюсь использовать описание системы, представленное в моем предыдущем ответе. В частности, состояние системы задается многовекторностью

{Test, T, {SoC_1,Relax_1}, {SoC_2,Relax_2}}

На самом деле это не лучшая переменная состояния (переменная состояния всегда должна быть максимально компактной). Например, не учитывается симметрия аккумуляторов. В «жестких» моделях подобных проблем следует избегать, когда это возможно.

Кроме того, я упростил ситуацию, предположив, что все происходит с временными интервалами в 6 часов. При этом можно просто увеличивать переменную T на 6 часов после каждого действия. Если бы были действия продолжительностью, скажем, 12 часов, нужно было бы добавить дополнительные переменные к переменной состояния, которые указывают, заблокирована ли батарея и когда она снова будет доступна. Не говоря уже о том, что была бы акция, которая длилась, например, 5 часов. Итак, вы видите, что время рассматривается здесь довольно просто.

Реализация

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

• Во-первых, что касается основных элементов: более элементарные задаются enums, например

  enum struct StateOfCharge
  {
      P0=0,
      P50,
      P100,
      END_OF_LIST
  };
  

  Целые числа тоже сработали бы хорошо, но я полагаю, что с перечислениями становится легче читать. Для этих перечислений я также предоставил operator<< для вывода на экран, а также operator++ и operator-- для увеличения/уменьшения состояния. Два последних оператора являются шаблонами функций, принимающими любое перечисление (по крайней мере, если оно содержит состояние END_OF_LIST).

• Более продвинутые элементы, такие как состояния и действия, являются классами. В частности, класс State содержит много логики: он может определить, разрешено ли данное действие через его член.

  bool isActionAllowed(Action const&) const
  

  Кроме того, он может дать вам следующее состояние для данного действия через

  State nextState(Action const&) const
  

  Эти функции занимают центральное место в итерации значений, описываемой далее.

• Есть класс BatteryCharger, выполняющий реальный алгоритм динамического программирования. Он содержит контейнер std::map<State,int> для хранения значения данного состояния (помните, что значение здесь — это просто время, необходимое для завершения, которое, естественно, должно быть сведено к минимуму). Для того, чтобы map работало, также есть operator<, сравнивающий две переменные State.

• Наконец, несколько слов о схеме Итерация ценности. В ответе выше я написал, что это можно сделать с помощью обратной итерации. Это верно, но это может стать довольно сложным, потому что вам нужно найти обратный путь, чтобы были покрыты все возможные состояния (и в лучшем случае только один раз). Хотя это было бы возможно здесь, можно также просто перебирать все состояния произвольным образом. Однако это необходимо делать итеративно, потому что в противном случае вы будете использовать значения состояния, которые вы еще не оптимизировали. Итерация здесь заканчивается, когда все значения сходятся.

  Дополнительную информацию об итерации значения см. в книге Саттона и Барто.

#include<iostream>
#include<array>
#include<map>
#include<type_traits>
#include<algorithm>

template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type>
bool isLast(T const& t)
{
    return t == static_cast<T>(static_cast<int>(T::END_OF_LIST) - 1);
}

template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type>
bool isFirst(T const& t)
{
    return t == static_cast<T>(0);
}



template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type>
T& operator++(T& t)
{
    if (static_cast<int>(t) < static_cast<int>(T::END_OF_LIST) - 1)
    {
        t = static_cast<T>(static_cast<int>(t)+1);
    }
    return t;
}

template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type>
T operator++(T& t, int)
{
    auto ret = t;
    ++t;
    return ret; 
}


template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type>
T& operator--(T& t)
{
    if (static_cast<int>(t) > 0)
    {
        t = static_cast<T>(static_cast<int>(t)-1);
    }
    return t;
}


template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type>
T operator--(T& t, int)
{
    auto ret = t;
    --t;
    return ret;
}



const int Nbattery = 2;
const int Nrecharger = 2;
const int Ndischarger = 1;
const int Ntest = 4;

enum struct StateOfCharge
{
    P0=0,
    P50,
    P100,
    END_OF_LIST
};

//screen output
std::ostream& operator<<(std::ostream& os, StateOfCharge const& s)
{
    if(s==StateOfCharge::P0) os << "P0";
    else if (s==StateOfCharge::P50) os << "P50";
    else if (s == StateOfCharge::P100) os << "P100";
    return os;
}


enum struct StateOfRelax
{
    H0=0,
    H6,
    H12,
    H18,
    H24,
    END_OF_LIST
};

//screen output
std::ostream& operator<<(std::ostream& os, StateOfRelax const& s)
{
    if(s==StateOfRelax::H0) os << "H0";
    else if (s == StateOfRelax::H6) os << "H6";
    else if (s == StateOfRelax::H12) os << "H12";
    else if (s == StateOfRelax::H18) os << "H18";
    else if (s == StateOfRelax::H24) os << "H24";
    return os;
}


struct SingleBatteryState
{
    //initialize battery as unfilled
    StateOfCharge SoC;
    StateOfRelax Relax;
    SingleBatteryState(StateOfCharge _SoC = static_cast<StateOfCharge>(0), StateOfRelax _Relax = static_cast<StateOfRelax>(0))
        : SoC(_SoC)
        , Relax(_Relax)
    {}


    //loop over state
    bool increase()
    {
        //try to increase Relax
        if (!isLast(Relax))
        {
            ++Relax;
            return true;
        }
        //if not possible, reset Relax
        else if (!isLast(SoC))
        {
            ++SoC;
            Relax = static_cast<StateOfRelax>(0);
            return true;
        }

        //no increment possible: reset and return false
        SoC = static_cast<StateOfCharge>(0);
        Relax = static_cast<StateOfRelax>(0);
        return false;
    }
};

std::ostream& operator<<(std::ostream& os, SingleBatteryState const& s)
{
    os << "("<<s.SoC << "," << s.Relax << ")";
    return os;
}


bool operator<(SingleBatteryState const& s1, SingleBatteryState const& s2)
{
    return std::tie(s1.SoC, s1.Relax) < std::tie(s2.SoC, s2.Relax);
}

bool operator==(SingleBatteryState const& s1, SingleBatteryState const& s2)
{
    return std::tie(s1.SoC, s1.Relax) == std::tie(s2.SoC, s2.Relax);
}

//here specify which cases you want to have tested
std::array<SingleBatteryState, Ntest> TestCases = { SingleBatteryState{ StateOfCharge::P50, StateOfRelax::H6 }
                                                  , SingleBatteryState{ StateOfCharge::P50, StateOfRelax::H24 }
                                                  , SingleBatteryState{ StateOfCharge::P100, StateOfRelax::H6 }
                                                  , SingleBatteryState{ StateOfCharge::P100, StateOfRelax::H24 } };


// for a state s (and action MEASURE), return the entry in the array Test
// which has to be set to true
int getTestState(SingleBatteryState const& s)
{
    auto it = std::find(std::begin(TestCases), std::end(TestCases), s);

    if(it==std::end(TestCases))
        return -1;
    else
        return it - std::begin(TestCases);
}


enum struct SingleAction
{
    RELAX = 0,
    RECHARGE,
    MEASURE,
    END_OF_LIST
};

std::ostream& operator<<(std::ostream& os, SingleAction const& a)
{
    if(a== SingleAction::RELAX) os << "RELAX";
    else if (a == SingleAction::RECHARGE) os << "RECHARGE";
    else if (a == SingleAction::MEASURE) os << "MEASURE";

    return os;
}


enum struct TimeOfDay
{
    H0 = 0,
    H6,
    H12,
    H18,
    END_OF_LIST
};


//here set office times
std::array<TimeOfDay,3> OfficeTime = {TimeOfDay::H6, TimeOfDay::H12, TimeOfDay::H18};

bool isOfficeTime(TimeOfDay t)
{
    return std::find(std::begin(OfficeTime), std::end(OfficeTime),t) != std::end(OfficeTime);
}

//screen output
std::ostream& operator<<(std::ostream& os, TimeOfDay const& s)
{

    if(s==TimeOfDay::H0) os << "0:00 h";
    else if (s == TimeOfDay::H6) os << "6:00 h";
    else if (s == TimeOfDay::H12) os << "12:00 h";
    else if (s == TimeOfDay::H18) os << "18:00 h";
    return os;
}


struct Action
{
    SingleAction& operator[](int i) { return A[i]; }
    SingleAction const& operator[](int i) const { return A[i]; }

    std::array<SingleAction, Nbattery> A{};

    bool increase()
    {
        for (int i = Nbattery - 1; i >= 0; --i)
        {
            if (!isLast(A[i]))
            {
                ++A[i];
                return true;
            }
            else
            {
                A[i] = static_cast<SingleAction>(0);
            }       
        }
        return false;
    }
};


//screen output
std::ostream& operator<<(std::ostream& os, Action const& A)
{
    os << "(";
    for (int i = 0; i < Nbattery-1 ; ++i)
    {
        os << A[i] << ",";
    }
    os << A[Nbattery-1] << ")";

    return os;
}



struct State
{
    std::array<bool, Ntest> Test{};
    TimeOfDay T = TimeOfDay::H0;
    std::array<SingleBatteryState, Nbattery> B{};

    State()
    {
        for (int i = 0; i < Ntest; ++i)
        {
            Test[i] = true;
        }
    }

    bool isSingleActionAllowed(SingleAction const& a) const
    {
        if ( !isOfficeTime(T) &&  a != SingleAction::RELAX)
        {
            return false;
        }

        return true;
    }

    bool isActionAllowed(Action const& A) const
    {
        //check whether single action is allowed
        for (int i = 0; i < Nbattery; ++i)
        {
            if (!isSingleActionAllowed(A[i]))
                return false;
        }

        //check whether enough Rechargers and Dischargers are available
        int re = 0;
        int dis = 0;

        for (int i = 0; i < Nbattery; ++i)
        {
            //increase re counter
            if (A[i] == SingleAction::RECHARGE)
            {
                ++re;
            }
            //increase dis counter
            else if (A[i] == SingleAction::MEASURE)
            {
                ++dis;
            }

            //check whether ressources are exceeded
            if (re>Nrecharger || dis > Ndischarger)
            {
                return false;
            }
        }

        return true;
    }

    //loop over state
    bool increase()
    {
        //increase time
        if (!isLast(T))
        {
            ++T;
            return true;
        }
        else
        {
            T = static_cast<TimeOfDay>(0);
        }

        //if not possible, try to increase single battery states
        for (int i = Nbattery-1; i >= 0; --i)
        {
            if (B[i].increase())
            {
                return true;
            }
        }

        //if also not possible, try to increase Test state
        for (int i = Ntest-1; i >=0; --i)
        {
            if (Test[i])
            {
                Test[i] = false;
                return true;
            }
            else
            {
                Test[i] = true;
            }
        }

        return false;
    }


    // given a single action and a single-battery state, calculate the new single-battery state.
    // it is assumed the action is allowed
    SingleBatteryState newState(SingleBatteryState s, SingleAction const& a) const
    {
        if (a == SingleAction::RELAX)
        {
            ++s.Relax;
        }
        else if (a == SingleAction::RECHARGE)
        {
            ++s.SoC;
            s.Relax = static_cast<StateOfRelax>(0);
        }
        else if (a == SingleAction::MEASURE)
        {
            --s.SoC;
            s.Relax = static_cast<StateOfRelax>(0);
        }
        return s;
    }

    // calculate new complete state while assuming the action s allowed
    State newState(Action const& a) const
    {
        State ret = *this;

        //increase time
        if (isLast(ret.T))
        {
            ret.T = static_cast<TimeOfDay>(0);
        }
        else
        {
            ret.T++;
        }

        //apply single-battery action
        for (int i = 0; i < Nbattery; ++i)
        {
            ret.B[i] = newState(B[i], a[i]);

            // if measurement is performed, set new Test state.
            // measurement is only possible if Soc=50% or 100%
            // and Relax= 6h or 24h
            if (a[i] == SingleAction::MEASURE
                && getTestState(B[i]) != -1)
            {
                ret.Test[getTestState(B[i])] = true;
            }
        }
        return ret;
    }

    int cost(Action const& a) const
    {
        if (std::find(std::begin(Test), std::end(Test), false) == std::end(Test))
        {
            return 0;
        }
        return 1;
    }

};

//screen output
std::ostream& operator<<(std::ostream& os, State const& S)
{
    os << "{(";
    for (int i = 0; i < Ntest-1; ++i)
    {
        os << S.Test[i]<<",";
    }
    os << S.Test[Ntest-1] << "),"<<S.T<<",";

    for (int i = 0; i < Nbattery; ++i)
    {
        os << "(" << S.B[i].SoC << "," << S.B[i].Relax<<")";
    }
    os << "}";

    return os;
}

bool operator<(const State& s1, const State& s2)
{
    return std::tie(s1.Test, s1.T, s1.B) < std::tie(s2.Test, s2.T, s2.B);
}




struct BatteryCharger
{
    bool valueIteration()
    {
        // loop over all states with one specified Test state
        State S;

        int maxDiff=0;
        do
        {
            int prevValue = V.find(S)->second;
            int minCost = prevValue;

            // loop over all actions
            // and determine the one with minimal cost
            Action A;
            do
            {
                if (!S.isActionAllowed(A))
                {
                    continue;
                }

                auto Snew = S.newState(A);
                int newCost = S.cost(A) + V.find(Snew)->second;

                if (newCost < minCost)
                {
                    minCost = newCost;
                }
            }
            while (A.increase());

            V[S] = minCost;

            maxDiff = std::max(maxDiff, std::abs(prevValue - minCost));
        }
        while (S.increase());

        //return true if no changes occur
        return maxDiff!=0;
    }


    void showResults()
    {
        State S;
        do
        {
            auto Aopt = getOptimalAction(S);
            auto Snew = S.newState(Aopt);
            std::cout << S << "   " << Aopt << "   " << Snew << "   " << V[S] << "   " << V.find(Snew)->second << std::endl;
        }
        while (S.increase());
    }

    Action getOptimalAction(State const& S) const
    {
        Action Aopt;

        Action A;
        int minCost = std::numeric_limits<int>::max();
        do
        {
            if (!S.isActionAllowed(A))
            {
                continue;
            }

            auto Snew = S.newState(A);
            int newCost = S.cost(A) + V.find(Snew)->second;

            if (newCost < minCost)
            {
                minCost = newCost;
                Aopt = A;
            }
        }
        while (A.increase());

        return Aopt;
    }

    BatteryCharger()
    {
        State S;
        do
        {
            int ad = 0;
            for (int i = 0; i < Ntest; ++i)
            {
                if (!S.Test[i])
                    ad += 100;
            }
            V[S] = ad;
        }
        while (S.increase());
    }

    std::map<State, int> V;
};





int main(int argc, char* argv[])
{
    BatteryCharger BC;

    int count = 0;
    while (BC.valueIteration())
    {
        ++count;
    };
    std::cout << "Value Iteration converged after " << count << " iterations\n"<<std::endl;

    //start at 6:00 with no tests at all performed
    State S;
    S.Test[0] = false;
    S.Test[1] = false;
    S.Test[2] = false;
    S.Test[3] = false;
    S.T = TimeOfDay::H6;

    //get sequence of optimal actions
    auto Aopt = BC.getOptimalAction(S);
    while (BC.V[S] != 0)
    {
        std::cout << S << "    " << Aopt << "   " << BC.V[S] << std::endl;

        S = S.newState(Aopt);
        Aopt = BC.getOptimalAction(S);
    }
    std::cout << S << "    " << Aopt << "   " << BC.V[S] << std::endl;

    return 0;
}

Вот DEMO, чтобы поиграть.

Результаты

С помощью приведенного выше кода можно получить следующие результаты, напечатанные на экране:

Value Iteration converged after 8 iterations

{(0,0,0,0),6:00 h,(P0,H0)(P0,H0)}    (RELAX,RECHARGE)   10
{(0,0,0,0),12:00 h,(P0,H6)(P50,H0)}    (RECHARGE,RECHARGE)   9
{(0,0,0,0),18:00 h,(P50,H0)(P100,H0)}    (RECHARGE,RELAX)   8
{(0,0,0,0),0:00 h,(P100,H0)(P100,H6)}    (RELAX,RELAX)   7
{(0,0,0,0),6:00 h,(P100,H6)(P100,H12)}    (MEASURE,RELAX)   6
{(0,0,1,0),12:00 h,(P50,H0)(P100,H18)}    (RELAX,RELAX)   5
{(0,0,1,0),18:00 h,(P50,H6)(P100,H24)}    (RELAX,MEASURE)   4
{(0,0,1,1),0:00 h,(P50,H12)(P50,H0)}    (RELAX,RELAX)   3
{(0,0,1,1),6:00 h,(P50,H18)(P50,H6)}    (RELAX,MEASURE)   2
{(1,0,1,1),12:00 h,(P50,H24)(P0,H0)}    (MEASURE,RELAX)   1
{(1,1,1,1),18:00 h,(P0,H0)(P0,H6)}    (RELAX,RELAX)   0

Видно, что итерация значения сходится после 8 итераций. На моем ПК и в Visual Studio в режиме Release это занимает примерно полсекунды. Таким образом, вы можете смело детализировать задачу и все же ожидать возможного точного ответа.

В строках ниже вы видите пример оптимизированного процесса тестирования. Здесь начальное состояние {(0,0,0,0),6:00 h,(P0,H0)(P0,H0)}, т.е. полный тест начинается в 6 утра с неиспользованными батареями (P0 здесь означает 0%, 6:00 h означает 6 утра или немецкое "6:00 Uhr"). Следующий столбец дает вам оптимизированное действие {RELAX,RECHARGE} (которое приводит к состоянию в следующей строке). Число в третьем столбце — это время (в единицах по 6 часов), которое еще требуется для завершения тестов. Для этого примера требуется в общей сложности 60 часов.

Вот и проблема с моделью решена. Чтобы проверить разные начальные состояния (они все оптимизированы!), просто измените следующие строки в main:

//start at 6:00 with no tests at all performed
State S;
S.Test = {false,false,false,false};
S.T = TimeOfDay::H6;

А теперь, получайте удовольствие! В лучшем случае вы сообщите нам, как вы действовали и насколько это было успешно.