Вот еще раз.
N точек связанные оптическими каналами с задержками пропорциональными длинам участков.
Если подать световой сигнал на любую входную точку, то на всех N-1 выходных точках, можно получить N-1 быстрейших сигналов (по переднему фронту) и cтолько же длиннейших (по заднему фронту). Промежуточные теряем, и черт с ними. Наибольший из N вариантов отыскивается элементарно.

Построить полный путь для максимального по времени сигнала двоичным поиском с временем log(N-1) - дело техники, но нас интересует кратчайший через все точки.
С учетом замечания Лукомора, этот искомый путь будет либо длиннее бОльшего запретного, либо меньше его. Все запретные пути короче минимум на 1 точку. Короче не по длине, а по количеству точек.

Тогда удаляем из TSP схемы по одной точке и находим сначала N конечных точек с максимиальным временем, а затем N максимальных маршрутов в N укороченных на точку схемах. Как выше написано, эта тривиальная процедура займет
N+Nlog(N-1) тактов.

А теперь возвращаем точку N-1 способами в найденный максимальный путь и повторяем N раз для всех их, за время N(N-1). В полном пути сигнал пройдет с единственным временем, которое будет либо меньше либо больше максимального запретного.

И, наконец. осталось найти в этом списке кратчайший путь двоичным поиском за logN

Отредактировано Шарпер (2018-09-11 16:17:59)

Мы же максимальные ищем на укороченных на точку картах, как разрешенные и строим для них пути

Свою долю отдай Доктору. Он принадлежит моему клану и я должен блюсти его интерес. 

И что неправильно? Провеотье дейьвия с логарифмами штоле. я не помню наверняка.

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

Не. Без квантов он меня послал далеко...

Какие св-ва есть у минимального пути с пропущенной точкой? Ьо, что это единственный минимальный мусорный для полного пути с возвращенной точкой - возврат точки в карту не даст ни олного мусорного, а только разрешенные. В них будет кратчаший искомый?