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

Амальгама

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

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


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


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

Сообщений 421 страница 450 из 692

421

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

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


Ты задачу сформулируй явно, а потом вангуй!

Отредактировано Лукомор (2018-09-10 10:21:17)

0

422

Не. До хрена паросочетаний проверять. Шило на мыло. Короче, начинает мне наскучивать. Завязывать пора.

0

423

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

Короче, начинает мне наскучивать. Завязывать пора.

Стоять, парнокопытное!  http://www.kolobok.us/smiles/light_skin/ok.gif
Так ни фига не пойдёт!!!  http://www.kolobok.us/smiles/standart/no2.gif
Я в это предприятие уже вложил солидный капитал - 
купил 48 листовую тетрадку в клеточку, и красиво подписал ее:
"Задача гипповояжера vs Задача коммипотама".  http://www.kolobok.us/smiles/light_skin/yahoo.gif
И вдруг автор идеи и главный коммерческий партнер
сваливает по кратчайшему маршруту коммивояжера в неизвестном направлении...  http://www.kolobok.us/smiles/light_skin/yahoo.gif
Так дела не делаются!
Будешь отвечать на все мои вопросы, коих овер-до-хрена!  http://www.kolobok.us/smiles/big_madhouse/ireful.gif

+1

424

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

Будешь отвечать на все мои вопросы, коих овер-до-хрена!

А куды я денусь?  http://www.kolobok.us/smiles/light_skin/scratch_one-s_head.gif

Увяз коготок стало быть?
Копать надо рядышком с наибольшими мусорными потерявшими по одной точке. Они легко находятся на TSP схеме для N-1 точки.
Сейчас думаю, что может дать путь через эти потерянные точки.

0

425

Метод конфискации принадлежности

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

Изловив искомые маршруты ,необходимо провести процедуру обратную конфискации – т.н принадлежание
Третье принадлежание производится вращением  отрезка  в произвольной плоскости для получения окружности радиуса R , содержащей все удачные маршруты . Величина радиуса подбирается путем последовательных приближений после первого (последнего) принадлежания
Второе принадлежание производится вращением окружности , содержащей все удачные маршруты вокруг оси проходящей через центр окружности и не лежащей в плоскости окружности,  под требуемым  углом .Легко представить эту фигуру напоминающую песочные часы. Центральная перетяжка делит фигуру на равные части ,содержащие равные количества одинаково удачных маршрутов , позволяющее отсечь  дублирующую половину  , и сократить обьем поиска.
Первое принадлежание – вращение полученной фигуры наподобие пращи , которое и выделит искомое из бесконечного количества в обьеме имеющем приемлемые размеры

+1

426

Я всё таки выскажусь по поводу относительной полезности незамкнутой и замкнутой задач коммивояжера.

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

о них снимали фильмы, и музыкальные видеоклипы, например, вот этот:

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

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

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

То-есть, коммивояжер, имеющий базу в Лондоне, задающий  вопрос true-математику, на предмет кратчайшего пути через основные европейские столицы,
рискует нарваться на ответ, типа Стамбул - Берлин - Лондон - Брюссель - Париж, где лондонская резиденция коммивояжера
мало того что оказывается где -то в середине маршрута, так еще и не учитывает необходимость возвращения на базу за новой партией товара,
а предполагает, скорее всего, одноразовое прохождения маршрута в стиле: "Увидеть Париж - и умереть".
Ответ абсолютно точный, и абсолютно бесполезный!
Кому же может быть полезна такая постановка задачи и такое решение ея?

Они могут быть полезны только "ковырятелям в носу" - эта героическая профессия с успехом заняла
опустевшую экологическую нишу после вымирания коммивояжеров, как биологического вида.
Ковырятели в носу никуда не путешествуют, они сидят дома, ковыряют в носу, глядя в потолок,
и вдруг, озаряются вопросом, а какой кратчайший маршрут можно проложить между основными европейскими столицами.
Полученный  ответ, типа Стамбул - Берлин - Лондон - Брюссель - Париж,
удовлетворяет ковыряющих в носу не только в Лондоне, Брюсселе и Берлине, но и в Жмеринке, и в каком-нибудь Урюпинске.
Профессия ковырятеля в носу экстерриториальна!  http://www.kolobok.us/smiles/light_skin/pleasantry.gif

Поэтому я называю незамкнутую задачу  - "задачей ковырятеля в носу"  http://www.kolobok.us/smiles/light_skin/yahoo.gif

Но, ОКей! Раз на эту задачу есть экспоненциальный спрос, будем решать ее за полиномиальное время.  http://www.kolobok.us/smiles/artists/laie/LaieA_016.gif

Задачи не выбирают, но всегда есть возможность выбрать способ решения!!!  http://www.kolobok.us/smiles/artists/laie/LaieA_032.gif

Отредактировано Лукомор (2018-09-10 13:26:32)

0

427

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

Легко представить эту фигуру напоминающую песочные часы.

Доктора в студию! Пациента теряем! Он себе непонятное представляет.

0

428

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

Метод конфискации принадлежности

Ай, молодец!  http://www.kolobok.us/smiles/light_skin/good.gif

0

429

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

после чего возвращался на базу N

0

430

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

Поэтому я называю незамкнутую задачу коммивояжера - "задачей ковырятеля в носу"  http://www.kolobok.us/smiles/light_skin/yahoo.gif

Нефиг думать = трясти надо.

0

431

О, да!  http://www.kolobok.us/smiles/light_skin/good.gif
Опять картинки только смотришь?
Ты бы еще понимал, о чем эта песня!!!
Она как раз в пользу замкнутых маршрутов!!!  http://www.kolobok.us/smiles/light_skin/yahoo.gif

Фрагмент текста:

I'm gonna take a trip to lonesome town
Gonna stay at heartbreak hotel
A fool such as I there never was


Перевод фрагмента:

Я уезжаю в город одиночества
Где остановлюсь в Отеле Разбитых Сердец
Такого дурака, как я, никогда еще не было!!!

  http://www.kolobok.us/smiles/light_skin/rofl.gif

Источник: https://www.amalgama-lab.com/songs/e/er … icket.html
© Лингво-лаборатория «Амальгама»: amalgama-lab.com/.

0

432

Да нет разницы замкнутый/разомкнутый. Добавь точку и объяви начальной.

0

433

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

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

Вы прослушали краткое содержание "метода ветвей и границ" - эвристического метода решения задачи коммивояжера.  http://www.kolobok.us/smiles/light_skin/good.gif

0

434

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

Да нет разницы замкнутый/разомкнутый. Добавь точку и объяви начальной.

Изменится матрица. Изменится решение, изменится ответ.
Не надо компромиссов, просто надо сказать:
"Я выбираю эту задачу, или вон ту", -  и решить ее,
а не растекаться мышью по коврику...

0

435

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

Такого дурака, как я, никогда еще не было!!!

Ну да, я такой.

0

436

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

Изменится матрица

Да решите сначала разомкнутый.

0

437

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

Нефиг думать = трясти надо.

(с) Паркинсон
Авторство указывать не забываем!  http://www.kolobok.us/smiles/light_skin/yahoo.gif

+1

438

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

Авторство указывать не забываем!  http://www.kolobok.us/smiles/light_skin/yahoo.gif

Ни фига. Группа автороф под ред. Альцгеймера

0

439

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

Да решите сначала разомкнутый.

Я же сказал: "ОКей".
Хотелось бы еще с условием определиться.
Насколько я понимаю, решать будем симметричную задачу,
то есть если от города А до города С 100 километров,
то и от города С до города А ровно столько же?

Это я к чему...
Ковырятели в носах придумали еще и асимметричную задачу коммивояжера,
когда от А до С есть дорога длиной 150 км, но от С до А есть еще прямая дорога длиной 100 км,
но она - с односторонним движением.
Таким образом, от А до С ровно 150 км, а от С до А всего 100 км.

Нет, я конечно понимаю, что нет разницы.
Проложи по две дороги разной длины вместо одной дороги между каждой парой городов, установи на всех дорогах знаки одностороннего движения,
добавь еще 0,5*N! путей, но всё ж таки, хотелось бы понять, какую задачу мы уже почти решили...

А то ведь будет, как в прошлый раз:
Задачу-то мы решили, и ответ сошелся, но, вот беда, ни одно условие под нее не подходит!  http://www.kolobok.us/smiles/light_skin/yahoo.gif

0

440

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

Ни фига. Группа автороф под ред. Альцгеймера

Да хрен редьки не слаще,
и всё же я попросил бы не путать:
благородного Паркинсона с вульгарным Альцгеймером!

0

441

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

Ты задачу сформулируй

Что за неспортивные идеи? Это ведь топик Шарпера. И всего 15 страница обсуждения. http://www.kolobok.us/smiles/sport/warning.gif

0

442

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

Это ведь топик Шарпера

Да. И я здесь занимаюсь мозговым компостом, чтоб пребывать в состоянии белопушистости и не реагировать на политику  http://www.kolobok.us/smiles/big_standart/timeout.gif

0

443

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

Что за неспортивные идеи?

http://www.kolobok.us/smiles/light_skin/blush.gif

0

444

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

решать будем симметричную задачу,
то есть если от города А до города С 100 километров,
то и от города С до города А ровно столько же?


КРУТО
не знал ,что при длине крокодила от носа до хвоста
равной длине крокодила от хвоста до носа
задача является симметричной !!!

0

445

а чтоб не флудить
вот и цитата из классики

Шпак. Как вам кажется наше местоположение, Тимофей Кондратьевич?

Лопуцьковский. Это прелесть! Когда я в 32-м году вояжировал из Чернигова в Воронеж, то, проезжая вашу деревню, любовался вашею природою и кое-что отметил в своем журнале.

Шпак. Вы ведете свой журнал?

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

Шпак. Это, должно быть, полезно?

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

Шпак. Вы только к Воронежу изволили путешествовать?

Лопуцьковский. Нет, я прежде проехал не к Воронежу, а в самый Воронеж, на Дворянскую улицу, а потом уже выехал из Воронежа обратно в Чернигов. Туда я сделал 645 верст и в обратный путь столько же точно.

0

446

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

КРУТО
не знал ,что при длине крокодила от носа до хвоста
равной длине крокодила от хвоста до носа
задача является симметричной !!!

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

0

447

какой же дурак по пузику меряет 7
ему же щикотно
или пукнет
или куснет за мягкое

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

это было сорок лет назад и до си в глазах стоит
как меряли высоту центрального блока на карусельном станке , контролерка была сверху , крутила микрометрический винт
а чтоб он крутился
леха садовский снизу поджимал ножку Шц СОВКОВОЙ ЛОПАТОЙ

0

448

http://tverdysplav.ru/wp-content/uploads/2014/09/ULG2.jpg
https://cs6.pikabu.ru/images/big_size_comm/2017-06_6/1498661676198659127.jpg

0

449

но это судя по всему трехметровый

а таких как ... сейчас не делают
секрет утерян

0

450

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

особенно, если крокодил только что покушал.

О! Проверяй крайний глюк.
Итак.
1 Ищем N раз максимальные запретные для одной пропущенной точки.
2 Ищем двоичным поиском N полных укороченных на 1 точку путей по максимальному времени, чтобы исключить запретные  на что потребуется N*log(N-1)!
3 Ищем кратчайший искомый подключая пропущенные точки к найденным путям N-1 способами, что потребует еще N(N-1) тактов
4 Ищем двоичным поиском искомый из N полных очищенных путей.
Где лажа?

На всякий случай это даст N+Nlog(N-1)!+N(N-1)+logN

Отредактировано Шарпер (2018-09-10 22:23:47)

0


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