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

Амальгама

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

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


Вы здесь » Амальгама » Reductor Sapiens » Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое


Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое

Сообщений 241 страница 270 из 692

241

#p90571,Ал написал(а):

От так любимых докторами выжигателей геморроя

Я смотрю, у тебя очень непростой жизненный путь.

#p90570,Ал написал(а):

вот же ВВСы

Что есть, то есть.

0

242

Наврал, конечно. Испытание надо произвести N-1 раз для всех точек, а значит сигналов будет (N(N-1)^2)/2 , что кстати, равно кол-ву соединений в матричном варианте. Не знаю как для оптоволокна, а вот бешеное кол-во соединений, учитывая ко-во транзисторов в проце, так ни разу не препятствие- 2 миллиарда еще 10 лет назад было. А на каждом слое матричного представления N*(N-1) соединений по которым сигналы разведены временными задержками

0

243

Ну почему Лукомор-то так не сразу?

0

244

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

И столько же нужно сигналов, чтоб получить среди них кратчайший по времени.  (N-1)! получаются, если перечислять все варианты.

(N-1)! - это всего разрешенных маршрутов.
А всего, вместе с запрещенными:
http://sh.uploads.ru/Tmkw9.gif

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

Согласно алгоритму Черны, мы доводим число путей до кипения
http://sh.uploads.ru/Tmkw9.gif
добавив по вкусу к разрешенным маршрутам еще овердохрена запрещенных всяких.
Потом, при содействии Штерна, Герлаха и какой-то матери, мы, героическими усилиями,
эти запрещенные маршруты отсеиваем, и возвращаемся к нашим баранам  исходным разрешенным маршрутам,
и начинаем их просчитывать за экспоненциальное время, поскольку за полиномиальное не получится...  http://www.kolobok.us/smiles/standart/no2.gif

0

245

а если сразу взять и поделить ?!

0

246

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

Эта задача не может быть решена за полиномиальное время, она экспоненциальная по времени.

"Бессмыслица — искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос… "(с) К.Хунта

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

(N-1)! - это всего разрешенных маршрутов.
А всего, вместе с запрещенными:
http://sh.uploads.ru/Tmkw9.gif


А что это за навязчивая идея перечислять все варианты? У нас искомый путь единственный, причем первый по времени. А (N-1)!-1 более длинных, отсекаются безоговорочно и как только, так сразу.
И на 100% не уверен, но (N-1)(N-1) по-моему неверна - между слоями точек проходит N(N-1)/2 сигналов, так что, если смотреть по матрице то для N-1 слоя будет всего (N-1)*N(N-1)/2=(N(N-1)^2)/2.
Если ошибаюсь, поправьте, плз, хотя это и не принципиально, поскольку и запрещенные интересуют не асе, а только меньшие нашего искомого. угу. Самый длинный запрещенный должен быть меньше искомого. Это и есить критерий отсева. Для того, чтобы его осуществить, надо найти максимальное время прохождения запрещенного сигнала. Все они пропускают хотя бы одну вершину, поскольку нельзя попасть дважды в одну и ту же не пропустив какой-либо обязательной.

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

Итак, за N мы получили время прохождения максимального запрещенного пути. Следующий сразу за ним больший разрешенный и является искомым.  http://www.kolobok.us/smiles/light_skin/smoke.gif

Отредактировано Шарпер (2018-09-06 13:35:31)

0

247

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

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

Тогда анализ должен включать обязательное прохождение через город.
Предлагаю города делать из дерева, и следить, чтобы все дымились!

+1

248

#p90587,DoctorLector написал(а):

Я смотрю, у тебя очень непростой жизненный путь.

1. а у кого он простой?
2. Я просто наблюдательный. http://www.kolobok.us/smiles/big_standart/biggrin.gif

0

249

Лукомор
А, ошибаюсь (N-1)(N-1) это перечисление

0

250

#p90598,Ал написал(а):

Предлагаю города делать из дерева, и следить, чтобы все дымились!

Не обязательно!
Из дерева можно делать дороги, а города - из фанеры.

0

251

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

А (N-1)!-1 более длинных, отсекаются безоговорочно и как только, так сразу.

А как узнать, что они более длинные?!

0

252

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

И на 100% не уверен, но (N-1)(N-1) по-моему неверна

Советую еще раз перечитать статью Черны.
Эта формула сразу под рис. 1 на стр.202.

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

А что это за навязчивая идея перечислять все варианты?

Это тоже к Черны вопрос...

+1

253

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

Самый длинный запрещенный должен быть меньше искомого.

Я думаю, что он будет больше искомого...

0

254

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

А как узнать, что они более длинные?!

Так по времени же. Они все длиннее кратчайшего.

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

Советую еще раз перечитать статью Черны.
Эта формула сразу под рис. 1 на стр.202.

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

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

Это тоже к Черны вопрос...

Не-а. Это вопрос к постановке задачи. Зачинатель перечислил все варианты и все мучаются перебором.

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

Я думаю, что он будет больше искомого...

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

0

255

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

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

Это если все стороны треугольника - прямые линии.
А если одна сторона - серпантин, то она может быть гораздо длиннее суммы двух других.

0

256

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

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

То-есть статью Черны ты не читал, но осуждаешь?  http://www.kolobok.us/smiles/light_skin/facepalm.gif 
Вот смотри:  http://www.kolobok.us/smiles/artists/snoozer/look.gif
Разрешенный путь А→B→C→D→E→F→A состоит из шести переходов между шестью городами.
Для однообразия рисуем правильный шестиугольник, верхний город обозначаем А, далее по часовой стрелке.
Кстати, именно этот разрешенный путь будет кратчайшим для правильного шестиугольника.
Запрещенный путь A→B→C→D→B→E→A стоит из шести переходов между шестью городами.
Изъята точка F, соответственно, точка B посещается дважды.
И мне отсюда совсем не очевидно, что два изъятых участка: E →F и F→A,
будут длиннее вновь образовавшихся двух участков: D→B и B→E,
то-есть что две стороны правильного шестиугольника будут длиннее двух пусть малых, но таки диагоналей...

Отредактировано Лукомор (2018-09-06 16:53:24)

+1

257

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

А если одна сторона - серпантин, то она может быть гораздо длиннее суммы двух других.

Уговорил. Щас подумаем.  А для метрической задачи как Вам? Для которой треугольное неравенство выполняется?

0

258

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

Это если все стороны треугольника - прямые линии.

Метрический вариант задачи. Вот давай сначала для него.

0

259

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

Так по времени же. Они все длиннее кратчайшего.

Ну и нахрена нам знать время?
Мы и так знаем, что есть кратчайший путь, и есть все другие пути,
причем, интересная особенность, все другие пути длиннее кратчайшего!
Если пронормировать по времени кратчайшего пути, то время прохождения кратчайшего пути будет равно 1.
Соответственно, времена прохождения остальных путей >1.
Нам остался сущий пустяк: Решить труднорешаемую (NP-полную) TSP задачу, чтобы найти кратчайший путь.

0

260

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

И мне отсюда совсем не очевидно, что два изъятых участка: E →F и F→A,
будут длиннее вновь образовавшихся двух участков: D→B и B→E,
то-есть что две стороны правильного шестиугольника будут длиннее двух пусть малых, но таки диагоналей...

Для метрической задачи выполняется

0

261

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

Для метрической задачи выполняется

Карандашик возьми!
Нарисуй, посчитай, удивись!
Какого хрена сторона правильного шестиугольника длиннее его же диагонали?

0

262

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

Соответственно, времена прохождения остальных путей >1.

Вот именно. Так что первый же зарегистрированный выходной сигнал даст решение.

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

Нам остался сущий пустяк: Решить труднорешаемую (NP-полную) TSP задачу, чтобы найти кратчайший путь.

Для метрической задачи отсев запрещенных я тебе показал. Что не так?

0

263

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

Нарисуй, посчитай, удивись!

УшОл рисовать

0

264

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

Так что первый же зарегистрированный выходной сигнал даст решение.

И как будет выглядеть это решение?
T=1, не?

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

УшОл рисовать

Стоять!
Уже всё нарисовано.
http://sd.uploads.ru/gLAua.jpg

По логике белопушистого, красный маршрут справа короче чёрного маршрута слева,
из-за того, что справа изъят город F.
Нечёткая какая-то логика.

0

265

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

И как будет выглядеть это решение?
T=1, не?

С восстановлением пути повременим до решения проблемы отсева мусорных.

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

Стоять!
Уже всё нарисовано.


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

По логике белопушистого, красный маршрут

Это про гражданскую войну штоле?  http://www.kolobok.us/smiles/big_madhouse/wacko3.gif

0

266

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

Нечёткая какая-то логика.

Ты меня засомневал и мне придется теперь искать железобетонное решение.

0

267

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

Это про гражданскую войну штоле?

Это про апокалипсис!  http://www.kolobok.us/smiles/light_skin/shok.gif

0

268

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

Это про апокалипсис!

Щас задачу решим и вызовем.

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

0

269

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

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

Еще надо найти площади всех треугольников, объёмы всех тетраэдров, и гиперобъёмы всех симплексов, вплоть до единственного (n-1)-мерного, а также радиусы всех описанных гиперокружностей!  http://www.kolobok.us/smiles/light_skin/pleasantry.gif

0

270

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

Еще надо

Не надо.

0


Вы здесь » Амальгама » Reductor Sapiens » Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое