На осях, естесно

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

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

Откуда там экспоненциальеое?
1 N-1 испытание на кратчайший вариант
2 Log₂((N-2)!) шагов восстановления от конца к началу

Вопрос, есть ли в п.п. 1 ошибка?

Отредактировано Шарпер (2018-10-19 15:29:47)

Куку, родной! Проверяем пары вход-выход, их N-1 вариант. Мы не строим пути, мы просто определяем откуда вылетит самая быстрая птичка

Это между входом и выходом их столько. На этапе отсевыа пофиг, нам нужен кратчайший между входом и выходом.

Да. И загорается надпись "Слив засчитан".

Точно отсеиваются? И регистрируется полный кратчайший?

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

Что ж получается, что решили коммивояжера?

Отредактировано Шарпер (2018-10-19 20:37:32)

Порешили...

Не мой вопрос

Ну, что ж, давайте тогда решим практически значимую задачу под кодовым названием "диспансеризация". Это своего рода комбинация задач коммивояжёра и системы массового обслуживания. Итак, на вход системы поступает народ. Будем считать, что не более 250 человек. Регистратура запускает их пачками от 1 до 3 штук за раз (будем считать, что у нас сидят 3 независимых регистратора с разной скоростью оформления документов). В учреждении есть штук 30 кабинетов, причём, в некоторых из них функции дублированы. Допустим, у нас есть 2 кабинета УЗИ и 2 кабинета ЭКГ, принимают 2 лора и 2 офтальмолога, но невролог, например, только один, а посетить надо любой один из дублирующих кабинетов. Уникальные кабинеты надо посетить все без исключения. Славный путь клиента должен закончиться в одном из 5 равноценных кабинетов, где дают вожделенную финальную справку. Время обслуживания в каждом кабинете известно, оно не обязано быть одинаковым даже в равноценных по функциям кабинетах. Время перемещения известно от любого кабинета до любого. Очереди допускаются.
Задача: на входе (в регистратуре) по мере поступления распечатывать и выдавать клиентам маршрутные карты, чтобы минимизировать суммарное время прохождения всей толпы через учреждение от регистратуры до выхода из одного из финальных кабинетов.
Забыл что-то важное... А, да, кровь и моча сдаются в разных местах и даже на разных этажах, курить можно только на улице, не ближе 15 метров от входа. Для простоты пока будем считать, что докторам не надо отлучаться в туалет, на обед и перекур для кварцевания и проветривания кабинетов. И да, клиенты мозгом не снабжены. Оперативное изменение маршрутов невозможно.

Ну Вы же произнесли магические слова. Задача оптимизации поточной линии с расчетом ритма и такта.