Наврал, конечно. Испытание надо произвести N-1 раз для всех точек, а значит сигналов будет (N(N-1)^2)/2 , что кстати, равно кол-ву соединений в матричном варианте. Не знаю как для оптоволокна, а вот бешеное кол-во соединений, учитывая ко-во транзисторов в проце, так ни разу не препятствие- 2 миллиарда еще 10 лет назад было. А на каждом слое матричного представления N*(N-1) соединений по которым сигналы разведены временными задержками

"Бессмыслица — искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос… "(с) К.Хунта

А что это за навязчивая идея перечислять все варианты? У нас искомый путь единственный, причем первый по времени. А (N-1)!-1 более длинных, отсекаются безоговорочно и как только, так сразу.
И на 100% не уверен, но (N-1)^(N-1) по-моему неверна - между слоями точек проходит N(N-1)/2 сигналов, так что, если смотреть по матрице то для N-1 слоя будет всего (N-1)*N(N-1)/2=(N(N-1)^2)/2.
Если ошибаюсь, поправьте, плз, хотя это и не принципиально, поскольку и запрещенные интересуют не асе, а только меньшие нашего искомого. угу. Самый длинный запрещенный должен быть меньше искомого. Это и есить критерий отсева. Для того, чтобы его осуществить, надо найти максимальное время прохождения запрещенного сигнала. Все они пропускают хотя бы одну вершину, поскольку нельзя попасть дважды в одну и ту же не пропустив какой-либо обязательной.

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

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

Отредактировано Шарпер (2018-09-06 13:35:31)

Так по времени же. Они все длиннее кратчайшего.

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

Не-а. Это вопрос к постановке задачи. Зачинатель перечислил все варианты и все мучаются перебором.

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

Метрический вариант задачи. Вот давай сначала для него.

Для метрической задачи выполняется

Вот именно. Так что первый же зарегистрированный выходной сигнал даст решение.

Для метрической задачи отсев запрещенных я тебе показал. Что не так?

Ты меня засомневал и мне придется теперь искать железобетонное решение.

Щас задачу решим и вызовем.

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