Амальгама |
Привет, Гость! Войдите или зарегистрируйтесь.
Вы здесь » Амальгама » Лукоморье 2.0 » Тень коммивояжера (психологический триллер).
Вот это вот, "Бинарным поиском, отключая по половине",
уф. Ты алгоритм поиска льва в пустыне знаешь? Пустыня делится пополам и в половине ищется лев. Та. в которой он найден делится снова пополам и т.д, пока не выловишь
Это бинарный поиск. Дальше мне непонятно что тут непонятного. в чем проблема найти ветку по которой пришел паровоз?
что такое слой на матрице? И как отрубить слой?
Ты схему Черны помнишь? Матрица N*N. Слой- строка.
что такое слой на матрице? И как отрубить слой?
Ты схему Черны помнишь? Матрица N*N. Слой- строка.
Останется матрица N(N-1), и кратчайший путь на ней может измениться...
Дальше мне непонятно что тут непонятного
непонятно "отключая по половине"
Слой- строка.
"Отрубаешь слой" = "отключаешь по половине".
А где вторая половина?!
Отредактировано Лукомор (2019-01-08 22:34:37)
Останется матрица N(N-1), и кратчайший путь на ней может измениться...
Нет. Время у него одно и то же.
непонятно "отключая по половине"
Ну в последнюю точку приходит N ребер. Заблокируй половину и выяснишь через какую половину прошел сигнал с нашим временем. И так пока не найдеш единственное ребро
А где вторая половина?!
Перекрыта вентилями!
Перекрыта вентилями!
Это все оставшиеся слои?! а как через вентиля сигнал идет?!
Одну половину отключил, вторую половину перекрыл вентилями.
ет. Время у него одно и то же.
У него - то же, но появятся пути с меньшим временем...
Это все оставшиеся слои?! а как через вентиля сигнал идет?!
Нет, только предпоследний слой. Никак сигнал не идет через перекрытые
У него - то же, но появятся пути с меньшим временем...
ыыыыыыыыы! Ну так следи только за сигналоом с известным временем!
Откуда вспышки
Справа.
или Слева.
Справа.
Рассвет у Вас штоле?
Ну я же сказал, нам важно какой приемник примет, а ближайший передатчик мы найдем по времени сигнала.
У нас на карте запросто может быть несколько передатчиков примерно на одинаковом расстоянии от приемника. Примерно одинаковом значит, что разница в расстоянии будет в пределах дальности распространения эм волн в рамках фиксированной погрешности определения времени. То есть все узлы в пределах города средней величины будут примерно равноудалены от приемника и различить их по времени прихода сигнала не получится.
На остальную морзянку начхать
Она будет создавать фон, на котором невозможно будет установить сам факт поступления нужного сигнала.
На всякий случай, для общего развития... Это устаревшая технология, когда по полю едет пеленгатор с крутящейся на крыше кузова антенной.
современные пеленгаторы стоят на месте, и определяют азимут на радиостанцию в считанные секунды.
В кино про Штирлица так запеленговали Юстаса, а вот за Алексом персональные машины посылали. 
Вот ты лучше скажи можно ли в реальности определить не только азимут, но и расстояние до передатчика.
Ну вот и все. Не катит.
Оно бы не катило даже если все работало бы как ты думаешь. Из-за невозможности определения точки выхода.
Пустыня делится пополам и в половине ищется лев. Та. в которой он найден делится снова пополам и т.д, пока не выловишь
Это когда лев один.
А тут ты делишь карту пополам, часть нужных узлов в одной половине, вторая - во второй. Какую половину выкидываем?
У нас на карте запросто может быть несколько передатчиков примерно на одинаковом расстоянии от приемника
Нет. Я не знаю, что Вы представляеите, но я говорю о специальной лабораторной установке основанной на измерении либо расстояния, либо времени. Так что "примерно" там ничего быть не может.
Она будет создавать фон, на котором невозможно будет установить сам факт поступления нужного сигнала.
Не будет - она придет ПОЗЖЕ.
============
Вы вообще не о том спорите. В конструкции проблем вообще никаких - обычный оптический компьютер. Проблема в способе отсева запретных путей
Из-за невозможности определения точки выхода.
Это как раз элементарно - представьте десяток передатчиков и десяток приемников на разном расстоянии, причем все передатчики стартуют одновременно. Первой свяжется ближайшая пара.
Это когда лев один.
Он и есть один - кратчайший по времени разрешенный сигнал.
А тут ты делишь карту пополам, часть нужных узлов в одной половине, вторая - во второй. Какую половину выкидываем?
Любую. Это стандартный алгоритм бинарного поиска. Не верите мне, прочтите в ВИКИ.
Ищем в одной половине, если нет - ищем в другой, т.е. отключам сначала одну, а потом, если не нашли - вторую половину.
Потом берем половину половины и так до единственного ребра, по которому проходит сигнал совпадающий со временем кратчайшего.
Вот ты лучше скажи можно ли в реальности определить не только азимут, но и расстояние до передатчика.
В реальности поступают по другому: Разносят на местности 3-4 пеленгатора. Максимум 6, потому что при дальнейшем увеличении их количества
точность определения координат растет незначительно...
Зная точно координаты пеленгаторов, и азимуты с каждого из них на передатчик, на пересечении азимутов получают точку, где находится радиостанция.
Для того, чтобы определять дальность с одной точки, необходимо, как минимум, знать мощность передатчика, при этом всё равно точность будет гораздо ниже,
чем при определении азимутов с нескольких точек.
а вот за Алексом персональные машины посылали.
Ну это потому что в городе, где переотражение от зданий, от любых препятствий искажает азимут.
Такое тоже имеет место быть, например, есть такой технический вид спорта -
спортивная радиопеленгация, в народе именуемая "охота на лис".
Она похожа на спортивное ориентирование, о котором я уже здесь упоминал.
Разница в том, что на каждом КП установлены радиопередатчики, каждый из которых
периодически передает свой уникальный сигнал.
у каждого участника имеется переносной пеленгатор, с которого он периодически,
двигаясь по маршруту, определяет азимуты с разных точек на разные радиостанции, уточняя их местоположение.
Задача: найти все КП, получить на каждом отметку, и вернуться на финиш, желательно первым по времени.
ыыыыыыыыы! Ну так следи только за сигналоом с известным временем!
Кошмарный случай, если совпадет время от двух различных маршрутов, мы не рассматриваем?
Рассвет у Вас штоле?
типа персеиды прилетели
Он и есть один - кратчайший по времени разрешенный сигнал.
А если два разных сигнала, у которых время одинаковое, а маршруты разные?
обычный оптический компьютер.
Гипотетический... 
Его еще не изобрели пока...
Отредактировано Лукомор (2019-01-09 11:12:18)
а потом, если не нашли - вторую половину.
При этом нужно включить обратно первую половину.
А поскольку одним движением "половину" выключить нельзя, нужно выключить каждый из элементов этой половины,
если не угадал, нужно каждый элемент первой половины включить обратно, и выключить каждый элемент второй половины.
Потом такие же операции нужно проделать с четвертью, и с другой четвертью, и.т.д.
это только я один цикл расписал.
А таких циклов - (N-1).
А еще, после каждой серии включений/выключений нужно запустить всю эту систему, и получить новые значения кратчайшего пути...
И, хотя количество запусков программы будет расти логарифмически,
но количество операций включения и выключения будет по-прежнему расти экспоненциально, а с ним и время на решение всей задачи.
Первой свяжется ближайшая пара.
Еще раз.
Нам не нужна ближайшая пара.
нам нужно минимальное время прохождения по цепочке из всех различных пар.
А таких циклов - (N-1).
кроме цикла где эн равно нулю !!!
кроме цикла где эн равно нулю !!!
это для двух городов только...
Там можно и полным перебором одного варианта ответ найти.
Зная точно координаты пеленгаторов, и азимуты с каждого из них на передатчик
А по рельсам так вообще...
Кошмарный случай, если совпадет время от двух различных маршрутов, мы не рассматриваем?
Значит будет два равнозначных кратчайших и что?
А если два разных сигнала, у которых время одинаковое, а маршруты разные?
Только что выше напейсал
Его еще не изобрели пока...
Это квантовый не изобрели, а оптический еще в 1983 году работал
При этом нужно включить обратно первую половину.
А поскольку одним движением "половину" выключить нельзя, нужно выключить каждый из элементов этой половины,
если не угадал, нужно каждый элемент первой половины включить обратно, и выключить каждый элемент второй половины.
Потом такие же операции нужно проделать с четвертью, и с другой четвертью, и.т.д.
это только я один цикл расписал.
А таких циклов - (N-1).
Дас ист фантастиш! У тебя спецвычислитель. Какие проблемы с программным управлением отключением?
А log2((N-1)!) это малое число. Убедись на калькуляторе
Нам не нужна ближайшая пара.
нам нужно минимальное время прохождения по цепочке из всех различных пар.
Ну вот послойно и восстановишь весь путь от ребра к ребру
---------------------
И вообще. Проблема в отсеве, а не в конструкции, но все почему-то предпочитают обсуждать именно ее
Проблема в отсеве, а не в конструкции, но все почему-то предпочитают обсуждать именно ее
ну понятно же почему.
Отсев невозможен за полиномиальное время, так хрен ли его обсуждать.
А конструкция - она такая конструкция... эфемерная...
Поскольку никто не может ничего понять про эту конструкцию, а всем интересно,
хотя понятно, что реализовать ее не удастся, то народ интересуется.
Законное любопытство...
Ну вот послойно и восстановишь весь путь от ребра к ребру
А если таких путей внезапно больше одного?!
Отредактировано Лукомор (2019-01-09 12:54:43)
тебя спецвычислитель.
Гипотетический...
Какие проблемы с программным управлением отключением?
экспоненциальный рост числа таких элементарных операций не проблема, не?!
А log2((N-1)!) это малое число.
A 2^N - это большое число... очень большое...
Отредактировано Лукомор (2019-01-09 13:03:16)
Вы здесь » Амальгама » Лукоморье 2.0 » Тень коммивояжера (психологический триллер).
