Я и говорю, что НКРМ - наше всё. Ваши алгоритмы на более старой технике не успеют отработать до угасания Солнца. Мы ведь это считаем "приемлемым временем", если я правильно понял?
Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое
Сообщений 361 страница 390 из 1000
Поделиться3612018-09-09 07:24:18
- Модератор
- Уважение: +14532
- Провел на форуме:
7 месяцев 13 дней - Последний визит:
Сегодня 17:58:40
Поделиться3622018-09-09 07:33:08
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90783,Шарпер написал(а):
Для каждой точки можно выяснить приводит ли ее пропуск к появлению бОльшего пути. Так что рано сдаваться
Конечно приводит.
Ведь общая длина пути не меняется.
Поскольку все точки лежат на кратчайшем пути, убирая два отрезка с кратчайшего пути, и соединяя двумя отрезками предыдущие участки, получаем более длинный путь.
См. мой чертеж.
Красный путь справа длиннее, чем слева черный - кратчайший.
Другое дело, что в мусорные пути по методу Черны попадают еще и "пути" другого рода, типа A→B→B→B→B→B→A, когда из шести участков четыре имеют нулевую длину.
Эти мусорные пути, конечно, короче кратчайшего.
Поделиться3632018-09-09 07:47:49
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90798,Шарпер написал(а):
Но боюсь, что классического способа отсева мусора нет
Надо использовать постнеклассический!
Предлагаю такой постнеклассический вариант:
Сначала отсеять все "правильные" пути - их во многие разы меньше.
Дальше все остальные пути, они все мусорные по разным причинам, за один шаг выбрасываются в корзину!
За один шаг, Карл!
Один шаг!
Мой алгоритм - абсолютный чемпион!
Короче него только мой предыдущий алгоритм, который предлагает вообще не создавать "мусорных" путей.
Тогда от них можно избавиться за ноль шагов.
Но это неспортивно, я знаю!
В техзадании же сказано: "Создать максимум трудностей, и мужественно их преодолевать".
Чем мы успешно и зани маемся.
Если бы было сказано:"Преодолеть",-
мы бы преодолели,
но ведь требуется - "преодолевать"!
Поделиться3642018-09-09 07:51:27
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90801,DoctorLector написал(а):
Я и говорю, что НКРМ - наше всё. Ваши алгоритмы на более старой технике не успеют отработать до угасания Солнца. Мы ведь это считаем "приемлемым временем", если я правильно понял?
Вы сидите в шорах перечисления всех вариантов. Если бы скульптор перечислял бы все варианты отсечений от камня, он ни одной скульпуры бы не заваял. А математики обосновали ьы эту невозможность
Поделиться3652018-09-09 07:52:48
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90802,Лукомор написал(а):
Другое дело, что в мусорные пути по методу Черны попадают еще и "пути" другого рода, типа A→B→B→B→B→B→A, когда из шести участков четыре имеют нулевую длину.
Мы учитываем только одну пропущенную точку.
Поделиться3662018-09-09 07:54:02
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90806,Лукомор написал(а):
Сначала отсеять все "правильные" пути - их во многие разы меньше.
Это способ перечисления.
Поделиться3672018-09-09 08:07:13
- Ветеран
- Уважение: +7554
- Пол: Мужской
- Провел на форуме:
3 месяца 16 дней - Последний визит:
Вчера 13:46:57
#p90761,Лукомор написал(а):
кое кто у нас - латентный апиридил!
В смысле - пассивный?
Disclaimer: 
ни на что не намекаю, я чисто спросить.
Поделиться3682018-09-09 08:12:29
- Ветеран
- Уважение: +7554
- Пол: Мужской
- Провел на форуме:
3 месяца 16 дней - Последний визит:
Вчера 13:46:57
#p90776,Шарпер написал(а):
А из всех 3 628 800 маршрутов только ОДИН самый короткий и первый по времени.
В общем случае - нет. Легко представить систему, где будет более одного варианта самых коротких маршрутов с идентичной длиной.
*уходит писать статью Черны "Задача Буриданова коммивояжера"*
Поделиться3692018-09-09 08:45:07
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Барабаны там-там, акустическая сеть!
#p90764,Шарпер написал(а):
Не получится - частота маленькая
Можно взять N барабанов, с разными собственными частотами.
На них можно сгенерировать достаточное количество мелодий, несущих необходимую информацию.
Ведь в чем фишка алгоритма Черны?
Поскольку TSP-задача - NP-hard, то нельзя никакими ухищрениями одновременно получить полиномиальное время и полиномиальные затраты других ресурсов (например, памяти).
Черны полиномиальное время компенсирует экспоненциальным числом испускаемых бозонов.
Каждый "бозон Черны" имеет достаточную память для хранения данных, необходимых для решения задачи.
Объём этой памяти ограничен количеством квантовых чисел данного бозона, каковых должно быть не меньше N, где N- число городов из условия задачи.
Минимальное число бозонов, необходимое для решения задачи составляет (N-1)^(N-1) при условии, что каждый бозон пройдет своим, оригинальным путем.
Таким образом общая "бозонная память" будет составлять N*(N-1)^(N-1) бит. Обработкой (чтением и записью) этой информации занимаются N*N процессоров, которыми являются каждая щель интерференционной решетки и каждый прибор Штерна-Герлаха.
Таким образом, главным условием работы алгоритма Черны является наличие экспоненциальной памяти,
распределенной между экспоненциальным числом ее носителей - "бозонов Черны".
А сколько "ячеек памяти" у фотона?
Сколько информации может нести фотон, так, чтобы имелся способ ее чтения и изменения во время его пролета через очередной "процессор"?
Я не знаю...
Поделиться3702018-09-09 09:02:23
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90814,Zagar написал(а):
Легко представить систему, где будет более одного варианта самых коротких маршрутов с идентичной длиной.
Трудно представить себе самый короткий маршрут, который "не отражается в зеркале".
То есть такой маршрут, который, будучи пройденным в обратном порядке, будет длиннее самого себя.
Если есть маршрут A→B→C→A, то есть еще другой маршрут A→C→B→A ровно такой же длины.
Теперь, за первый прогон, белопушистый нашел только длину кратчайшего маршрута.
Но сам маршрут он не запомнил, поскольку у фотона нет путевого журнала.
Вернувшись в исходную точку A, он хочет теперь найти остальные точки маршрута "обратным ходом"
При этом получается что обе точки B и С будут "предыдущими" для точки А, причем далее: для точки В предыдущей будет точка С, а для точки С предыдущей будет точка В.
Для комбинации из трех точек ситуацию можно еще разрулить в рукопашную, для 100 000 точек всё не так очевидно...
Поделиться3712018-09-09 09:06:17
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90809,Шарпер написал(а):
Мы учитываем только одну пропущенную точку.
А что мы делаем с вариантом A→B→B→B→B→B→A?
Он ведь тоже мусорный.
Черны его отсеивает, а мы что делаем?
Считаем разрешенным?
Поделиться3722018-09-09 09:10:09
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90813,Zagar написал(а):
В смысле - пассивный?
Наверное, я хотел написать - "перманентный", но... три раза промахнулся по клавишам...
и два раза вообще не попал... 
Поделиться3732018-09-09 09:20:11
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90808,Шарпер написал(а):
Вы сидите в шорах перечисления всех вариантов.
Конечно выгоднее сидеть в шорах отсеивания "мусорных вориантов".
Там шоры - ого-го какие, завернуться можно целиком, как в тулуп!
/уходит, напевая:
"В шкуре волка теплей, чем в тулупе козла-а-а"
(с) Веня Д'ркин "Дружок Фома"/
О, кстати:
Отредактировано Лукомор (2018-09-09 09:29:30)
Поделиться3742018-09-09 10:24:21
- Модератор
- Уважение: +14532
- Провел на форуме:
7 месяцев 13 дней - Последний визит:
Сегодня 17:58:40
#p90808,Шарпер написал(а):
Вы сидите в шорах перечисления всех вариантов
Довольно редкое обвинение, обычно уж чем-чем, но зашоренностью мышления меня не попрекают. К слову сказать, я теперь сомневаюсь насчёт военного применения алгоритма. Всё бы ничего, но подготовка к пуску ракеты в течение нескольких лет может внезапно не устроить наших военных. Можно, правда, попробовать заинтересовать эстонский генштаб.
Поделиться3752018-09-09 10:28:57
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90814,Zagar написал(а):
Легко представить систему, где будет более одного варианта самых коротких маршрутов с идентичной длиной.
Без разницы. Они все придут первыми ноздря в ноздрю. И их все можно проигнорить по равенству
Поделиться3762018-09-09 10:31:07
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90822,DoctorLector написал(а):
Довольно редкое обвинение, обычно уж чем-чем, но зашоренностью мышления меня не попрекают. К слову сказать, я теперь сомневаюсь насчёт военного применения алгоритма. Всё бы ничего, но подготовка к пуску ракеты в течение нескольких лет может внезапно не устроить наших военны
Для военного варианта самый короткий маршрут назнвчается приказом. Это примерно как с числом Пи. 
Поделиться3772018-09-09 10:34:34
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90825,Шарпер написал(а):
Довольно редкое обвинение
А я тоже не догматик, тем более, что из-за того, что занимаю мозги абстрактной задачей, которая по-вилимому не имеет решения, уже месяц живу при нормальном давлении, не лезу в политику и не кусаю форумчан. Согласитесь, что в смысле терапии мне следует продолжать, а провокаторов, которые пытаются доказать мне бесперспективность, следует гнать в шею.
Поделиться3782018-09-09 10:39:37
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90817,Лукомор написал(а):
Можно взять N барабанов, с разными собственными частотами.
Хрен получится найти нужное кол-во собственных частот
#p90817,Лукомор написал(а):
Поскольку TSP-задача - NP-hard, то нельзя никакими ухищрениями одновременно получить полиномиальное время и полиномиальные затраты других ресурсов
Это не доказано и всего лишь мнение. Является проблемой тысячелетия и за решение полагается млн дохлых енотов от института Клея
#p90817,Лукомор написал(а):
Минимальное число бозонов,
Это к квантовикам
Поделиться3792018-09-09 10:41:32
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90818,Лукомор написал(а):
Вернувшись в исходную точку A
Нет там возврата, перечитайте Черны
Поделиться3802018-09-09 10:44:23
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90819,Лукомор написал(а):
А что мы делаем с вариантом A→B→B→B→B→B→A?
Он короче самого короткого с пропуском однй точки и отсеивается на раз. Короче. все мусорные отсеиваются на раз. Единственное, пока не получается найти условие точного соотношения икомого пути и множеств мусорных.
==========
Виноват. Такой вообще запрещен - нельзя в матричном варианте попасть в точку выхода сразу в след слое.
Отредактировано Шарпер (2018-09-09 10:47:45)
Поделиться3812018-09-09 11:01:27
- Модератор
- Уважение: +14532
- Провел на форуме:
7 месяцев 13 дней - Последний визит:
Сегодня 17:58:40
#p90829,Шарпер написал(а):
нельзя в матричном варианте попасть в точку выхода сразу в след слое
Это существенно меняет дело, тогда можно воспользоваться уже готовой программой.
Отредактировано DoctorLector (2018-09-09 11:01:59)
Поделиться3822018-09-09 11:01:49
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90825,Шарпер написал(а):
Для военного варианта самый короткий маршрут назнвчается приказом.
Недаром в военной геометрии любая кривая короче прямой, проходящей мимо начальника!
Поделиться3832018-09-09 11:09:21
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90827,Шарпер написал(а):
Хрен получится найти нужное кол-во собственных частот
Не просто частот, но и их последовательностей (мелодий)!
Отредактировано Лукомор (2018-09-09 11:11:27)
Поделиться3842018-09-09 11:14:13
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90823,Шарпер написал(а):
Они все придут первыми ноздря в ноздрю. И их все можно проигнорить по равенству
Причем все без исключения.
После того как мы проигнорируем все кратчайшие маршруты, переходим к игнорированию более длинных.
Поделиться3852018-09-09 11:20:00
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90833,Лукомор написал(а):
Причем все без исключения.
Ты хочешь, чтобы я рассердился и перещел от бессмысленных упражнений для мозга на личности? Дудки.
Поделиться3862018-09-09 11:48:48
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90828,Шарпер написал(а):
Нет там возврата, перечитайте Черны
Я читал! 
А ты только картинки смотрел... 
Поделиться3872018-09-09 11:51:39
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90835,Лукомор написал(а):
Я читал!
И не додумал, как исключить попадание в начальную точку
Поделиться3882018-09-09 11:53:50
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90834,Шарпер написал(а):
Ты хочешь, чтобы я рассердился
Я хочу чтобы ты сам тоже понял, чо сказал...
Когда ты утверждаешь, что все кратчайшие маршруты
"придут первыми ноздря в ноздрю. И их все можно проигнорить по равенству"
В переводе с бегемотьего это как раз и означает, что все кратчайшие маршруты мы игнорируем.
Поделиться3892018-09-09 11:58:19
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p90836,Шарпер написал(а):
И не додумал, как исключить попадание в начальную точку
Его невозможно исключить.
В начальной точке 1 стоят фиьтры и детекторы Штерна-Герлаха D которые считают длины маршрутов.
Если же мы последний участок пути не приплюсуем, то и не получим длину кратчайшего пути,
и не отсеем мусорные пути
Поделиться3902018-09-09 12:00:00
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 16:46:03
#p90837,Лукомор написал(а):
В переводе с бегемотьего это как раз и означает, что все кратчайшие маршруты мы игнорируем.
Это, разве в переводе с бегемотьего на лукоморный и только
