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

Амальгама

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

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


Вы здесь » Амальгама » Лукоморье 2.0 » Другая тень


Другая тень

Сообщений 61 страница 90 из 264

61

Итак, суть вопроса заключается в следующем.

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

Тогда я решил рассмотреть простейшие графы с небольшим количеством пунктов.
Для трех пунктов, как ни крути, получится один цикл, точнее два цикла по формуле N!=2!=2,
но эти два цикла будут отличаться только направлением обхода - \по и \против часовой стрелки.
В общем случае получается треугольник, а кратчайший, он же длиннейший, путь будет равен периметру треугольника.
http://s5.uploads.ru/t/RqUOy.jpg

Это отправная точка нашего исследования...

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

Иными словами, мы нарисовали на плоскости треугольник.
Теперь нам хотелось бы раскрасить всю плоскость в три цвета так,
чтобы любая точка, лежащая в секторе своего цвета, давала бы тот же кратчайший путь,
что и любая другая точка из этого сектора.
Для выпуклых четырехугольников ответ уже известен apriori: кратчайшим путем будет периметр четырехугольника.
http://s5.uploads.ru/t/it7mu.jpg
Я зафиксировал на плоскости три пункта А,В,С.
Стороны получившегося треугольника я продолжил за вершины вовне треугольника.
Теперь, если я выбираю любую точку в красной области, например P' , то получится трапеция AСВP' с диагоналями  AB и CP'.
Кратчайшим путем в этом графе с четырьмя вершинами будет его периметр.
Аналогично, любая точка в зеленой области даст трапецию АВСР'',
с кратчайшим путем по ее периметру, и любая точка в синей области даст четырехугольник ВАСР''',
и кратчайший путь будет также по периметру его.
У нас остались четыре не закрашенных области, одна внутри треугольника АВС,
и три вне его, но между продолжениями сторон треугольника
С ними дело будет обстоять несколько сложнее.
Но об этом я расскажу уже завтра, то-есть сегодня...  http://www.kolobok.us/smiles/standart/smile3.gif

Отредактировано Лукомор (2019-03-18 01:19:00)

0

62

Небольшое отступление...

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

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

Граф распадается таким образом на замкнутый цикл из четырех отрезков,
и два отрезка, по которым маршрут не проходит.
Для выпуклого графа с четырьмя вершинами, такого, как на рисунке:
http://sg.uploads.ru/t/kql5I.jpg
,- три возможных цикла показаны на соответствующих рисунках.
Циклы выделены разным цветом, отрезки, через которые цикл не проходит - черные.
1. http://s7.uploads.ru/RWkT2.jpg
2. http://sg.uploads.ru/Gpaud.jpg
3. http://sg.uploads.ru/IxFit.jpg

Из рисунков видно,
что только один из трех циклов не будет иметь самопересечений типа "петля Шарпера",
ясно что этот маршрут и будет кратчайшим.

Что еще можно выудить из этих рисунков?
Любые два маршрута, выбранные из трех возможных, будут иметь, из четырех отрезков: два одинаковых отрезка, и два разных.
Ясно, что шесть отрезков - ребер полного графа, попарно входят или не входят в каждый из трех маршрутов.
Я их изображу каждую пару своим цветом, это будут:
пара диагоналей, и две пары противолежащих сторон.
http://sh.uploads.ru/Dez9N.jpg
Эти пары неразлучны: нельзя построить такой замкнутый маршрут,
в который бы один отрезок из пары входил, а второй не входил.
Или маршрут проходит через оба отрезка из пары, или через оба не проходит.
Достаточно найти самую длинную, в сумме, пару отрезков и выкинуть ее.
Оставшийся маршрут из четырех отрезков будет всегда замкнутым, и всегда кратчайшим. Для выпуклого четырехугольника эта пара - пара диагоналей.
Она всегда будет длиннее любой пары противолежащих сторон.
Поэтому, для выпуклого четырехугольника, кратчайшим маршрутом будет всегда его периметр.
Что еще интересно, отрезки из пары никогда не следуют друг за другом,
они будут либо четными, либо нечетными номерами при обходе сторон.

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

Отредактировано Лукомор (2019-03-18 11:44:00)

+1

63

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

петля Шарпера

http://www.kolobok.us/smiles/big_madhouse/ireful.gif  http://www.kolobok.us/smiles/light_skin/dash1.gif  http://www.kolobok.us/smiles/big_madhouse/wacko3.gif  http://www.kolobok.us/smiles/light_skin/hang1.gif

0

64

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

петля Шарпера

http://www.kolobok.us/smiles/artists/laie/LaieA_016.gif
Я там существенно дополнил текст крайнего сообщения.  http://www.kolobok.us/smiles/madhouse/mail1.gif
Дочитай, тебе понравится!  http://www.kolobok.us/smiles/light_skin/good.gif

0

65

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

типа "петля Шарпера"

Вот ведь... пройдут годы, народ, строя логистические схемы межпланетной доставки пиццы, будет знать, что такое "Петля Шарпера", а нас всех и не вспомнят! http://www.kolobok.us/smiles/big_standart/biggrin.gif
*в сторону*
Блин, а он ещё и гневится... мда-а-а...

0

66

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

0

67

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

только один из трех циклов не будет иметь самопересечений типа "петля Шарпера"

Аплодирую! А планируется построение других конструкций? Ну, там, "табурет Шарпера", например?

0

68

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

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

Это ты его как андролог гинеколога спрашиваешь?

0

69

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

строя логистические схемы межпланетной доставки пиццы,

Не, не пиццы, нет!  http://www.kolobok.us/smiles/standart/agree.gif
Схемы доставки лицензионных картриджей для 3-D принтеров!!!  http://www.kolobok.us/smiles/light_skin/yahoo.gif
А там уж пластмассовую кашу кто себе чего захочет, то и распечатает из файла, можно и пиццу...
А можно и водочки холодненькой, сразу в пластиковом одноразовом стаканчике,
и солёненький огурчик, уже порезанный на тоненькие дольки, с маленьким кусочком хлебушка Borodinskij™ ®.
/судорожно сглатывает слюну...  http://www.kolobok.us/smiles/standart/smile3.gif

Отредактировано Лукомор (2019-03-18 21:10:43)

+2

70

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

будет знать, что такое "Петля Шарпера"

Да, они не будут повторять этих ошибок...
они будут делать свои...  http://www.kolobok.us/smiles/light_skin/secret.gif

+1

71

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

а нас всех и не вспомнят!

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

Не вспомнят одного лишь Лукомора... http://www.kolobok.us/smiles/standart/no2.gif
Так часто бывает...  http://www.kolobok.us/smiles/artists/laie/LaieA_034.gif

Отредактировано Лукомор (2019-03-18 21:21:21)

0

72

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

что делать с вогнуто-выпуклыми?

Это как раз самое интересное! http://www.kolobok.us/smiles/light_skin/good.gif

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

Там просто будет многобукв, и хотелось бы выложить если не одним постом (не получится никак!),
то хотя бы за короткий промежуток времени между первым и крайним постами...
может быть сегодня-на-завтра как раз подходящий момент:
"...ночь будет лунная!" ( © Веня Д'ркин "Старая мельница")  http://www.kolobok.us/smiles/standart/smile3.gif

0

73

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

А планируется построение других конструкций?

Ответил выше Алу...
Конструкций сколько угодно, пора уже конвейер запускать...  http://www.kolobok.us/smiles/standart/smile3.gif

0

74

х

Отредактировано Лукомор (2019-03-19 08:42:19)

0

75

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

Не вспомнят одного лишь Лукомора...
Так часто бывает...

Поэтому ты посты оттуда вложением выкладываешь? http://www.kolobok.us/smiles/light_skin/rofl.gif

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

Это ты его как андролог гинеколога спрашиваешь?

Да! http://www.kolobok.us/smiles/big_standart/biggrin.gif

0

76

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

У меня уже столько материала нарыто, что хватит увековечить не только тех, кто сейчас с нами здесь, на планете Амальгама,
но и всех, кто здесь побывал ранее, и половину завсегдатаев Сцылога, и даже с Мембраны кое-кого... 
Не вспомнят одного лишь Лукомора...

Ну давай назовем это "тайники Лукомора".

0

77

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

У меня уже столько материала нарыто

Кто бы сомневался. Даже анекдот такой есть: "Дедушка, зачем ты клумбу машинным маслом поливаешь, цветочки же повянут?".

+1

78

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

Поэтому ты посты оттуда вложением выкладываешь?

Если честно, спросонья из этой фразы НХНП: откуда-оттуда посты, каким-таким вложением, и почему это должно быть смешно?   http://www.kolobok.us/smiles/light_skin/dash1.gif 
Старею стремительно, наверное...  http://www.kolobok.us/smiles/artists/laie/LaieA_034.gif

0

79

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

Ну давай назовем это "тайники Лукомора".

Нет уж, пусть остается просто "это", для загадочности...  http://www.kolobok.us/smiles/standart/smile3.gif

0

80

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

Даже анекдот такой есть: "Дедушка, зачем ты клумбу машинным маслом поливаешь, цветочки же повянут?".

... с бородой...  http://www.kolobok.us/smiles/standart/smile3.gif

0

81

Я вчера обломался продолжать тему, и теперь, поскольку под рисунком уже набежали комменты,
я его перетаскиваю ниже сюда.
http://s9.uploads.ru/t/2Rvz0.jpg
из рисунка видно, что нам осталось рассмотреть четыре не закрашенных области,
при попадании в которые, подвижная четвертая точка не дает выпуклого четырехугольника.
Если точка (Р) находится внутри треугольника АВС, то у нас получится вот такая конструкция:
http://s3.uploads.ru/VCopb.jpg
Если же точка окажется вовне треугольника, но в не закрашенной  области
(между продолжениями двух сторон из одной вершины), то картинка будет та же самая, только внутрь нового треугольника,
образованного двумя вершинами и четвертой точкой, попадет одна из вершин исходного треугольника АВС.
Например:
http://s5.uploads.ru/NmJfT.jpg
, - если точка P'' оказалась снаружи треугольника, но внутри  продолжения сторон АС и ВС,
то вершина С окажется внутри треугольника АВР'', это будет все тот же треугольник с точкой внутри.
Поэтому я начну рассмотрение с первого варианта: Точка Р внутри треугольника АВС, остальные - аналогичны...

Отредактировано Лукомор (2019-03-19 09:16:14)

0

82

С этого момента будем работать только с вот этой элегантной конструкцией:
http://s3.uploads.ru/VCopb.jpg
На этом графе также можно проложить три различных маршрута:
1. http://sh.uploads.ru/NkSdF.jpg
2. http://s5.uploads.ru/P9mxo.jpg
3. http://s8.uploads.ru/rGqE1.jpg
В отличие от выпуклого четырехугольника здесь нет "пары диагоналей",
которая априорно длиннее любой "пары противолежащих сторон".
Конечно, можно (и нужно!), разбить шесть отрезков на три пары,
которые совместно либо входят, либо не входят в каждый из трех маршрутов.
Вот эти три пары:
- АВ & CP;
- АС & ВP;
- ВС & АP;
Разбиение единственно, первая пара не входит в третий маршрут,
вторая - во второй, и первая - в третий.

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

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

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

Отредактировано Лукомор (2019-03-19 10:09:38)

0

83

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

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

Это центр описанной окружности

0

84

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

Это центр описанной окружности

Это не правильный ответ!  http://www.kolobok.us/smiles/artists/laie/LaieA_013.gif

Отредактировано Лукомор (2019-03-19 12:11:00)

0

85

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

Это не правильный ответ!  http://www.kolobok.us/smiles/artists/laie/LaieA_013.gif

Тогда я не понял, что за три линии пересекающиеся в точке при равенстве длин. Это и есть центр описанной.

0

86

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

Тогда я не понял, что за три линии пересекающиеся в точке при равенстве длин. Это и есть центр описанной.

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

А, между тем, американский математик Кларк Кимберлинг (Clark Kimberling) составил и поддерживает в актуальном состоянии "Энциклопедию центров треугольника",
в которой собраны сведения обо всех, хотя бы чем-то, примечательных точках, связанных с треугольником.  http://www.kolobok.us/smiles/light_skin/good.gif
Таковых, на сегодняшний день, насчитывается уже 31 722 (тридцать одна тысяча семьсот двадцать две)!!!  http://www.kolobok.us/smiles/light_skin/shok.gif
Интересно, что пару таких замечательных точек открыл, как говорят, император Франции Наполеон I Бонапарт!  http://www.kolobok.us/smiles/artists/laie/LaieA_032.gif
----------------
К тому же я нигде не говорил, что эти три линии - прямые!
Скорее наоборот - это три коники, к каковым, как известно относятся окружность, эллипс, парабола и гипербола...

0

87

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

Тогда я не понял, что за три линии пересекающиеся в точке при равенстве длин.

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

0

88

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

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

Итак ,  я начал с простых вещей...
Я взял правильный, или равносторонний треугольник.
Это единственный треугольник, для которого справедливо утверждение Шарпера о центре описанной окружности.
просто потому, что для такого треугольника в этой точке пересекаются и высоты и медианы и биссектрисы, и много чего еще.
http://s9.uploads.ru/kgKcF.jpg

Отредактировано Лукомор (2019-03-19 16:16:54)

0

89

это смотря еще какая медиана
а то и в серёдку не попадет !!!

0

90

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

Если честно, спросонья из этой фразы НХНП: откуда-оттуда посты, каким-таким вложением,

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

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

и почему это должно быть смешно?

А кто сказал, что это должно быть смешно? Плакать, блин, хочется!

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

Это центр описанной окружности

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

Это не правильный ответ!

Ты просто не знаешь способности бегемот, он из любого центра всю округу обо опишет.

0


Вы здесь » Амальгама » Лукоморье 2.0 » Другая тень