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

Амальгама

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

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


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


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

Сообщений 571 страница 600 из 868

571

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

Не ипите мне мозги, лучше помогите материально.

"Бог подаст!" (с)

0

572

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

Две! Отсев мусора и построение пути

У Черны это "2 в 1", и делается параллельно за одну часть.
Чудо-бозоны пробежали от источника S до детектора D, и путь построен и мусор отсеян.
Расчет окончен!

0

573

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

У Черны это "2 в 1", и делается параллельно за одну часть.
Чудо-бозоны пробежали от источника S до детектора D, и путь построен и мусор отсеян.

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

0

574

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

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

Ну всё ты правильно понял!
Там заморочка в том, что количество необходимых для решения задачи бозонов, и, следовательно,
энергия для их генерации, растут экспоненциально.
И если ты ещё не начал копать котлован под электростанцию для снабжения энергией генератора бозонов, то это сильно задержит поиск решения задачи коммивояжера. 
Статью Черны я не читал, но осуждаю!
Мне, почему-то, кажется, что задачу коммивояжера, ответ в которой, для заданных мною ранее условий  будет:
"Кратчайший маршрут : А - В - С - А"
и которая требует экспоненциального  времени решения,
Черны изначально подменил на задачу, ответ в которой будет:
"Кратчайший маршрут имеет длину 700 километров",
и которая изначально решается за полиномиальное время...

Отредактировано Лукомор (2018-09-14 19:36:23)

0

575

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

необходимых для решения задачи бозонов

иронически

взяли бы тахионы
уже б пивко баночное квасили
не теряя времени

0

576

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

Ну всё ты правильно понял!

Этого же не может быть! Бегемот не может ничего понять правильно. Это же в сапижалях!

0

577

сапижали, боин! Лано! Вы мне еще по ипале должны остались!

0

578

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

сапижали, боин!

Мьечно!

+1

579

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

сапижали, боин! Лано!

Этим заклинанием дух Черны не вызовешь!  http://www.kolobok.us/smiles/standart/agree.gif
Я пробовал.  http://www.kolobok.us/smiles/rpg/wizard.gif
Там какое-то слово пропущено...  http://www.kolobok.us/smiles/light_skin/scratch_one-s_head.gif

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

0

580

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

Вы мне еще по ипале должны остались

Зачем тебе четыре шпалы?! http://www.kolobok.us/smiles/standart/smile3.gif

0

581

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

Вы мне еще по ипале должны остались!

Если вернём долг, то нас привлекут за хулиганство.

+1

582

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

Зачем тебе четыре шпалы?!

на петлицу

0

583

Я тут задался вопросом,
почему не было никакой реакции на моё сообщение,
в котором я привел решение линейной задачи коммивояжера за линейное же время.
Любой реакции, критической, негативной, или просто невпопад...
После тяжелого, продолжительного раздумья, меня осенило.
Картинки!
В моём сообщении не было картинок...
Никто не станет читать многабукафф,
если эти многабукафф не разбавлены картинками до гомеопатической дозы.
Выкладываю здесь приложение к моему фундаментальному труду с картинками, табличками и формулками.
Сначала я повторяю свою судьбоносную работу, поскольку найти ее среди спама уже затруднительно даже ее автору.
И сразу же прикладываю обесчанное приложение.
Пользуйтесь, я не жадный!

+1

584

"Решение линейной задачи коммивояжера за линейное время".
(с) Лукомор
     независимый исследователь.

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

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

Таким образом,
я НЕ решаю:
-замкнутый вариант симметричной геометрической задачи коммивояжера;
-замкнутый вариант асимметричной геометрической задачи коммивояжера;
-незамкнутый вариант асимметричной геометрической задачи коммивояжера;
Я также не решаю никакой из вариантов обобщенной задачи коммивояжера.

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

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

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

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

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

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

0

585

Приложение №1, к "Решению линейной задачи коммивояжера за линейное время".

Задача №1.
Условие задачи представлено в виде графа и матрицы расстояний, соответствующих графу.
http://s5.uploads.ru/0BIZj.jpg

Решение руками:
Минимальный кратчайший путь будет пролегать между крайними, наиболее удаленными городами.

Кратчайший незамкнутый путь:
1. A – B – C – D – E – F       Длина:  100 + 120 + 140 + 160 + 180 = 700
2. F – E – D – C – B – A                         Длина:  180 + 160 + 140 + 120 + 100 = 700

Кратчайший замкнутый путь:
    A – B – C – D – E – F – A        Длина:  100 + 120 + 140 + 160 + 180 + 700 = 1400

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

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

0

586

Для проверки решения данные из условия задачи были внесены
в матрицу расстояний онлайн калькулятора для задачи коммивояжера:
https://math.semestr.ru/kom/index.php

http://s9.uploads.ru/BsT81.jpg

В результате работы калькулятора был получен результат:

В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(5,6), (6,1), (1,2), (2,3), (3,4), (4,5),
Длина маршрута равна F(Mk) = 1400
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера


Калькулятор считает только замкнутые маршруты.
Чтобы получить кратчайший незамкнутый маршрут, нужно исключить самый длинный отрезок,
в данном случае (6,1)=FA, получится незамкнутый маршрут  (1,2), (2,3), (3,4), (4,5), (5,6) длиной 700.
Результаты расчета совпали (только вручную быстрее...  http://www.kolobok.us/smiles/standart/smile3.gif  ).

Отредактировано Лукомор (2018-09-16 11:03:50)

0

587

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

на петлицу

На петлицу, это будет не по заслугам, а если ещё куда, то...

0

588

И не лень ведь было!

0

589

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

И не лень ведь было!

Вот!
Наконец-то!!

Хоть какая-то, пусть кривая, пусть кособокая, но, ведь, критика!!!
Теперь есть, наконец-то, на что отвечать, возражать, полемизировать, наконец!
Я так этого ждал!

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

Ведь на примере усовершенствования алгоритма Черны из этой темы, мы прекрасно видим ответ на  вопрос из предыдущей темы:" Как человек изобретает?"

Ответ простой:"Человек надувает щёки!".
А что из этого выйдет, изобретение, или громкий пук,
зависит лишь от разности давлений на обоих выходах...

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

Иное дело - Лукомор!
Подобно Архимеду из Сиракуз,
взяв в руки рычаг, Лукомор будет искать точку опоры,
а погрузившись в ванну, начнет искать Эврику!
Но он никогда не будет искать кратчайший путь,
если требуется найти кратчайший путь.
Ему не лень решить 10 или 30 задач коммивояжера с рзличными начальными условиями.
Но он знает, что "истина где-то рядом", и он будет искть где-то рядом.
Он посчитает периметры, площади треугольников, радиусы вписанных и описанных окружностей.
И всё это ради того, чтобы найти некоторые общие закономерности,
некоторые инварианты, которые не зависят от изменения некоторых условий задачи.

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

Но.
"Не так прост Лукомор,
как Лукомор не прост!"
(с) Лукомор.

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

Для начала я слегка повернул каждый следующий участок маршрута коммивояжера, на немного, градусов на 30.
Задаа перестала быть линейной, она стала полноправной метрической задачей коммивояжера.
Но кратчайший маршрут, который в линейной задаче находился тривиально,
этот кратчайший маршрут остался прежним!
В следующем своём сообщении я продемонстрирую эту задачу и ее решение.

+1

590

Да, ладно. Инженерные методы отличаются нечеткой постановкой задачи, чтоб она не мешалапоиску способа. Когда способ найден он проверяется на частичеую применимость, ибо 905 их отсекаются на этом этапе. Так что строгие постановки только потеря времени. Вот, например, про вариант подключения изъятой точки, как конечной я и не писал, поскольку способ отсеялся сразу по необходимости знать промежуточные запретные, что в общем приводит к ограничению по перекрытию сигналов, что невозможно. Т.е. пока Вы там формализовалт задачу. я проверил пару дюжин способов.

0

591

И в общем-то все. Стоп на этом. Наскучило. До следующего осенения.

0

592

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

почему не было никакой реакции на моё сообщение,

там нечего обсуждать
все понятно

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

0

593

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

меня осенило.
Картинки!
В моём сообщении не было картинок...
Никто не станет читать многабукафф,


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

+1

594

лично я
отметаю линейность
и не потому
что прям
ключевым словом в названии задачи ЗАДАЧА КОММИВОЯЖЕРА
является не слово ЗАДАЧА
на красный плащ которой мы мечемся с чувством положительного содрогания
а слово КОММИВОЯЖЕРА -

нуу
как бы вам обьяснить

путь может быть коротким или длинным
или его не может быть вообще

идеальный вариант
кратчайший
не вставая с места Сыт, пьян и нос в табаке

Это как задача водолаза
задача мясника
задача боксера

+1

595

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

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

А я нашел только  один способ, работающий на специфическом и очень ограниченном множестве задач коммивояжера,
и теперь этот способ буду "дорабатывать наgильником", а область применения - расширять,
благо от линейного времени до полиномиального
есть куда отступать выравнивать линию фронта...  http://www.kolobok.us/smiles/standart/smile3.gif

0

596

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

меня осенило.

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

До следующего осенения.

А осень еще не кончилась.

+2

597

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

лично я
отметаю линейность

Это потому, что ты сейчас находишься в уютном трёхмерном мире, и эпоха средневековья уже прошла, в основном, повсеместно.

А был бы ты сейчас в линейном одномерном мире,
и объяснялся бы перед Линейной Инквизицией,
что вовсе не отметаешь линейность,
что тебя неправильно поняли,
и что не надо тут этих линейных пыток... http://www.kolobok.us/smiles/light_skin/scare.gif

0

598

Приложение №2. к "Решению линейной задачи коммивояжера за линейное время".

Задача №2.

В рассматриваемой в этом приложении задаче, сохранены расстояния между соседними городами,
а именно:
AB=100, BC=120, CD=140, DE=160, EF=180.
Однако каждый последующий отрезок повернут по часовой стрелке, относительно предыдущего.
Таким образом углы:
ABC=BCD=CDE=DEF=150 (градусов).
Соответственно все расстояния между городами, за исключением соседних городов,
будут меньше чем в линейной задачи, и вычисляются из соответствующих треугольников.
После такого преобразования задача перестает быть линейной, и становится обычной задачей коммивояжера.

Условие задачи (Граф и матрица расстояний).

http://s9.uploads.ru/xisDT.jpg

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

Кратчайшие замкнутые маршруты:

A - B - C - D - E - F - A       
Длина пути = 100 + 120 + 140 + 160 + 180 + 530,06 = 1230,06

A - F - E - D - C - B - A
Длина пути = 530.06 + 180 + 160 + 140 + 120 + 100 = 1230,06

Кратчайшие незамкнутые маршруты:

A - B - C - D - E - F       
Длина пути = 100 + 120 + 140 + 160 + 180 = 700
A - F - E - D - C - B - A
Длина пути = 180 + 160 + 140 + 120 + 100 = 700

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

Решение задачи методом ветвей и границ с помощью онлайн-сервиса "Задача коммивояжера".

Матрица расстояний:

http://s5.uploads.ru/yfsuJ.jpg

Результат расчета:

В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(6,5), (5,4), (4,3), (3,2), (2,1), (1,6),
Длина маршрута равна F(Mk) = 1230.06
Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера


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

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

0

599

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

Приложение №2. к "Решению

Доктор! А Вам не кажется, что кроме белопушистого у нас появился белогорячий?  http://www.kolobok.us/smiles/light_skin/shok.gif

0

600

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

А был бы ты сейчас в линейном одномерном мире,

а был бы я в одномерном мире
а был бы я одномерным барыгой
а было б два пункта А и В

ВОТ И ВСЁ  ((

0


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