#p96446,Лукомор написал(а):
Онм же на разных частотах работают...
Ну и как это к нашей задаче?
Тень коммивояжера (психологический триллер).
Сообщений 961 страница 990 из 1000
Поделиться9612019-01-10 00:52:14
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
Поделиться9622019-01-10 01:43:36
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96447,Шарпер написал(а):
Ну и как это к нашей задаче?
Никак!
Поделиться9632019-01-10 07:16:53
- Ветеран
- Уважение: +7554
- Пол: Мужской
- Провел на форуме:
3 месяца 16 дней - Последний визит:
Сегодня 00:05:58
#p96440,Шарпер написал(а):
Лазерный луч же имеет точное направление на приемник, а в лабораторной установке вообще может идти в оптоволокне. Там в принципе не может быть наложения случайных сигналов.
Это если у каждого оптоволокна в конце стоит свой собственный приемник. Итого в системе из N узлов имеем N*(N-1) оптоволокон и соответствующих лазеров и приемников, плюс столько же проводов для передачи управляющих сигналов с маршрутизатора на лазеры и еще столько же проводов для передачи данных всех приемников в маршрутизатор. Плюс собственно маршрутизатор, он же система переработки получаемой информации. И это мы еще не приступали к решению собственно задачи коммивояжера. Это пока что лишь простая аналоговая модель карты расположения узлов вместо обычной цифровой карты, для реализации которой хватит возможностей среднего смартфона.
#p96440,Шарпер написал(а):
Не понимаю, что Вас смущает.
Смущает только то, что задача коммивояжера будет вычислительно гораздо проще задачи правильной маршрутизации сигналов в такой системе.
#p96440,Шарпер написал(а):
Как это нельзя, если в матрице N*N куча слоев и предпоследний в самом верхнем слое?
Простая система, 4 узла: А, Б, В, Г. Допустим, мы знаем, что А - точка входа, Г - точка выхода. Из Г существуют ребра Г-А, Г-Б и Г-В. Ребро Г-А не годится, потому что оно замыкает вход на выход и дает запрещенный короткий маршрут А-Г, выкидываем. Остаются ребра Г-Б и Г-В. Какое выкидываем, какое оставляем?
#p96437,Лукомор написал(а):
После того как я ответил, имею я право узнать, о чём был вопрос?
Можно ли, отправив сигнал в многоузловую систему по априори неизвестной траектории и получив обратный сигнал неизвестно откуда, определить точку выхода сигнала, если известно только время между отправкой и получением сигнала?
#p96443,Лукомор написал(а):
Я же там ясно написал: в сигнале должна накапливаться (и сохраняться, с возможностью считывания) информация о пройденных узлах.
И о порядке их прохождения, разве нет?
Поделиться9642019-01-10 08:59:51
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96453,Zagar написал(а):
Это если у каждого оптоволокна в конце стоит свой собственный приемник. Итого в системе из N узлов имеем N*(N-1) оптоволокон и соответствующих лазеров и приемнико
И что? В любом сотовом т/ф примерно то же самое на плате
#p96453,Zagar написал(а):
Смущает только то, что задача коммивояжера будет вычислительно гораздо проще задачи правильной маршрутизации сигналов в такой системе.
Нет.
#p96453,Zagar написал(а):
Простая система, 4 узла: А, Б, В, Г. Допустим, мы знаем, что А - точка входа, Г - точка выхода. Из Г существуют ребра Г-А, Г-Б и Г-В. Ребро Г-А не годится, потому что оно замыкает вход на выход и дает запрещенный короткий маршрут А-Г, выкидываем. Остаются ребра Г-Б и Г-В. Какое выкидываем, какое оставляем?
Ну 4-х угольник же особый случай, который Вы вон в уме решаете, заранее зная запрещенный путь. Но неважно. При вершине Г у нас три ребра. Вот и берите любую половину (или по отдельности) и проверяйте.
Для наглядлности лучше взять 6-ти угольник
При вершине - 5 ребер, вот и берите любую их половину
#p96453,Zagar написал(а):
Можно ли, отправив сигнал в многоузловую систему по априори неизвестной траектории и получив обратный сигнал неизвестно откуда, определить точку выхода сигнала, если известно только время между отправкой и получением сигнала?
Ну вот на зимней рыбалке рыба плывущая по неизвестной траектории определяет лунку своим натуральным выходом. В чем проблемы-то?
Поделиться9652019-01-10 09:48:23
- Ветеран
- Откуда: Е-бург
- Уважение: +2216
- Пол: Мужской
- Возраст: 71 [1953-03-03]
- Провел на форуме:
4 месяца 5 дней - Последний визит:
Сегодня 14:37:33
#p96456,Шарпер написал(а):
При вершине - 5 ребер, вот и берите любую их половину
А что, не хватает ребер ?
Поделиться9662019-01-10 10:24:57
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96456,Шарпер написал(а):
Для наглядлности лучше взять 6-ти угольник
Вот именно этот я тоже в уме решаю! 
Поделиться9672019-01-10 10:31:35
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96459,Лукомор написал(а):
Вот именно этот я тоже в уме решаю!
Но здесь хотя бы 5 надо на 2 делить, а не 3 
Поделиться9682019-01-10 10:32:16
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96458,SERGEY написал(а):
А что, не хватает ребер ?
Ну кое у кого я понял есть проблемы
Поделиться9692019-01-10 10:46:17
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96453,Zagar написал(а):
Простая система, 4 узла: А, Б, В, Г. Допустим, мы знаем, что А - точка входа, Г - точка выхода. Из Г существуют ребра Г-А, Г-Б и Г-В. Ребро Г-А не годится, потому что оно замыкает вход на выход и дает запрещенный короткий маршрут А-Г, выкидываем. Остаются ребра Г-Б и Г-В. Какое выкидываем, какое оставляем?
Перебором.
Шарпер сначала в А пущает сигнал, и в Г засекает время.
Потом отключает ребро ГБ гипотетическим магическим электронным коммутатором, и запускает снова луч из А.
Снова засекает время. Если время совпало, значит ГВ предыдущее ребро на кратчайшем пути.
Если не совпало, включает обратно ГБ, отключает ГВ, Снова запускает сигнал из А, засекает время.
Если время совпало, значит мы убедились, что последний участок пути - ГБ.
Теперь отключаем все входящие в Г, кроме БГ. Отключаем один из двух участков, входящих в Б.
Снова запускаем сигнал из А.
Если время не изменилось, переходим еще на один уровень к началу.
если время изменилось, включаем отключенный участок, отключаем другой.
снова запускаем сигнал из А в Г.
И. т. д., пока не доберемся трудами великими до исходного пункта А.
Я уже выше отмечал, что число всех этих включений/отключений растет экспоненциально, но Шарпер считает по своему.
Для него выключить, допустим 64 участка, и включить другие 64, - это ОДНО действие, а не 128, поэтому сложность алгоритма получается логарифмическая...
Он так видит... 
Поделиться9702019-01-10 10:50:21
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96460,Шарпер написал(а):
Но здесь хотя бы 5 надо на 2 делить, а не 3
Здесь не надо делить!
Пятиугольник выпуклый, значит кратчайший путь проходит по периметру:
АBCDEFA, соответственно сопряженный к нему AFEDCBA.
Поделиться9712019-01-10 10:55:43
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96453,Zagar написал(а):
И о порядке их прохождения, разве нет?
По хорошему - да! И о пройденном расстоянии (типа автомобильного одометра)...
По плохому - хотя бы только пройденные узлы, чтобы на финише знать, - полный маршрут, или где-то есть срезанный угол....
По Шарперу - пофиг на ту информацию.
Поделиться9722019-01-10 11:09:59
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96453,Zagar написал(а):
Можно ли, отправив сигнал в многоузловую систему по априори неизвестной траектории и получив обратный сигнал неизвестно откуда, определить точку выхода сигнала, если известно только время между отправкой и получением сигнала?
я опять ничего не понял. 
Особенно про "точку выхода" 
Гугль знает только .точку выхода троичного нерва, точку выхода седалищного нерва, и точку выхода из языка.
Которую будем определять7 
А да, еще "точку выхода луча", которая определяется, как
"Точка пересечения акустической оси с контактной поверхностью преобразователя.
Задолбали уже эти шарперизмы. 
Как по мне, точка выхода, это то место откуда сигнал выходит в путь, то-есть стартует.
Определять ее не надо, мы и так знаем, в какой точке мы запустили сигнал в эту систему.
Поделиться9732019-01-10 11:13:45
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96460,Шарпер написал(а):
Но здесь хотя бы 5 надо на 2 делить, а не 3
Да чего там делить-то.
Пять, если делить на 2, - это одна четверка и одна единица, .
Подумаешь, высшая арифметика, это каждый знает!
Поделиться9742019-01-10 11:19:24
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96462,Лукомор написал(а):
Я уже выше отмечал, что число всех этих включений/отключений растет экспоненциально, но Шарпер считает по своему.
Втупи, наконец, про бинарный поиск и вычисли log2(N!) - 100!= 9,332621544×10¹⁵⁷ , а log₂(100!)=524,76499329
и повторить N раз.
Поделиться9752019-01-10 11:27:47
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96463,Лукомор написал(а):
Здесь не надо делить!
Пятиугольник выпуклый, значит кратчайший путь проходит по периметру:
АBCDEFA, соответственно сопряженный к нему AFEDCBA.
Не лергай раками! Играем в конкретный способ бинарного поиска пути
#p96464,Лукомор написал(а):
По Шарперу - пофиг на ту информацию.
Умница! Дедуктивный метод рулит.
#p96466,Лукомор написал(а):
Да чего там делить-то.
#p96465,Лукомор написал(а):
Задолбали уже эти шарперизмы.
#p96466,Лукомор написал(а):
Да чего там делить-то.
Если пошевелить эклером, то Ал говорил о какой-то кассе. Нет? Я не посвящен... 
Поделиться9762019-01-10 11:29:52
- Ветеран
- Уважение: +7554
- Пол: Мужской
- Провел на форуме:
3 месяца 16 дней - Последний визит:
Сегодня 00:05:58
#p96456,Шарпер написал(а):
Вот и берите любую половину (или по отдельности) и проверяйте.
Проверили, подходят обе. Какую выкидывать?
#p96465,Лукомор написал(а):
я опять ничего не понял.
Особенно про "точку выхода"
Вот запустили мы луч в систему, первый узел, с которого стартует луч, это будет точка входа. Луч погулял по системе узлов и с какого то последнего узла пришел к нам на приемник. Вот этот последний узел - точка выхода. Можно ли определить из какого узла пришел последний сигнал, если мы знаем только время между входом и выходом луча?
Поделиться9772019-01-10 11:37:29
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96469,Zagar написал(а):
Проверили, подходят обе. Какую выкидывать?
Не могут они обе подойти - там по условию расстояния разные, а время у Вас одно.
#p96469,Zagar написал(а):
Вот запустили мы луч в систему, первый узел, с которого стартует луч, это будет точка входа. Луч погулял по системе узлов и с какого то последнего узла пришел к нам на приемник. Вот этот последний узел - точка выхода. Можно ли определить из какого узла пришел последний сигнал, если мы знаем только время между входом и выходом луча?
В матричном варианте точками входа и выхода м.б. все точки. Ловим кратчайший по времени разрешенный у всех точек
Поделиться9782019-01-10 11:47:52
- Ветеран
- Уважение: +7554
- Пол: Мужской
- Провел на форуме:
3 месяца 16 дней - Последний визит:
Сегодня 00:05:58
#p96462,Лукомор написал(а):
Перебором.
Шарпер сначала в А пущает сигнал, и в Г засекает время.
Потом отключает ребро ГБ гипотетическим магическим электронным коммутатором, и запускает снова луч из А.
Снова засекает время. Если время совпало, значит ГВ предыдущее ребро на кратчайшем пути.
Если не совпало, включает обратно ГБ, отключает ГВ, Снова запускает сигнал из А, засекает время.
Если время совпало, значит мы убедились, что последний участок пути - ГБ.
Теперь отключаем все входящие в Г, кроме БГ. Отключаем один из двух участков, входящих в Б.
Снова запускаем сигнал из А.
Если время не изменилось, переходим еще на один уровень к началу.
если время изменилось, включаем отключенный участок, отключаем другой.
снова запускаем сигнал из А в Г.
И. т. д., пока не доберемся трудами великими до исходного пункта А.
Я уже выше отмечал, что число всех этих включений/отключений растет экспоненциально, но Шарпер считает по своему.
Для него выключить, допустим 64 участка, и включить другие 64, - это ОДНО действие, а не 128, поэтому сложность алгоритма получается логарифмическая...
А вот сразу нельзя было так объяснить? 
Насчет трудозатрат, я так понимаю, что на последнем узле надо протестить N-1 его связей с остальными узлами. На выбранном предпоследнем нужно будет прозвонить N-2 связи (одну уже тестили на предыдущем этапе, надо, правда, будет запомнить какую). Итого на каждом из m-ных шагов надо проверять N-m связей, всего таких шагов M=N-1. Общей число тестировок по схеме что-то типа (N-1)*N/2. То есть вполне себе полиномиальное количество.
Если считать, что прозвон одной связи это одна операция.
И только если считать, что мы знаем точку выхода, что для меня совсем не факт.
Поделиться9792019-01-10 11:58:47
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96471,Zagar написал(а):
А вот сразу нельзя было так объяснить?
А я как объяснял изначально?
Ну я же описывал уже. С него началась упопея.
Если мы знаем точку выхода и время наикратчайшего разрешенного сигнала, то восстановить весь путь бинарным поиском от конца к началу плевое дело.
1 Отрубаем половину участков которые могут претендовать на предпоследние и снова запускаем агрегат. Если сигнал совпал с предыдущим, значит в этой половине предыдущий участок пути
2 Отрубаем еще половину и снова повторяем пока не останется один предпоследний участок.
3 Берем предпоследнюю точку за последнюю и повторяем фокус с ней.
#p96471,Zagar написал(а):
Насчет трудозатрат, я так понимаю, что на последнем узле надо протестить N-1 его связей с остальными узлами.
log2((N=1)!) на каждую точку (или слой)
Поделиться9802019-01-10 12:02:05
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96471,Zagar написал(а):
И только если считать, что мы знаем точку выхода, что для меня совсем не факт.
(вкрадчиво) А вот, если Вы поймали рыбку из подо льда, этого достаточно для регистрации местоположенния лунки и времени ее вылова?
Поделиться9812019-01-10 12:17:34
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96467,Шарпер написал(а):
Втупи, наконец, про бинарный поиск и вычисли log2(N!) - 100!= 9,332621544×10¹⁵⁷ , а log₂(100!)=524,76499329
и повторить N раз.
Ты где эту формулку взял?!
Положи на место, и не трогай, если пользоваться не умеешь...
Вот для N=6, твоя формулко даёт log2(N!)=2,56...
Вот и распиши эти 2, 56... действия, применительно к твоему чертежу для шести точек.
Что включаем, что исключаем, что получаем.
Единственное условие - уложиться в 2, 56... элементарных операций.
Поделиться9822019-01-10 12:26:43
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96468,Шарпер написал(а):
Не лергай раками! Играем в конкретный способ бинарного поиска пути
Какой на бинарный поиск, если кратчайший путь для каждого случая известен.
Для выпуклого шестиугольника - это периметр.
Для выпуклого пятиугольника, шестая точка внутри, другой способ.
Для выпуклого четырехугольника, две точки внутри, еще один способ.
Для треугольника с тремя точками внутри - свой способ.
Итого - четыре варианта всего.
и в каждом сразу находится кратчайший путь.
Поделиться9832019-01-10 12:26:51
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96474,Лукомор написал(а):
Ты где эту формулку взял?!
Двоичный поиск к Вашим услугам. Есть в Вики, так что я не вижу смысла расписывать
Поделиться9842019-01-10 12:28:08
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96475,Лукомор написал(а):
Какой на бинарный поиск, если кратчайший путь для каждого случая известен.
Еще раз. Мы рассматриваем пример двоичного поиска! Не надо лезть с частным случаем
Поделиться9852019-01-10 12:28:10
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96468,Шарпер написал(а):
Дедуктивный метод рулит.
Дефективный метод!
Поделиться9862019-01-10 12:30:33
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96468,Шарпер написал(а):
Если пошевелить эклером
Шевелить эклером прилюдно - это просто-таки неприлично!
Поделиться9872019-01-10 12:33:50
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96469,Zagar написал(а):
Можно ли определить из какого узла пришел последний сигнал, если мы знаем только время между входом и выходом луча?
Нет.
Поделиться9882019-01-10 12:39:02
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p96470,Шарпер написал(а):
Не могут они обе подойти - там по условию расстояния разные
А суммарные расстояния могут оказаться одинаковыми.
Например:
Один маршрут:27 секунд, плюс 33 секунды, плюс 30 секунд = всего полторы минуты.
Второй маршрут: 45 секунд, плюс 10 секунд, плюс 35 секунд = всего полторы минуты.
Поделиться9892019-01-10 12:39:52
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96480,Лукомор написал(а):
Zagar
Можно ли определить из какого узла пришел последний сигнал, если мы знаем только время между входом и выходом луча?
Нет.
Подпись автора
"Самая тяжелая болезнь на свете, -
это привычка думать. Она неизлечима."© Эрих Мария Ремарк
Можно! По условию, каждый путь имеет свое время, а значит и точку выхода, в которой это время регистрируется. Дальше как обычно
Поделиться9902019-01-10 12:41:49
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 13:25:43
#p96481,Лукомор написал(а):
А суммарные расстояния могут оказаться одинаковыми.
Не могут, если об этом специально позаботиться и изменить расстояния для исключения совпадений.
