#p110969,лукаш написал(а):
А вы знаете, что безграмотных теперь в гроб не кладут, а ложат?
"Не дождётесь!" 
Другая тень
Сообщений 481 страница 510 из 1000
Поделиться4812019-09-13 00:40:29
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Поделиться4822019-09-13 07:29:48
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Итак, я, своим оригинальным методом "объединения точек", решил учебную задачу для 13 пунктов,
и получил длину кратчайшего пути L =393.845 км.
Теперь я буду условия этой задачи скармливать различным популярным онлайн-калькуляторам,
и сравнивать полученные результаты со своим результатом, чтобы оценить эффективность своего нового метода.
На первом месте в поисковом рейтинге гугля симпатичный сайт
https://math.semestr.ru/kom/index.php
На этом сайте умопомрачительное количество всевозможных онлайн-калькуляторов,
среди них онлайн-калькулятор для задачи коммивояжера, которую они предлагают решить двумя методами:
методом "ветвей и границ", и "венгерским" методом.
К сожалению, в этом сервисе нельзя задать исходные данные в виде координат пунктов, а только в виде матрицы расстояний.
При этом положительный момент заключается в том, что исходные данные можно вставлять прямо с экселевского листа,
одним кликом мышки. Максимальное количество городов, которое может быть задано на этом ресурсе - 14 городов.
Я ввел свои данные для 13 пунктов,
и получил подробное решение на 35 страницах, исписанных убористым вордовским почерком
Times New Roman двенадцатого размера.
Опуская подробности, в конце 35 страницы находим ответ:
" Длина маршрута равна F(Mk) = 397,680 "
Вот этот маршрут:
Отредактировано Лукомор (2019-09-13 07:55:26)
Поделиться4832019-09-13 08:09:05
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 03:47:27
#p110967,Лукомор написал(а):
Можно опуститься и до одной точки, но никакого практического смысла в этих действиях решительно нет.
Есть! Называется самовывоз
#p110967,Лукомор написал(а):
обратный переход от 4 точек к 8 точкам несколько сложен
Обратного перехода не существует, если не сохранять всю информацию об исходной позиции
#p110967,Лукомор написал(а):
Вот и все.
...
у меня получился
Ну и за сколько шагов решается 17! ?
Поделиться4842019-09-13 08:13:29
- Ветеран
- Откуда: Е-бург
- Уважение: +2216
- Пол: Мужской
- Возраст: 71 [1953-03-03]
- Провел на форуме:
4 месяца 5 дней - Последний визит:
Вчера 12:03:11
#p110967,Лукомор написал(а):
точками посредине между ними
А почему посередине ?
Поделиться4852019-09-13 08:34:26
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110994,Шарпер написал(а):
Есть! Называется самовывоз
Это обратная задача!
А задача коммивояжера - это самоввоз!
Поделиться4862019-09-13 08:37:45
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110994,Шарпер написал(а):
Обратного перехода не существует, если не сохранять всю информацию об исходной позиции
Вся информация об исходной позиции называется условием задачи.
Если мы решаем какую-то задачу, то у задачи безусловно существует условие.
Поделиться4872019-09-13 08:41:32
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110997,SERGEY написал(а):
А почему посередине ?
По уставу!
Я взял методику определения средней точки попадания из "Наставления по стрелковому делу", статья 64...
Поделиться4882019-09-13 08:47:08
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110994,Шарпер написал(а):
Обратного перехода не существует
Вот переход от 4 пунктов
к трем пунктам:
Вот обратный переход от трех пунктов к четырем:
Пальцем покажи, где чего не существует?
Поделиться4892019-09-13 08:51:19
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110994,Шарпер написал(а):
Ну и за сколько шагов решается 17! ?
1. От 17 к 13
2. От 13 к 10
3. От 10 к 9
4. От 9 к 8
5. От 8 к 4
6. От 4 к 8
7. От 8 к 9
8. От 9 к 10
9. От 10 к 13
10. От 13 к 17
Итого: за 10 шагов решается 17.
Поделиться4902019-09-13 09:05:57
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Итак, метод "объединения пунктов" заборол самый популярный онлайн-калькулятор,
работающий по методу "ветвей и границ" со счетом 393.845 : 397.680.
Правда тут есть нюанс.
Решение, полученное онлайн- калькулятором, имеет то, что я назвал скрытой петлей:
Так что этот метод также не умеет находить скрытые петли.
Я распутал эту петлю, и получил результат чуть лучше, но не дотягивающий до метода "объединения точек":
Что еще мне не понравилось в методе "ветвей и границ", это то, что в самом начале решения они пишут:
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,8 );(8,9);(9,10);(10,11);(11,12);(12,13);(13,1)
Иными словами, результат решения задачи будет зависеть от порядка следования пунктов в матрице расстояний,
и, если в решении методом "ближайшего соседа" приходится для 13 пунктов решать задачу 13 раз,
то здесь вариантов матрицы расстояний возможно всего 13 х 12 / 2 = 78 и задачу придется решить 78 раз, чтобы потом отобрать лучшее решение.
Я к такому пока не готов!
Дальше, на этом же интернет ресурсе есть еще решение задачи коммивояжера "венгерским" методом, но оно тупо не дает решения, а останавливается на 149 шаге... 
Отредактировано Лукомор (2019-09-13 09:28:44)
Поделиться4912019-09-13 09:39:45
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Следующий по рейтингу сайт, предлагающий решение задачи коммивояжера онлайн,
это персональный сайт преподавателя экономики Галяутдинова Руслана Рамилевича:
http://galyautdinov.ru/task/zadacha-kommivoyazhera
Задача коммивояжера на этом сайте решается все тем же методом "ветвей и границ", который я позже планирую разобрать здесь более подробно,
Максимальное количество городов - 15.
К сожалению, исходные данные здесь могут быть представлены только матрицей расстояний, которую нельзя скопировать из таблицы Excell,
а приходится вбивать вручную, и расстояния между городами должны быть только целыми числами.
Однако эти неудобства с лихвой компенсируются качеством работы программы, а результатом я был, буквально, поражен!
Общая длина найденного оптимального маршрута составляет 389,922 ед. дл.
Это решение лучше, чем решение методом "объединения точек"!
Шок!
Отредактировано Лукомор (2019-09-23 07:18:28)
Поделиться4922019-09-13 09:49:28
- Ветеран
- Откуда: Е-бург
- Уважение: +2216
- Пол: Мужской
- Возраст: 71 [1953-03-03]
- Провел на форуме:
4 месяца 5 дней - Последний визит:
Вчера 12:03:11
#p111003,Лукомор написал(а):
По уставу!
Поделиться4932019-09-13 14:38:24
- Ветеран
- Уважение: +3615
- Провел на форуме:
3 месяца 2 дня - Последний визит:
2024-11-11 14:12:38
#p111002,Лукомор написал(а):
Если мы решаем какую-то задачу, то у задачи безусловно существует условие.
*любуется витиеватостью*
Поделиться4942019-09-13 16:01:52
- Модератор
- Уважение: +14531
- Провел на форуме:
7 месяцев 13 дней - Последний визит:
Вчера 23:23:31
#p111002,Лукомор написал(а):
Если мы решаем какую-то задачу, то у задачи безусловно существует условие.
Не факт! По крайней мере, в случае с Шарпером я бы не стал так уж категорически это утверждать.
Поделиться4952019-09-13 16:03:02
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p111015,Ал написал(а):
любуется
Дык! 
Поделиться4962019-09-13 17:05:46
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 03:47:27
#p111025,DoctorLector написал(а):
Не факт! По крайней мере, в случае с Шарпером я бы не стал так уж категорически это утверждать.
Ну дык я же механик, а у нас у тех кого еще не испортили анал итическими методами 50% задач на тему пойди туда не знаю куда и принеси то, не знаю что. Ну или изобрети
Поделиться4972019-09-13 18:17:57
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p111030,Шарпер написал(а):
Ну дык я же механик
Механик-гинеколог, очевидно!
Поделиться4982019-09-13 18:20:38
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p111025,DoctorLector написал(а):
Не факт! По крайней мере, в случае с Шарпером
Я давно уже предлагал, еще на Сцылоге, ограничить,
и, после того, как задача решена, менять условие не более трех раз... 
Поделиться4992019-09-13 19:16:44
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 03:47:27
#p111038,Лукомор написал(а):
Механик-гинеколог
Посмотреть могу. А чо, есть проблемы во внутренних органах?
Поделиться5002019-09-13 19:30:01
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p111044,Шарпер написал(а):
А чо, есть проблемы во внутренних органах?
"Не дождетесь!" (с)
Нет проблем ни во внутренних, ни во внешних, ни в контролирующих...
Чист, аки стёклушко!
Поделиться5012019-09-13 20:53:44
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Итак, я был поражен в самое сердце...
Я был уверен,, что мой супер-пупер метод - самый супер-пупер метод из всех возможных,
но тут я внезапно получил еще один сокрушительный удар ниже клавиатуры.
Я решил не испытывать больше никаких онлайн-калькуляторов,
поскольку уже всё равно мой алгоритм так непринужденно повержен,
поэтому я вернулся к старому доброму методу "ближайшего соседа."
Уж тут-то, я был уверен, мой метод будет вне всякой конкуренции.
Отредактировано Лукомор (2019-09-14 06:43:36)
Поделиться5022019-09-13 22:26:19
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 03:47:27
#p111055,Лукомор написал(а):
Итак, я был поражен в самое сердце...
Экий ты ранимый... Бери пример с бегемотофф
Поделиться5032019-09-14 07:05:55
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Я испытал метод "ближайшего соседа" со всех 13 стартовых позиций, и вот что я получил в итоге:
На третьей позиции в рейтинге решений методом "ближайшего соседа" находится решение, полностью идентичное тому,
которое я получил своим оригинальным методом "объединения точек".
Таким образом, выяснилось, что мой метод не конкурентоспособен
уже по сравнению с методом "ближайшего соседа", не говоря уже о методе "ветвей и границ".
Ну и, значит, в топку его...
Конечно, его можно попробовать допилить до конкурентного состояния, но у меня есть уже более лучший метод и я приступаю здесь и сейчас к его изложению.
Еще только одно любопытное замечание. Алгоритм решения методом "объединения точек" относится к "жадным" алгоритмам, также как алгоритм "ближайшего соседа".
Именно поэтому решение методом "объединения точек" совпало с одним из решений методом "ближайшего соседа".
В то же время, ни одно из двух полученных решений методом "ветвей и границ", который не является "жадным", не совпадает, и не может совпасть,
ни с одним из решений методом ближайшего соседа.
Поделиться5042019-09-14 07:10:03
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p111059,Шарпер написал(а):
Экий ты ранимый... Бери пример с бегемотофф
Ни разу не ранимый, это фигура речи такая!
На самом деле, я изначально знал, что метод "объединения точек" не будет лучшим...
Я поставил на другую лошадку...
Поделиться5052019-09-14 19:58:50
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
Если кто-нибудь помнит, в начале весны я занимался рассмотрением в этой теме простейшей конфигурацией задачи коммивояжера для четырех пунктов.
Причем три внешних пункта образуют треугольник, а четвертый пункт находится внутри этого треугольника.
Если кто не помнит, можно начинать читать отсюда, буквально с третьей страницы этой темы.
С самого начала
Если кому лень читать все обсуждение, то вот конкретный результат:
Более конкретно
Там всего пол странички...
Поскольку по ссылкам всё равно никто не пойдет, я вкратце напомню.
Меня тогда интересовала чисто математическая сторона задачи в следующей постановке.
Если зафиксировать вершины треугольника,
то как найти точку внутри треугольника, такую,
что все три различных замкнутых маршрута
через эту точку и три вершины треугольника равны между собой?
Я нашел решение этой задачи, и выяснил,
что эта точка имеет специальное название - Equal Detоur Point ,
что она совпадает с центром "внутренней окружности Содди",
и что всё это впервые исследовал и нашел в 1985 году голландский математик Geert R. Veldkamp .
Отредактировано Лукомор (2019-09-14 20:19:44)
Поделиться5062019-09-14 23:49:56
- Ветеран
- Уважение: +3175
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
#p111138,Лукомор написал(а):
Если кто не помнит,
я ПОМНЮ
Поделиться5072019-09-15 07:34:03
- Ветеран
- Уважение: +3615
- Провел на форуме:
3 месяца 2 дня - Последний визит:
2024-11-11 14:12:38
#p111138,Лукомор написал(а):
Я нашел решение этой задачи, и выяснил,
что эта точка имеет специальное название - Equal Detоur Point ,
что она совпадает с центром "внутренней окружности Содди",
и что всё это впервые исследовал и нашел в 1985 году голландский математик Geert R. Veldkamp .
поэтому любой инженер-конструктор перед углубление в ТЗ должен произвести патентный поиск.
Поделиться5082019-09-15 08:38:05
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p111176,Ал написал(а):
поэтому любой инженер-конструктор перед углубление в ТЗ должен произвести патентный поиск.
Патентный поиск в гугле результатов не дал, поскольку я спрашивал всё подряд, но на русском ничего не нашлось.
Пока я не нашел самостоятельно формулу для этой точки в трилинейных координатах,
и не начал эту формулу сравнивать с каждой точкой по "Энциклопедии знаменитых точек треугольника",
ничего не получалось.
Когда же я нашел эту точку в энциклопедии (Х176),
и загуглил по ее английскому названию,
тогда гугль уже справился, и притащил примерно 5 миллионов результатов.
То есть, для поиска надо хотя бы примерно представлять, что ищешь.
Поделиться5092019-09-15 08:44:56
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 03:47:27
#p111181,Лукомор написал(а):
То есть, для поиска надо хотя бы примерно представлять, что ищешь.
Ага. Я ж говорил, в 90% случаев не знаешь что ищешь, ну или это ранее уже решенная задача и требуется ее лишь локализовать
Поделиться5102019-09-15 08:49:57
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 03:47:27
#p111176,Ал написал(а):
поэтому любой инженер-конструктор перед углубление в ТЗ должен произвести патентный поиск.
Вообще=то рекомендуется поискать известное и делательно типовое, а уж только потом изобретать и проверять патенты
