Амальгама |
Привет, Гость! Войдите или зарегистрируйтесь.
Вы здесь » Амальгама » Reductor Sapiens » Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое
Ага.
Значица так - искомый кратчайший будет больше наибольшенго запрещенного с пропущенной точкой за исключением случаев, когда при этой точке не выполняется неравенство треугольника.
Ты задачу сформулируй явно, а потом вангуй!
Отредактировано Лукомор (2018-09-10 10:21:17)
Не. До хрена паросочетаний проверять. Шило на мыло. Короче, начинает мне наскучивать. Завязывать пора.
Короче, начинает мне наскучивать. Завязывать пора.
Стоять, парнокопытное! 
Так ни фига не пойдёт!!! 
Я в это предприятие уже вложил солидный капитал -
купил 48 листовую тетрадку в клеточку, и красиво подписал ее:
"Задача гипповояжера vs Задача коммипотама". 
И вдруг автор идеи и главный коммерческий партнер
сваливает по кратчайшему маршруту коммивояжера в неизвестном направлении...
Так дела не делаются!
Будешь отвечать на все мои вопросы, коих овер-до-хрена! 
Будешь отвечать на все мои вопросы, коих овер-до-хрена!
А куды я денусь? 
Увяз коготок стало быть?
Копать надо рядышком с наибольшими мусорными потерявшими по одной точке. Они легко находятся на TSP схеме для N-1 точки.
Сейчас думаю, что может дать путь через эти потерянные точки.
Метод конфискации принадлежности
Первая конфискация – проэцирование бесконечного мира с конечным количеством удачных маршрутов на плоскость дает бесконечную плоскость с проэкциями удачных маршрутов.
Вторая конфискация - проэцирование бесконечной плоскости с конечным количеством удачных маршрутов на прямую дает бесконечную прямую с проэкциями удачных маршрутов.
Третья конфискация - проэцирование бесконечной прямой с конечным количеством удачных маршрутов в отрезок , однозначно содержащий все удачные маршруты
Изловив искомые маршруты ,необходимо провести процедуру обратную конфискации – т.н принадлежание
Третье принадлежание производится вращением отрезка в произвольной плоскости для получения окружности радиуса R , содержащей все удачные маршруты . Величина радиуса подбирается путем последовательных приближений после первого (последнего) принадлежания
Второе принадлежание производится вращением окружности , содержащей все удачные маршруты вокруг оси проходящей через центр окружности и не лежащей в плоскости окружности, под требуемым углом .Легко представить эту фигуру напоминающую песочные часы. Центральная перетяжка делит фигуру на равные части ,содержащие равные количества одинаково удачных маршрутов , позволяющее отсечь дублирующую половину , и сократить обьем поиска.
Первое принадлежание – вращение полученной фигуры наподобие пращи , которое и выделит искомое из бесконечного количества в обьеме имеющем приемлемые размеры
Я всё таки выскажусь по поводу относительной полезности незамкнутой и замкнутой задач коммивояжера.
Задача коммивояжера родилась из практических наблюдений за тяжелой судьбой коммивояжеров,
коих, с развитием интернета, видимо уже не осталось на земном шаре.
А когда-то эти ископаемые густо населяли поверхность Земли, о них слагали песни,
например, известные "Коробейники":
о них снимали фильмы, и музыкальные видеоклипы, например, вот этот:
Сущность работы коммивояжера заключалась в том, чтобы имея склад в уездном городе N,
он брал партию товара, и объезжал близлежащие и не близлежащие населенные пункты,
где умело втюхивал свой нехитрый ассортимент местным аборигенам,
после чего возвращался на базу N за следующей партией товара для нового цикла...
Такому жизненному циклу ископаемого, безусловно соответствует замкнутый вариант задачи коммивояжера, где маршрут начинается и заканчивается в N.
Этот алгоритм безусловно полезен любому коммивояжеру, желающему сэкономить пару центов на каждом цикле,
который в данном случае называется гамильтоновским, в честь великого математика, почетного коммивояжера, лучшего друга всех коммивояжеров.
Вчера я с интересом узнал, что существует незамкнутая задача коммивояжера,
которая предполагает посещение N пунктов ровно по одному разу без возврата на базу,
и с легкой степнью офигения понял, что именно эту задачу решает наш бегемот-ученый.
Суть ее, чтобы найти кратчайший незамкнутый маршрут, неважно, где начинающийся,
и неважно где заканчивающийся, важно, что это два любых разных города.
То-есть, коммивояжер, имеющий базу в Лондоне, задающий вопрос true-математику, на предмет кратчайшего пути через основные европейские столицы,
рискует нарваться на ответ, типа Стамбул - Берлин - Лондон - Брюссель - Париж, где лондонская резиденция коммивояжера
мало того что оказывается где -то в середине маршрута, так еще и не учитывает необходимость возвращения на базу за новой партией товара,
а предполагает, скорее всего, одноразовое прохождения маршрута в стиле: "Увидеть Париж - и умереть".
Ответ абсолютно точный, и абсолютно бесполезный!
Кому же может быть полезна такая постановка задачи и такое решение ея?
Они могут быть полезны только "ковырятелям в носу" - эта героическая профессия с успехом заняла
опустевшую экологическую нишу после вымирания коммивояжеров, как биологического вида.
Ковырятели в носу никуда не путешествуют, они сидят дома, ковыряют в носу, глядя в потолок,
и вдруг, озаряются вопросом, а какой кратчайший маршрут можно проложить между основными европейскими столицами.
Полученный ответ, типа Стамбул - Берлин - Лондон - Брюссель - Париж,
удовлетворяет ковыряющих в носу не только в Лондоне, Брюсселе и Берлине, но и в Жмеринке, и в каком-нибудь Урюпинске.
Профессия ковырятеля в носу экстерриториальна! 
Поэтому я называю незамкнутую задачу - "задачей ковырятеля в носу"
Но, ОКей! Раз на эту задачу есть экспоненциальный спрос, будем решать ее за полиномиальное время. 
Задачи не выбирают, но всегда есть возможность выбрать способ решения!!! 
Отредактировано Лукомор (2018-09-10 13:26:32)
Легко представить эту фигуру напоминающую песочные часы.
Доктора в студию! Пациента теряем! Он себе непонятное представляет.
Метод конфискации принадлежности
Ай, молодец! 
после чего возвращался на базу N
Поэтому я называю незамкнутую задачу коммивояжера - "задачей ковырятеля в носу"
Нефиг думать = трясти надо.
О, да!
Опять картинки только смотришь?
Ты бы еще понимал, о чем эта песня!!!
Она как раз в пользу замкнутых маршрутов!!!
Фрагмент текста:
I'm gonna take a trip to lonesome town
Gonna stay at heartbreak hotel
A fool such as I there never was
Перевод фрагмента:
Я уезжаю в город одиночества
Где остановлюсь в Отеле Разбитых Сердец
Такого дурака, как я, никогда еще не было!!!
Источник: https://www.amalgama-lab.com/songs/e/er … icket.html
© Лингво-лаборатория «Амальгама»: wwwamalgama-lab.com/.
Да нет разницы замкнутый/разомкнутый. Добавь точку и объяви начальной.
Легко представить эту фигуру напоминающую песочные часы. Центральная перетяжка делит фигуру на равные части ,содержащие равные количества одинаково удачных маршрутов , позволяющее отсечь дублирующую половину , и сократить обьем поиска.
Первое принадлежание – вращение полученной фигуры наподобие пращи , которое и выделит искомое из бесконечного количества в обьеме имеющем приемлемые размеры
Вы прослушали краткое содержание "метода ветвей и границ" - эвристического метода решения задачи коммивояжера.
Да нет разницы замкнутый/разомкнутый. Добавь точку и объяви начальной.
Изменится матрица. Изменится решение, изменится ответ.
Не надо компромиссов, просто надо сказать:
"Я выбираю эту задачу, или вон ту", - и решить ее,
а не растекаться мышью по коврику...
Такого дурака, как я, никогда еще не было!!!
Ну да, я такой.
Изменится матрица
Да решите сначала разомкнутый.
Нефиг думать = трясти надо.
(с) Паркинсон
Авторство указывать не забываем!
Авторство указывать не забываем!
Ни фига. Группа автороф под ред. Альцгеймера
Да решите сначала разомкнутый.
Я же сказал: "ОКей".
Хотелось бы еще с условием определиться.
Насколько я понимаю, решать будем симметричную задачу,
то есть если от города А до города С 100 километров,
то и от города С до города А ровно столько же?
Это я к чему...
Ковырятели в носах придумали еще и асимметричную задачу коммивояжера,
когда от А до С есть дорога длиной 150 км, но от С до А есть еще прямая дорога длиной 100 км,
но она - с односторонним движением.
Таким образом, от А до С ровно 150 км, а от С до А всего 100 км.
Нет, я конечно понимаю, что нет разницы.
Проложи по две дороги разной длины вместо одной дороги между каждой парой городов, установи на всех дорогах знаки одностороннего движения,
добавь еще 0,5*N! путей, но всё ж таки, хотелось бы понять, какую задачу мы уже почти решили...
А то ведь будет, как в прошлый раз:
Задачу-то мы решили, и ответ сошелся, но, вот беда, ни одно условие под нее не подходит!
Ни фига. Группа автороф под ред. Альцгеймера
Да хрен редьки не слаще,
и всё же я попросил бы не путать:
благородного Паркинсона с вульгарным Альцгеймером!
Ты задачу сформулируй
Что за неспортивные идеи? Это ведь топик Шарпера. И всего 15 страница обсуждения. 
Это ведь топик Шарпера
Да. И я здесь занимаюсь мозговым компостом, чтоб пребывать в состоянии белопушистости и не реагировать на политику 
Что за неспортивные идеи?
решать будем симметричную задачу,
то есть если от города А до города С 100 километров,
то и от города С до города А ровно столько же?
КРУТО
не знал ,что при длине крокодила от носа до хвоста
равной длине крокодила от хвоста до носа
задача является симметричной !!!
а чтоб не флудить
вот и цитата из классики
Шпак. Как вам кажется наше местоположение, Тимофей Кондратьевич?
Лопуцьковский. Это прелесть! Когда я в 32-м году вояжировал из Чернигова в Воронеж, то, проезжая вашу деревню, любовался вашею природою и кое-что отметил в своем журнале.
Шпак. Вы ведете свой журнал?
Лопуцьковский. Ежедневно и со всею подробностью. Записываю, где был, что видел, слышал, с кем что говорил и даже мыслил.
Шпак. Это, должно быть, полезно?
Лопуцьковский. Прелесть, как полезно! Вообразите, что во время моего вояжа в Воронеж, на обратном пути в Чернигов, я, заглянув в мой журнал, наперед знал, где буду ночевать и что найду к ужину.
Шпак. Вы только к Воронежу изволили путешествовать?
Лопуцьковский. Нет, я прежде проехал не к Воронежу, а в самый Воронеж, на Дворянскую улицу, а потом уже выехал из Воронежа обратно в Чернигов. Туда я сделал 645 верст и в обратный путь столько же точно.
КРУТО
не знал ,что при длине крокодила от носа до хвоста
равной длине крокодила от хвоста до носа
задача является симметричной !!!
С крокодилом так не получится...
От носа до хвоста по хребту всяко меньше, чем от хвоста до носа по пузику,
особенно, если крокодил только что покушал.
Асимметричная задача...
Симметричной может быть только мумия крокодила, специально изготовленная...
какой же дурак по пузику меряет 7
ему же щикотно
или пукнет
или куснет за мягкое
мерный крокодил, изходя из метрологической парадигмы , плосок и упруг , как пятиметровый штангенциркуль
бляя
как вспомню , так вздрогну
это было сорок лет назад и до си в глазах стоит
как меряли высоту центрального блока на карусельном станке , контролерка была сверху , крутила микрометрический винт
а чтоб он крутился
леха садовский снизу поджимал ножку Шц СОВКОВОЙ ЛОПАТОЙ
но это судя по всему трехметровый
а таких как ... сейчас не делают
секрет утерян
особенно, если крокодил только что покушал.
О! Проверяй крайний глюк.
Итак.
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)
Вы здесь » Амальгама » Reductor Sapiens » Эврика, эврикой, а что с ней делать в моем возрасте? Гиппопотическое
