Содействие - исключение из 3-го закона Ньютона.

Амальгама

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Амальгама » Лукоморье 2.0 » Вторая тень


Вторая тень

Сообщений 61 страница 90 из 1000

61

#p96627,Zagar написал(а):

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

Т.е. концевой выключатель у Вас есть ЦУ? Ну, в смысле отрубания всего и вся -= таки да.

#p96627,Zagar написал(а):

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

А я Вам в 100500-й раз специально отвечаю, что
1 маршрутизатор в том смысле какой вкладываете Вы по аналогии с вычислительными сетями здесь не нужен. Нужен повторитель с настраиваемой задержкой. [

2 бестолку обсуждать конкретную конструкцию установки, если неизвестен способ отсева запретных путей. Они м.б. самыми разными от графа до матрицы.

#p96627,Zagar написал(а):

Ты ответил, что маршрутизатор нужен. ОК, я тоже так думаю. Хрен с ним, что он будет стоить дороже гугла со всеми его дата-центрами, он ведь нам не этим дорог.

Вот что мне тут нравится на форуме, так это маниакальная способность участников обсуждать не принциаиальную невозможность "драки Годзиллы с Кинг-Конгом на небоскребе, а технику боя и их вооружение"

И эти люди, запрещают мне фантазировать!

0

62

#p96628,Zagar написал(а):

В принципе и это возможно. Если поставить приемник-спектрометр с лазером-модификатором сигнала не во ВСЕ узлы, а на ВСЕ ребра между узлами. То есть надо всего-то не N спектрометров-лазеров, а N*(N-1) спектрометров и столько же лазеров. Тогда такая система может работать без перекрытия сигналов даже при их одновременном движении.


Да ради бога! Матричная реализация.

#p96628,Zagar написал(а):

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

Полупроводникрвые лазеры позволяют все сделать на плате. Про спектрометры я не знаю.

0

63

#p96639,Шарпер написал(а):

http://ru.knowledgr.com/00367333/ВычислительнаяНеприводимость

По-прежнему, не прошу ссылку на конкретную цитату из конкретной книги Вольфрама, которую Шарпер в глаза не видел...

Та ссылка, с видом на роскошную помойку,

где удивительным образом соседствуют "Артур Шопенгауэр" и "Удивительный человек-паук",
"алтайские языки" и "Анна Курникова", "Альберт Эйнштейн" и "однолетнее растение",

она, вообще говоря, о другом.

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

Ссылка же, любезно представленная нашим альтернативномыслящим другом,
ведет нас прямо к понятию "Вычислительной Неприводимости", некой метафизической сущности,
смысл которой заключается в невозможности выразить простыми формулами сложные явления Природы.

Отредактировано Лукомор (2019-01-15 02:40:23)

0

64

Никак не могу перейти к случаю N=5,
который для моих традиционных исходных данных уже просчитан вдоль и поперек,
и так и просится быть выложенным в это теме.

Всё время что-то отвлекает...

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

Я начал эту эпопею, еще в бегемотьей теме, с рассмотрения случая N=6,
для которого я выбрал некоторые начальные условия и правила их изменения.

При этом для расчета кратчайшего пути я пользовался стандартным он-лайн калькулятором,
"спецвычислителем", каковых достаточно на просторах интернетов,
а калькулятор пользовался "методом ветвей и границ".

Калькулятор давал какое-то решение, я особо не проверял, всё шло  хорошо,
до тех пор, пока я не перешел к случаю N=4, и не начал практиковать просчет всех путей, благо их всего три различных для этого случая.
И вот тут оказалось, что для полностью развернутого "складного метра", и для полностью сложенного,
есть два замкнутых пути одинаковой протяженности.

http://s7.uploads.ru/x8NXW.jpg

Два из трех!
Далее, при внимательном рассмотрении, оказалось, что для случая N=5 таких совпадающих по длине замкнутых маршрутов 4 (из 12),
четыре на полностью развернутом "складном метре" (угол между любыми двумя смежными участками маршрута составляет 180 градусов),
и четыре - на полностью сложенном (угол между соседними отрезками составляет ноль градусов).
Причем один из этих четырех маршрутов умудряется быть кратчайшим на обоих концах  интервала
(и больше нигде, ни при каком значении угла внутри интервала от 0 до 180 градусов).
Далее, оказалось, что для N=6 таких совпадающих по длине кратчайших маршрутов, на концах интервала углов будет уже по 8.
(А он-лайн калькулятор давал один кратчайший маршрут!).
Для любого произвольного N, количество кратчайших замкнутых маршрутов в линейной задачи коммивояжера  будет равно:
$$\large 2^{(N-3)}$$

Отредактировано Лукомор (2019-01-15 16:15:57)

0

65

#p96640,Шарпер написал(а):

Т.е. концевой выключатель у Вас есть ЦУ? Ну, в смысле отрубания всего и вся -= таки да.

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

#p96640,Шарпер написал(а):

1 маршрутизатор в том смысле какой вкладываете Вы по аналогии с вычислительными сетями здесь не нужен. Нужен повторитель с настраиваемой задержкой. [

Не будет работать. На всех приемниках вместо сигналов будет белый шум. Если точнее, то прерывистый белый шум с настраиваемой ритмичностью.

#p96640,Шарпер написал(а):

2 бестолку обсуждать конкретную конструкцию установки, если неизвестен способ отсева запретных путей.

Известен. Один мой знакомый Шарпер уже давно, топика два назад, его обнаружил.

#p96640,Шарпер написал(а):

Вот что мне тут нравится на форуме, так это маниакальная способность участников обсуждать не принциаиальную невозможность "драки Годзиллы с Кинг-Конгом на небоскребе, а технику боя и их вооружение"

А я еще на мембране предлагал решить все энергетические проблемы человечества за счет применения недорогих небольших легких очень мощных аккумуляторов с бесконечным запасом энергии. И не надо портить эту гениальную идею всякими глупыми вопросами о технической реализации.
PS: Точнее, я даже насчет реализации все тогда решил: надо просто снабженцам поручить найти и купить такие аккумуляторы в нужном количестве.
В данном случае это можно поручить коммивояжерам: пусть они сами найдут и сами внедрят в свою практику алгоритм построения оптимального маршрута с линейной сложностью N/2. Кто не найдет, лишать премии.

#p96641,Шарпер написал(а):

Полупроводникрвые лазеры позволяют все сделать на плате.

И чтобы воссоздать реальную геометрию задачи, их надо будет по плате двигать? С нанометровой точностью. И как насчет точности определения расстояния в несколько десятков нанометров лазерным дальномером?
В конце концов, есть готовые процессоры на компах, которые все это реализуют как надо, с меньшими затратами и глюками, только с электричеством вместо лазерного света. Зачем изобретать лазерный велосипед?

Отредактировано Zagar (2019-01-15 05:33:51)

0

66

#p96643,Лукомор написал(а):

По-прежнему, не прошу ссылку на конкретную цитату из конкретной книги Вольфрама, которую Шарпер в глаза не видел...

А почему это я должен ублажать Ваш личный эклер, при условии, что я с Мембрании еще про вычислительную неприводимость и клеточные автоматы  пишу?
Короче, эксклюзивно для Лукоморов с карамелью головного мозга! Журнал "В мире науки" №11 за 1984 год ссылка, откуда можно скачать https://sites.google.com/site/zurnalyss … a-1984-god
Статья С.Вольфрама на 98 странице, определение неприводимости под картинкой на 108 стр.  Все? Или через неделю снова при упоминании потребуете пруфов? Запишите тогда на бумажке штоле!  http://www.kolobok.us/smiles/big_madhouse/ireful.gif

#p96643,Лукомор написал(а):

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

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

0

67

#p96646,Zagar написал(а):

.

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

Я не о сигналах, а о терминах. Концевик, даже если он не обычная кнопка, а создание на основе технического зрения и нейронных сетях, никак не м.б. отнесен к центру управления в моем понимании.

#p96646,Zagar написал(а):

Не будет работать. На всех приемниках вместо сигналов будет белый шум. Если точнее, то прерывистый белый шум с настраиваемой ритмичностью.

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

#p96646,Zagar написал(а):

Известен. Один мой знакомый Шарпер уже давно, топика два назад, его обнаружил.

Нет. Все способы оказались неверны. Последний, со спектрами, забраковали Вы. Или Вы нашли способ?

#p96646,Zagar написал(а):

В данном случае это можно поручить коммивояжерам:

У нас экономика всей страны им и поручена. Которую пятилетку в пути, но из пустыни пока не вывели. Наоборот, пустыня прирастает (Сибирью), что наводит на мысль, что пустыню нельзя вывести из коммивояжеров и мир обреченЪ.

#p96646,Zagar написал(а):

В конце концов, есть готовые процессоры на компах, которые все это реализуют как надо, с меньшими затратами и глюками, только с электричеством вместо лазерного света. Зачем изобретать лазерный велосипед?

Обычный комп не умеет решать задачи физическим способом, тем более с распараллеливанием. Здесь требуется гибридный вычислитель. А численное моделирование опять упрется в NP

#p96646,Zagar написал(а):

И чтобы воссоздать реальную геометрию задачи, их надо будет по плате двигать? С нанометровой точностью. И как насчет точности определения расстояния в несколько десятков нанометров лазерным дальномером?

Про дальномер я писал для примера аналогово-цифрового устройства. А расстояние вполне успешно и даже проще моделируется задержкой времени.

0

68

#p96648,Шарпер написал(а):

определение неприводимости под картинкой на 108 стр.


Под картинкой на стр.108 - пояснение к картинке на стр.108.

"ЯВЛЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ НЕРАЗРЕШИМОСТИ, по-видимому, возникает во
многих физических и математических системах".


Это не сильно тянет на определение...

0

69

#p96648,Шарпер написал(а):

В том-то и дело, что NP проблема возникает только при применении способов полного перебора, т.е. иначе вычислительного  эксперимента с перечислением.

Дело совершенно в другом.
Дело в том, что проблемы NP не существует.

Есть проблема P=NP, которая говорит, что полный перебор - это тупо, и что не надо перебирать заведомо "плохие" варианты, число которых экспоненциально растет,
а надо перебирать только "хорошие" варианты, которые могут быть конкретными кандидатами на решение, и количество которых растет полиномиально.

0

70

Я продолжу про линейную задачу коммивояжера для четырех городов...

После того, как выяснилось, что в линейном варианте не один,
а сразу два различных замкнутых маршрута будут кратчайшими,

http://s7.uploads.ru/x8NXW.jpg

а третий возможный маршрут неизбежно будет длиннее тех двух,

http://sd.uploads.ru/k8nlV.jpg

я задумался, а почему так происходит...

Отредактировано Лукомор (2019-01-15 19:55:49)

0

71

#p96652,Лукомор написал(а):

Это не сильно тянет на определение...

Читать надо до конца! Я уж не прошу всю статью, хотя бы до конца тот абзац, начало которого Вы привели.

0

72

#p96653,Лукомор написал(а):

Дело совершенно в другом.
Дело в том, что проблемы NP не существует.

Есть проблема P=NP, которая говорит, что полный перебор - это тупо, и что не надо перебирать заведомо "плохие" варианты, число которых экспоненциально растет,
а надо перебирать только "хорошие" варианты, которые могут быть конкретными кандидатами на решение, и количество которых растет полиномиально.

Офигенно!

Мое утверждение

#p96648,Шарпер написал(а):

NP проблема возникает только при применении способов полного перебора,


Категорическое его опровержение Лукомором -

"Дело в том, что проблемы NP не существует.

Есть проблема P=NP, которая говорит, что полный перебор - это тупо"

Маладес! Я таки сейчас понял, что значит "две большие разницы"  http://www.kolobok.us/smiles/light_skin/yahoo.gif

Отредактировано Шарпер (2019-01-15 16:33:46)

0

73

#p96656,Шарпер написал(а):

Маладес! Я таки сейчас понял, что значит "две большие разницы"

Сказать-то чё хотел?!

Отредактировано Лукомор (2019-01-15 16:36:22)

0

74

#p96655,Шарпер написал(а):

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

Я прочитал...
Там нет ничего про задачи классов P и NP.
Там про Вычислительную Неразрешимость.
Это про совсем другое...

0

75

#p96656,Шарпер написал(а):

Офигенно!
Мое утверждение: "NP проблема возникает"


#p96656,Шарпер написал(а):

Категорическое его опровержение Лукомором -
"Дело в том, что проблема NP не возникает".


- Да, опровержение.
- Да, категорическое.

Офигенно?!
- Нет!!!  http://www.kolobok.us/smiles/artists/laie/LaieA_016.gif

0

76

#p96652,Лукомор написал(а):

Это не сильно тянет на определение...

Не... Я щас всем лентяям... Тыцните в картинку и читайте

http://sh.uploads.ru/2nABx.png

Отредактировано Шарпер (2019-01-15 16:54:51)

0

77

#p96658,Лукомор написал(а):

Там про Вычислительную Неразрешимость.

А речь шла не о неприводимости. Чмитайте сызнова

0

78

#p96659,Лукомор написал(а):

- Да, опровержение.

Бггг

0

79

#p96660,Шарпер написал(а):

ыцните в картинку и читайте

Одно не понятно:
Какое отношение текст под картинкой на странице 106,
имеет к 

#p96648,Шарпер написал(а):

определение неприводимости под картинкой на 108 стр.

0

80

#p96663,Лукомор написал(а):

Одно не понятно:
Какое отношение текст под картинкой на странице 106,
имеет к

Я тоже этого не знаю, а что? Через в карамель к не вмещаеццо?  http://www.kolobok.us/smiles/light_skin/sarcastic.gif

0

81

#p96664,Шарпер написал(а):

Я тоже этого не знаю, а что?

А то. что там была другая картинка, а потом она была

#p96660,Шарпер написал(а):

Отредактировано Шарпер (Сегодня 15:54:51)

0

82

#p96665,Лукомор написал(а):

А то. что там была другая картинка, а потом она была

Если Вы считаете, что эта информация делает меня умнее и дает ответ на животрепещущий вопрос, то  вы таки http://www.kolobok.us/smiles/big_standart/cool.gif  ошибаетесь

0

83

После того, как выяснилось, что в линейном варианте не один,
а сразу два различных замкнутых маршрута будут кратчайшими,

http://s7.uploads.ru/x8NXW.jpg

а третий возможный маршрут неизбежно будет длиннее тех двух,

http://sd.uploads.ru/k8nlV.jpg

я задумался, а почему так происходит...

У всех трех маршрутов есть нечто общее.

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

В крайних точках A и D каждый из них должен развернуться на 180 градусов,
так как дальше пути нет.

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

Следовательно, вся разница в длине их маршрутов заключается в первой части пути:
от A к D.

Рассмотрим эту часть пути более подробно.

Первый коммивояжер делает три последовательных шага AB-BC-CD,
двигаясь поступательно, всё время вперед.
Общая длина его пути равна сумме длин этих трех отрезков,
и равна обратному пути DA.
AB + BC + CD = DA.

Второй коммивояжер добирается до AD за два шага
AB + BD = AD,
и так же за два шага возвращается обратно:
DC + CA = DA.
Он также движется только вперед, разворачиваясь лишь в крайних точках A и D.
Поэтому пройденный путь у обоих одинаковый по возвращении в исходный пункт А.

Иное дело третий коммивояжер.
Он, также как и первый, попадает из А в D за три хода: AC + CB + BD,
разница в том, что он в каждом городе разворачивается на 180 градусов, и движется в противоположную сторону.
Поэтому пройденный им путь составляет
AC + CB + BD = (AB + BC) + BC + (BC + CD) = (AB + BC + CD) + 2 * BC=
= AD + 2 * BC > AD.

Отредактировано Лукомор (2019-01-15 20:37:34)

0

84

#p96666,Шарпер написал(а):

Если Вы считаете, что эта информация делает меня умнее

Боже упаси!
Куды же ещё-то умнее?!  http://www.kolobok.us/smiles/light_skin/shok.gif

0

85

#p96649,Шарпер написал(а):

Концевик, даже если он не обычная кнопка, а создание на основе технического зрения и нейронных сетях, никак не м.б. отнесен к центру управления в моем понимании.

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

#p96649,Шарпер написал(а):

Нет. Все способы оказались неверны. Последний, со спектрами, забраковали Вы. Или Вы нашли способ?

Это все технически нереализуемо или реализуемо с чудовищными затратами. Но сам предложенный способ отбраковки маршрутов, если известно кратчайшее полное время и точка выхода сигнала, вроде рабочий.

#p96649,Шарпер написал(а):

Наоборот, пустыня прирастает (Сибирью)

Не надо нами прирастать.

#p96649,Шарпер написал(а):

Обычный комп не умеет решать задачи физическим способом, тем более с распараллеливанием.

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

0

86

#p96667,Лукомор написал(а):

и равна обратному пути DA.
AB + BC + CD = DA.

а меня стращал
что мол в каждый город разрешается входить единожды (((
а когда он идет обратно он и В и С заходит повторно
и не надо про транзит

0

87

#p96669,Zagar написал(а):

здесь как раз должен быть единый центр, управляющий всей системой в целом.

Нет. Управление здесь "парадоксальное" (для всех, кроме механиков). Управляющим является луч, который в свою очередь зависит от настраиваемой "геометрии".

#p96669,Zagar написал(а):

Это все технически нереализуемо или реализуемо с чудовищными затратами

Ну вот...

#p96669,Zagar написал(а):

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

Виноват,но это не способ отбраковки. Наоборот, без него неворзможно найти ни точку выхода, ни время.

#p96669,Zagar написал(а):

Не надо нами прирастать.

Тогла пустыня придет к вам.

#p96669,Zagar написал(а):

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

А численное моделирование упрется в NP перечисление

0

88

#p96670,лукаш написал(а):

а меня стращал
что мол в каждый город разрешается входить единожды (((
а когда он идет обратно он и В и С заходит повторно
и не надо про транзит


Стращать вас таких не перестращать!

Я уже тут распин овыв ался,
и про проблему эту рассказывал,
и как я ее обошёл аккуратно.

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

Конечно, можно просто выкинуть эти крайние случаи,
и рассматривать интервал углов от 1  до 179 градусов,
в котором уже всё чинно - благородно, если бы не одно большое НО.
Даже два больших НО-НО.

Во-первых этот случай интересен сам по себе.
Там получается, что единственный кратчайший путь в окрестности конца интервала
остаётся кратчайшим и при этом предельном значении.
Но, именно в пределе когда вся ломаная линия уже выпрямилась, вдруг оказывается,
что для четырех городов сразу два маршрута, этот и еще один, становятся равными по длине.
Соответственно, для пяти городов их будет четыре - один и еще три.
Для шести городов -этот и еще четыре и три, всего восемь...
Для N городов - 2 в степени (N-3).

Во-вторых, могут быть еще случаи,
когда три или более городов окажутся  на одной прямой линии чисто случайно.
Я такой случай изучил сразу после линейного, и случая выпуклого многоугольника.
Здесь пока не выложил, но если доживу, обязательно выложу.
Для примера:
Пять городов, три из которых образуют треугольник,
а два других лежат на одной или двух сторонах этого треугольника.
При такой замысловатой конфигурации,
кратчайший замкнутый путь всё равно будет проходить по периметру треугольника.

Действительно, если города стоят на одной линии, то АC = АВ + ВС.
И действительно, в каждый город нужно  зайти и выйти не более одного раза.

Моё решение проблемы.
1. Коммивояжер передвигается в этом случае на вертолёте, и попадает из города А в город С минуя город В, но не заходя в него.
2. Альтернативный вариант - коммивояжер двигается пешком, на подводе, на автомобиле,
но вокруг каждого города есть объездная кольцевая дорога, по которой можно миновать город, не посетив его.
Даже лучше будет не так.
Трасса от А до D - прямая, безо всяких кольцевых, а города В и С чуточку в стороне от трассы, ещё лучше - прилегают к ней в одной точке.
А посещением города считать только если с трассы свернул, типа в центр города.
3. Или коммивояжер едет транзитным поездом из А в С, который проходит через В, но без остановки.

Так понятно?!

Отредактировано Лукомор (2019-01-16 01:59:39)

0

89

#p96671,Шарпер написал(а):

А численное моделирование упрется в NP перечисление

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

0

90

Зачем случай городов на одной линии рассматривать (мазохизм что ли ?)?. При любом N, решение всегда одно - шуруй через всю цепочку до конца, а потом возвращайся если хочешь. И все другие решения будут равны по длине или длиннее.

0


Вы здесь » Амальгама » Лукоморье 2.0 » Вторая тень