Задача выбора оптимальной последовательности действий

[Muha_]

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

Собственно задача:
В электрической схеме (города) нужно выполнить $N$ указанных действий с выключателями (включить или отключить). Действий может быть быть 5, 10, изредка больше, например 15.
Для каждого действия можно вычислить признак допустимости или штрафную функцию (для допустимых), которые зависят от действия и текущего состояния схемы, которое, в свою очередь, определятся совокупностью предыдущих выполненных действий (полученное текущее состояние не завит от того, в какой последовательности выполнялись действия).
Задача - выбрать последовательность, включающую все $N$ действий, которая была бы допустима и имела минимальную суммарную штрафную функцию.

Дополнительные пояснения:

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

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

Текущее мое решение: рекурсивный перебор всех возможных перестановок с остановкой расчета, если потребовалось слишком много времени.
Варианты улучшения:
Должна существовать лучшая последовательность перебора вариантов, чем рекурсивный перебор всех перестановок $N!$, т.к. в одно и то же состояние схемы можно прийти разными путями, но дальше достаточно найти оптимальный вариант выполнения оставшихся для этого состояния действий только один раз. Может так получится $2^N$ вместо $N!$.
Кроме того, можно ввести некий элемент случайности в последовательность перебора вариантов (пока не представляю как).
Можно применить метод ветвей и границ, отсекая варианты, штраф для которых хуже, чем уже один из найденных окончательных вариантов.
Можно использовать генетический алгоритм, но это сложно и он может не уложиться в несколько тысяч расчетов штрафной функции.

Спасибо.

[iifat]

Что-то в настолько общем случае, совершенно безосновательно чует моё сердце, никакого эффективного решения нет и быть не может. Возможно, вам стоит посмотреть Липский, Комбинаторика для программистов — там описан способ перебора перестановок парными перестановками, что может (а может и не) сократить общее количество подсчётов штрафной функции.

[Muha_]

Спасибо. Про парные перестановки так сразу в книге не нашел. Надо изучать.

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

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

Здесь ощущение, что я изобретаю велосипед.

PS: по снижению числа вычислений, оказалось что мой велосипед называется Held–Karp algorithm для задачи Коммивояжера. Уже легче. Возможно так же подойдет и какой-то эвристический метод от задачи Коммивояжера.

[iifat]

Muha_ в сообщении #1349246 писал(а):

Про парные перестановки так сразу в книге не нашел

На всякий случай: 1,4 Генерирование перестановок, алгоритм 1,11