#p96833,Шарпер написал(а):
лучше бы придумал алгоритм разаязывания петель в коммивояжере.
Что такое петли, и зачем их развязывать?!
Вторая тень
Сообщений 181 страница 210 из 1000
Поделиться1812019-01-19 06:36:50
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
Поделиться1822019-01-19 06:39:28
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96833,Шарпер написал(а):
лучше бы придумал алгоритм разаязывания петель в коммивояжере.
Сначала нужно придумать сам алгоритм решения задачи коммивояжера, а потом уже смотреть, какие там петли...
Поделиться1832019-01-19 06:41:03
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96790,лукаш написал(а):
А мужики то и не знают !!
Впрочем, весьма возможно, что ты прав! 
Поделиться1842019-01-19 06:50:09
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96783,лукаш написал(а):
возьмем наш родной четырехугольник
у него есть ПУТЬ и ИМЯ - периметр
выкинем узел
и чо будет ПУТЬ короче чем периметр *?
Вот как-то сразу не нашел опровергающий пример...
И потом не нашел...
Зато нашел ошибку в своих расчетах...
Теперь мне нужно проверить,
всегда ли, выкидыванием любой одной точки из N,
из кратчайшего маршрута через N точек получается кратчайший маршрут через N-1 точку.
Если да, то это просто здорово!
Поделиться1852019-01-19 06:57:37
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
Случай N=5 для моих исходных данных - я уже был готов выложить быстренько,
но нашел нестыковку, которая есть следствие ошибки, которую не нашел пока.
Поэтому начинаю выкладывать здесь и сейчас, поскольку нужно идти уже дальше,
но быстренько уже не получится, поскольку надо будет всё перепроверять
попутно
Случай N=5, поехали!
А, нет, стоп!
никуда покуда не поехали...
У меня еще не все углы расчитаны...
Отредактировано Лукомор (2019-01-19 08:41:49)
Поделиться1862019-01-19 07:01:26
- Дичинка
- Уважение: +1326
- Пол: Мужской
- Провел на форуме:
5 месяцев 17 дней - Последний визит:
Сегодня 15:05:29
#p96842,Лукомор написал(а):
Что такое петли, и зачем их развязывать?!
#p96843,Лукомор написал(а):
Сначала нужно придумать сам алгоритм решения задачи коммивояжера, а потом уже смотреть, какие там петли...
Ну вот способ ближвйшего соседа неплох, но петьли дает
https://habr.com/ru/post/329604/
А мой параллельный коммутацией коротких лучше, но тоже дает петли
Поделиться1872019-01-19 08:47:06
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96847,Шарпер написал(а):
А мой параллельный коммутацией коротких лучше, но тоже дает петли
Так и не понял, что такое эти "петли", и чем они тебе не угодили?!
Поделиться1882019-01-19 09:19:34
- Ветеран
- Уважение: +3174
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
петли - это наверно пересечения
хотя.....
Поделиться1892019-01-19 09:28:24
- Ветеран
- Откуда: Е-бург
- Уважение: +2158
- Пол: Мужской
- Возраст: 71 [1953-03-03]
- Провел на форуме:
4 месяца 3 дня - Последний визит:
Сегодня 15:22:48
Если пересечение не находится на точке, можно укоротить путь, сменив коммутацию точек в пересечении и направление прохода петли.
Поделиться1902019-01-19 10:07:13
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96868,SERGEY написал(а):
Если пересечение не находится на точке, можно укоротить путь, сменив коммутацию точек в пересечении и направление прохода петли.
Да, тут в этом конкретном примере напильником легко доработать...
Петля: (100,90), (85,20), (100,0), (85,50) перестановкой двух внутренних точек переводится в контур: (100,90), (100,0), (85,20), (85,50),
а петля из 12 звеньев от (100,90) до (50,75) перестановкой (100,90), (50,100), (10,85) в начале петли, и (25,70), (50,75) в конце петли.
Поделиться1912019-01-19 10:09:12
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96847,Шарпер написал(а):
А мой параллельный коммутацией коротких лучше, но тоже дает петли
Он таки "лучше", или "тоже дает петли"?
Поделиться1922019-01-19 11:09:53
- Дичинка
- Уважение: +1326
- Пол: Мужской
- Провел на форуме:
5 месяцев 17 дней - Последний визит:
Сегодня 15:05:29
#p96870,Лукомор написал(а):
Он таки "лучше", или "тоже дает петли"?
И то и это. Ближ. сосед вдобавок зависит от точки начала и петляет по-разному, а мой не зависит
Поделиться1932019-01-19 11:11:29
- Дичинка
- Уважение: +1326
- Пол: Мужской
- Провел на форуме:
5 месяцев 17 дней - Последний визит:
Сегодня 15:05:29
#p96868,SERGEY написал(а):
Если пересечение не находится на точке, можно укоротить путь, сменив коммутацию точек в пересечении и направление прохода петли.
А ты не знаешь будет пересечение или нет,пока сам себя не загонишь в тупик
Поделиться1942019-01-19 11:25:27
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96874,Шарпер написал(а):
А ты не знаешь будет пересечение или нет,пока сам себя не загонишь в тупик
Никто не запрещает методом последовательных приближений допиливать пошагово!
С каждой итерацией улучшая чего-нить...
Вот, например:
#p96869,Лукомор написал(а):
Петля: (100,90), (85,20), (100,0), (85,50) перестановкой двух внутренних точек
переводится в контур: (100,90), (100,0), (85,20), (85,50),
это действо (в правом нижнем углу твоего примера)
дает сокращение пути ажно на 3,791,
с 564,516 до 560,725, т.е. менее одного прОцента...
#p96869,Лукомор написал(а):
а петля из 12 звеньев от (100,90) до (50,75)
перестановкой (100,90), (50,100), (10,85) в начале петли,
и (25,70), (50,75) в конце петли.
Это уже более радикальная перестановка,
она дает выигрыш в 34,985, что, с учетом предыдущего улучшения,
дает кратчайший путь длиною в 525,740.
Общий выигрыш от развязывания двух петель составил без малого 7 процентов от исходного решения.
Отредактировано Лукомор (2019-01-19 12:07:29)
Поделиться1952019-01-19 12:03:51
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96874,Шарпер написал(а):
А ты не знаешь будет пересечение или нет,пока сам себя не загонишь в тупик
Это хороший алгоритм поимки льва в пустыне:
просто сидишь и ждешь, когда лев сам себя загонит в тупик. 
Поделиться1962019-01-19 12:06:34
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96873,Шарпер написал(а):
Ближ. сосед вдобавок зависит от точки начала и петляет по-разному, а мой не зависит
Казалось бы, причем тут точка начала,
если маршрут всё равно замкнутый,
а замкнутый маршрут остается кратчайшим,
с какой точки не начинай обход.
Поделиться1972019-01-19 14:00:32
- Дичинка
- Уважение: +1326
- Пол: Мужской
- Провел на форуме:
5 месяцев 17 дней - Последний визит:
Сегодня 15:05:29
#p96878,Лукомор написал(а):
Казалось бы, причем тут точка начала,
если маршрут всё равно замкнутый,
а замкнутый маршрут остается кратчайшим,
с какой точки не начинай обход.
А вот, оказывается, что способ ближ. соседа дает разные путанки в зависимости от начала
Поделиться1982019-01-19 14:30:50
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96883,Шарпер написал(а):
А вот, оказывается, что способ ближ. соседа дает разные путанки в зависимости от начала
Это крайне плохо!
То что пути разные, означает, просто, что они не кратчайшие.
Хуже всего то, что он может и вобще не дать кратчайшего пути, даже после перебора всех начальных точек...
Поделиться1992019-01-19 14:54:41
- Ветеран
- Уважение: +3174
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
#p96868,SERGEY написал(а):
Если пересечение не находится на точке, можно укоротить путь, сменив коммутацию точек в пересечении и направление прохода петли.
с кем ты разговариваешь ?
Поделиться2002019-01-19 14:58:49
- Ветеран
- Уважение: +3174
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
#p96878,Лукомор написал(а):
а замкнутый маршрут остается кратчайшим,
с какой точки не начинай обход.
по сурьезу ?
кстати
насчет возврата в ноль в условии имх ничего не сказано
или я что то пропустил
что
у него хаза там ?
Поделиться2012019-01-19 16:19:22
- Ветеран
- Уважение: +7405
- Пол: Мужской
- Провел на форуме:
3 месяца 13 дней - Последний визит:
Сегодня 14:45:12
#p96883,Шарпер написал(а):
А вот, оказывается, что способ ближ. соседа дает разные путанки в зависимости от начала
Это если из середки брать. А ты попробуй за начальный брать самый крайний, например, самый нижний/самый правый.
Поделиться2022019-01-19 16:22:43
- Дичинка
- Уважение: +1326
- Пол: Мужской
- Провел на форуме:
5 месяцев 17 дней - Последний визит:
Сегодня 15:05:29
#p96885,Лукомор написал(а):
То что пути разные, означает, просто, что они не кратчайшие.
естественно. Это ж эвристический способ, который не дает гарантии точного. Точный только с отсевом всех возможных запретных с получением кратчайшего разрешенного
Поделиться2032019-01-19 16:24:56
- Ветеран
- Уважение: +7405
- Пол: Мужской
- Провел на форуме:
3 месяца 13 дней - Последний визит:
Сегодня 14:45:12
И еще я бы метод ближайшего соседа дополнил бы предварительной таксономией, чтобы разбить все точки на группы.
И это даже для перебора выигрышно.
Типа, три группы по 10 точек каждая лучше, чем одна группа 30 точек. Имеется в виду, что перебор путей идет сначала между группами в целом, а уже потом внутри каждой группы между точками.
Это должно хорошо работать для существенно неравномерного распределения точек в пространстве. Типа, несколько городов, внутри каждого сколько-то точек - достаточно оптимизировать маршрут внутри каждого города, а потом маршруты между городами, не надо перебирать все варианты связей между всеми точками.
И, соответственно, будет неэффективно, если распределение в пространстве более-менее равномерное.
Поделиться2042019-01-19 16:25:11
- Дичинка
- Уважение: +1326
- Пол: Мужской
- Провел на форуме:
5 месяцев 17 дней - Последний визит:
Сегодня 15:05:29
#p96894,Zagar написал(а):
Это если из середки брать. А ты попробуй за начальный брать самый крайний, например, самый нижний/самый правый.
Из какой середки? Способ ближайшего зависит от точки начала. Мой способ параллельной коммутации не зависит от начальной точки, но путанку тоже дает.
Поделиться2052019-01-19 16:26:00
- Дичинка
- Уважение: +1326
- Пол: Мужской
- Провел на форуме:
5 месяцев 17 дней - Последний визит:
Сегодня 15:05:29
#p96896,Zagar написал(а):
разбить все точки на группы.
Есть такой, не помню названия
Поделиться2062019-01-19 16:59:27
- Ветеран
- Уважение: +5741
- Провел на форуме:
6 месяцев 2 дня - Последний визит:
Сегодня 08:53:25
#p96890,лукаш написал(а):
кстати
насчет возврата в ноль в условии имх ничего не сказано
или я что то пропустил
что
у него хаза там ?
Ты что-то пропустил...
Вот классическая формулировка:
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) —
одна из самых известных задач комбинаторной оптимизации,
заключающаяся в поиске самого выгодного маршрута,
проходящего через указанные города хотя бы по одному разу
с последующим возвратом в исходный город.
В сущности, этот классический вариант более всего соответствует смыслу работы реального коммивояжера.
Пробежавшись по всему маршруту,
распродав по пути товар,
он возвращается на базу,
в город, где у него типа склад.
Там он затаривается новой порцией товара,
и уходит на следующий цикл.
Существуют всякие еретические отступления от классического варианта задачи, например:
Замкнутый и незамкнутый варианты задачи[править | править код]
В замкнутом варианте задачи коммивояжёра требуется посетить все вершины графа, после чего вернуться в исходную вершину.
Незамкнутый вариант отличается от замкнутого тем, что в нём не требуется возвращаться в стартовую вершину.
Это, как: "увидеть Париж, и умереть".
Задача одноразового коммивояжера. 
Отредактировано Лукомор (2019-01-19 17:03:52)
Поделиться2072019-01-19 17:21:08
- Ветеран
- Уважение: +3174
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
#p96899,Лукомор написал(а):
он возвращается на базу,
я не возражаю
но раньше я это себе представлял как детский билиард где маленькая пушечка последовательно выстреливает шарики и они безвозвратно находят пути с разными очками
Поделиться2082019-01-19 18:19:51
- Ветеран
- Откуда: Е-бург
- Уважение: +2158
- Пол: Мужской
- Возраст: 71 [1953-03-03]
- Провел на форуме:
4 месяца 3 дня - Последний визит:
Сегодня 15:22:48
#p96889,лукаш написал(а):
с кем ты разговариваешь ?
А разве я обязан к кому-то конкретно обращаться ?
Поделиться2092019-01-19 18:44:10
- Ветеран
- Уважение: +3174
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
#p96903,SERGEY написал(а):
А разве я обязан к кому-то конкретно обращаться ?
че так серьезно
сразу ?
это обычное обращение,когда человек не может вникнуть в текст аффтора )
и представляет его голос как бы исходящий из зеркала
8
Кто-то вдруг произнес с выражением:
-- "Устремив свои мысли на высшее "Я", свободный от вожделения и
себялюбия, исцелившись от душевной горячки, сражайся, Арджуна!"
Я вздрогнул. Парень тоже вздрогнул.
-- "Бхагавад-гита"! -- сказал голос. -- Песнь третья, стих
тридцатый.
то же из этой серии
- какие же вы дураки оба !!
я вообще не могу понять о чем вы говорите
Поделиться2102019-01-19 18:46:41
- Ветеран
- Уважение: +3174
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
#p96899,Лукомор написал(а):
Незамкнутый вариант отличается от замкнутого тем, что в нём не требуется возвращаться в стартовую вершину.
о
блин!!
а я и не знал
что я говорю прозой (с)
