[pva]

Можно попробовать решить обратную задачу. Т.е. найти минимальный остов. http://ru.wikipedia.org/wiki/Минимал...стовное_дерево Дерево Штайнера. http://book.itep.ru/3/stain_tree.htm »

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

Код:

+---------+
|         |
|         |
|         |
|         |
+-..      |
+--+.     |
|  |.     |
|  ||     |
+--++-----+

а допустимо такое:

Код:

+--+------+
|  |      |
|  |      |
|  |      |
|  |      |
+-..      |
+---.     |
|   .     |
|   |     |
+---+-----+

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

подумав-подумав допёрло как можно сделать. Нужно использовать принцип максимума понтрягина
. Пронумеруем контакты в любом порядке и начинаем поочереди их перебирать. За текущее состояние процесса принимаем направление обработанных дорожек + оставшиеся возможные направления необработанных (для каждого направления есть своя цена). Так как требуется найти интегральную цену (разделяемая на части сумма), этим принципом пользоваться можно.
Допустим мы уже сделали несколько ходов и у нас есть список возможных направлений для оставшихся дорожек. Тогда наши последовательные ходы должны быть такими, чтобы обеспечить наименьшее значение интеграла (суммарной цены). Мысленно доводим решение задачи до конца и начинаем раскручивать её обратно. На каждом шаге для контакта N (0<=N<=max(N)) и возможного направления I (0<=I<4) запоминаем рассчитываем наименьшую длину и запоминаем соответсвующую ей распайку контактов. Рассчёт ведётся из соображений, что сначала ни один контакт (из изначально не заблокированных) не заблокирован, потом что идеальный контакт заблокирован, потом что из оставшихся идеальный заблокирован и т.д.
На следующем шаге берём за основу полученные (максимум) 4 состояния, и рассчитываем схему с добавленным контактом. Итого потребуется вычислить (max(N)+1)*4 (возможно недоделанных) схем.