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

Амальгама

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

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


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


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

Сообщений 451 страница 480 из 868

451

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

Проверяй крайний глюк.

НХНП!
повторяю меленно и разборчиво вопрос:

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

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

0

452

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

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

Я решаю задачу в постановке Черны и не забиваю себе башню. Потом разберемся.

0

453

Лукомор
Что непонятного? Задача - избавиться от мусора и вычленить кратчайший искомый. Ты огорчил меня тем, что пропуск точки может дать мусорный путь длиннее искомого. Я нашел другой вариант отсева.
Сначала ищем максимальные мусорные, а потом для них полные пути, по которым проходит максимальный мусорный. Ну и т.д.

0

454

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

0

455

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

Я решаю задачу в постановке Черны и не забиваю себе башню

О!
Замкнутую, значит...
А только что решал другую, незамкнутую.
Так все-таки, между двумя любыми конкретными точками один путь, или два разных?

0

456

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

И вдруг автор идеи и главный коммерческий партнер
сваливает по кратчайшему маршруту коммивояжера в неизвестном направлении...  
Так дела не делаются!

А я ведь с самого начала нихром и электроток предлагал! Вот послушал бы...

0

457

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

А только что решал другую, незамкнутую.

Уф. Ты мне, тупому механику можешь объяснить в чем разница? Ну вот возьми свой шестиугольник с картинки и разомкни в любой точке.

0

458

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

Уф. Ты мне, тупому механику можешь объяснить в чем разница? Ну вот возьми свой шестиугольник с картинки и разомкни в любой точке.

Подожди, потом, всё потом!
Вот чуток эйфория схлынет!
Я только что нашел решение задачи коммивояжера, не то что за полиномиальное, но за линейное время...
Проверил на онлайн-калькуляторе, оказывается есть такой для задачи коммивояжера, считает до 14 городов.
Результат совпал с моим решением.
Щас пойду водички хлебну, и распишу всё подробно...
И теперь я думаю: "Поторопился я 48-листовую тетрадку покупать,
от этой задачки можно было 12-листовой отбиться! "  http://www.kolobok.us/smiles/light_skin/yahoo.gif

Отредактировано Лукомор (2018-09-11 05:31:12)

0

459

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

0

460

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

0

461

Эпиграф:
   "Итак-а!" (с) Столбняк

Вступление:
   Сразу оговорюсь, я решаю незамкнутый вариант
симметричной геометрической задачи коммивояжера.
Это означает, что маршрут коммивояжера начинается в одном городе,
проходит все остальные города ровно по одному разу,
и заканчивается в каком-нибудь другом городе,
без возврата в город, где маршрут начался.
При этом, расстояния "туда" и "обратно" между любой парой городов
равны между собой, а дороги между всеми городами являются прямыми линиями.
Следует отметить, что геометрическая задача коммивояжера с евклидовой метрикой
всегда будет одновременно и метрической,
поскольку в этом случае относмтельно длин всех рёбер выполняется неравенство треугольника.
В своем решении я нигде не использую ни манхэттенскую (квартальную метрику)
ни максимальную метрику.
Таким образом,
я НЕ решаю:
-замкнутый вариант симметричной геометрической задачи коммивояжера;
-замкнутый вариант асимметричной геометрической задачи коммивояжера;
-незамкнутый вариант асимметричной геометрической задачи коммивояжера;
Я также не решаю никакой из вариантов обобщенной задачи коммивояжера.

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

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

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

Мы назвали этот вариант задачи коммивояжера - Линейной Задачей Коммивояжера.
Решениями Линейной Задачи Коммивояжера являются два кратчайших маршрута,
проложенных между двумя наиболее удаленными друг от друга городами,
таким образом, что все другие города находятся между этими двумя городами.
В этом варианте задачи коммивояжера длина кратчайшего маршрута
будет равна арифметической сумме расстояний между соседними городами.
Таким образом, для Линейной Задачи Коммивояжера с количеством городов равным N,
общее количество арифметических операций сложения, необходимых для нахождения
кратчайшего пути равно (N-1) и линейно растет с ростом N.
Для нахождения самого кратчайшего маршрута необходимо выполнить только сортировку расстояний от каждого города до остальных городов.
Два города с максимальным расстоянием между ними будут начальным и конечным на кратчайшем маршруте, остальные будут иметь наименьшие расстояния до соседних с ними городов вдоль всего маршрута.

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

Отредактировано Лукомор (2018-09-11 07:32:57)

0

462

#p90980,SERGEY написал(а):

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

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

+1

463

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

Да что вы к этому коммивояжеру прицепились?

Нельзя отдавать это на откуп не профессионалам в области динамического программирования,
к тому же, и коммивояжеров уже не осталось,
по крайней мере такой профессии нет в "Едином классификаторе профессий" http://www.kolobok.us/smiles/artists/laie/LaieA_016.gif

Да и ставка приличная: на кону 1 (один) миллион долларов от НИИ Клея,
за решение задачи тысячелетия "P=NP".  http://www.kolobok.us/smiles/standart/snooks.gif

В конце-концов, "а пофлудить?"(c)  http://www.kolobok.us/smiles/light_skin/yahoo.gif

0

464

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

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

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

+1

465

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

А я ведь с самого начала нихром и электроток предлагал

"Это же не наш метод!"(с) к/ф "Операция Ы"  http://www.kolobok.us/smiles/standart/smile3.gif

Отредактировано Лукомор (2018-09-11 07:56:42)

0

466

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

Эпиграф:

И не лень хногей маяться? Проверь вариант

0

467

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

Каким условиям должен удовлетворять граф

Да много условий. Я вот как-то так представлял, но возможны и другие варианты.
http://puzzleit.ru/files/puzzles/96/96349/_original.jpg

0

468

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

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

Алгоритм составления плана эвакуации: подожгите здание и зарисуйте, откуда полезут люди.

+1

469

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

от НИИ Клея

С инструкцией: нюхайте в пакете, пока не увидите миллион долларов. Хорошая премия...
http://s00.yaplakal.com/pics/pics_original/4/7/0/10546074.jpg

0

470

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

нюхайте в пакете

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

Мы нашли все максимальные разрешенные пути для TSP с пропущенными точками, что соответствует нахождению всех максимальных мусорных без пропуска точек.
Дальше мы находим все варианты полных укороченных на одну точку путей для этих максимальных.
А теперь к каждому варианту подключаем пропущенные точки и смотрим что получится.
а должно получиться, что искомый будет длиннее укороченного варианта, если выполняется правили треугольника, и МЕНЬШЕ, если оно не выполняется и обзод точки дает более длинный путь.
Вариантов всего два. Ну, а общее время я считал выше.

0

471

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

лучше бы подключились к анализу

Вы на часы смотрели? Сказано же: приём с 8 до 9 утра!
http://mpsdoc.com/wp-content/uploads/2017/11/55cb68c0d2ff4.jpg

0

472

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

И не лень хногей маяться?

В топку твой вариант!!!

Я задачу коммивояжера не просто за полиномиальное время,
я ее за линейное время решил, это абсолютный мировой рекорд,
который никто и никогда не побьёт!!!

Всего (N-1) арифметическое сложение!
Да и сложения не нужны.

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

0

473

Лукомор
Я всерьез прошу проверить

0

474

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

Я всерьез прошу проверить

А чего там проверять?!
Ошибка сразу бросается в глаза!
Ошибка заключается в том, что вся осмысленная часть информации находится в твоей голове, а ключ к тому шифру, который в том твоем сообщении,
которое ты просишь проверить - утерян.
Орфографию можно проверить, да.
К орфографии особых претензий нет, особенно если взять поправку на коэффициент отношения размера бегемотьего пальца к размеру клавиши на клавиатуре...
Где-то 97 попаданий из ста - приличный результат.

0

475

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

вся осмысленная часть информации находится в твоей голове

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

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

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

Отредактировано Шарпер (2018-09-11 15:21:37)

0

476

Напомню, что максимальный путь строится от конечной точки полученной по максимальнлму времени, т.е. по заднему фронту светового сигнала

0

477

DoctorLector
Обращаюсь к Вам. Вам что -то непонятно в тексте? Спрашиваю, для того, чтоб довести до полной ясности

0

478

Да, и еще один момент.

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

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


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

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

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

Я ввожу здесь новое понятие, хотя, возможно, в "большой" математике такое понятие и соответствующее ему обозначение существуют.

Я называю "РАНГОМ" маршрута (или пути) на графе с N вершинами,
которые отождествляются с городами,
количество последовательных участков R (0<R<N+1) из которых этот маршрут состоит.
Всю эту чушь я обозначаю большой латинской буквой K с верхним и нижним индексами,
http://s3.uploads.ru/TJpVy.gif

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

Отредактировано Лукомор (2018-09-11 15:40:52)

0

479

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

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

Не понял, каким механизмом она решается. Все перечислительные задачи упрутся в факториал, имхо, так что разъясняйте

Но, в перерыве проверьте предложенный вариант, а то я начинаю думать, что задача таки решена.  http://www.kolobok.us/smiles/big_madhouse/wacko3.gif

0

480

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

Напомню, что максимальный путь строится от конечной точки полученной по максимальнлму времени, т.е. по заднему фронту светового сигнала

Максимальный запретный, надо полагать?
Или максимальный разрешенный?

Чёрт! Этот квест:"Пойми бегемота!" никогда не закончится!

На всякий случай, в плане повышения эрудиции:
В армии задний фронт называется тыл, а при движении - арьергард!

0


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