#p112634,Ал написал(а):
там два варианта, в зависимости от чётности проходов.
Там целое море вариантов...
Другая тень
Сообщений 781 страница 810 из 1000
Поделиться7812019-10-03 14:19:07
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
Поделиться7822019-10-03 14:37:06
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112634,Ал написал(а):
для внутренних сначала нужно кратчайшим путём выйти на ближнюю внешнюю, потом
Почему снова кратчайшим?
Он может быть и не кратчайшим, вот пример:
Поделиться7832019-10-03 14:40:56
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112640,DoctorLector написал(а):
Я так чувствую, что вы скоро накликаете Мать Русского Квадратостроения в полный рост.
Ну, это разве что если спиритический сеанс провести... 
Отредактировано Лукомор (2019-10-04 04:27:26)
Поделиться7842019-10-03 17:52:15
- Ветеран
- Уважение: +3615
- Провел на форуме:
3 месяца 2 дня - Последний визит:
2024-11-11 14:12:38
#p112655,Лукомор написал(а):
Есть один нюанс: при запуске с разных пунктов дает разные результаты, поэтому нужно
запускать его с каждого пункта, и выбирать самый короткий из получившихся "кратчайших" путей.
Если дополнить его алгоритмом "пути домой" или "дальней точки" этот нюанс снимается.
Поделиться7852019-10-04 04:25:17
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112674,Ал написал(а):
Если дополнить его алгоритмом "пути домой" или "дальней точки" этот нюанс снимается.
Мне ничего не известно об этих двух безусловно замечательных алгоритмах, кроме их названий. 
Не уверен, что их реализация сколько-нибудь проще, чем реализация двух эпохальных алгоритмов Шарпера: "полного перебора "спецвычислителем"",
и "обратного хода бинарным поиском".
--------------------------------------------------
Кстати, я внимательно рассмотрел сбоку свой алгоритм "объединения точек",
и пришел к выводу, что он реализует, правда на свой лад,
идею Шарпера о полном переборе "спецвычислителем".
Это забавно, но я здесь ни капли не шучу.
Я имею в виду, буквально, следующее.
НА первом этапе работы своего метола я нахожу все пути со всех точек одновременно,
правда только на глубину одного хода.
При этом сразу же проявляются контуры кратчайшего маршрута -
это отрезки, которые являются кратчайшими "в обе стороны",
то-есть они будут кратчайшим из обоих пунктов, являющихся концами этих отрезков.
Завершается первый этап заменой таких отрезков представляющими их медианными пунктами.
На втором этапе какой либо из этих медианных пунктов может вновь оказаться концом отрезка, "кратчайшего в обе стороны".
И мы получаем уже цепочку из двух отрезков, с учетом найденного на первом этапе.
Так в задачке на 17 пунктов получились 4 таких цепочки: одна длиной в 6 отрезков, две длиной 4 отрезка, и один - из трех отрезков.
Теперь, обратным ходом "бинарным поиском",
мы находим направление включения каждого из найденных отрезков в кратчайший маршрут
в прямом или инверсном направлении.
Все, как у Шарпера, только более рационально, и без фанатизьма...
Отредактировано Лукомор (2019-10-04 04:26:52)
Поделиться7862019-10-04 06:09:49
- Модератор
- Уважение: +14532
- Провел на форуме:
7 месяцев 13 дней - Последний визит:
Вчера 23:37:52
#p112697,Лукомор написал(а):
Все, как у Шарпера, только более рационально, и без фанатизьма
Есть сильное подозрение, что этими словами можно характеризовать вообще любой практически применимый алгоритм, существующий в этом мире, и, главное, работающий.
Поделиться7872019-10-04 07:21:38
- Ветеран
- Уважение: +3615
- Провел на форуме:
3 месяца 2 дня - Последний визит:
2024-11-11 14:12:38
#p112697,Лукомор написал(а):
Мне ничего не известно об этих двух безусловно замечательных алгоритмах, кроме их названий.
Ну, сами названия говорящие...
#p112697,Лукомор написал(а):
Не уверен, что их реализация сколько-нибудь проще, чем реализация двух эпохальных алгоритмов Шарпера: "полного перебора "спецвычислителем"",
и "обратного хода бинарным поиском".
что вполне может быть.
#p112697,Лукомор написал(а):
НА первом этапе работы своего метола я нахожу все пути со всех точек одновременно,
правда только на глубину одного хода.
Это у тебя просто точек мало.
#p112697,Лукомор написал(а):
Все, как у Шарпера, только более рационально, и без фанатизьма...
Поделиться7882019-10-04 10:46:16
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112705,Ал написал(а):
Это у тебя просто точек мало.
У меня вообще речь не идет о количестве точек...
Оно не принципиально.
Дело только в их взаимном расположении.
Если точка В самая ближайшая к точке А, а все другие находятся от точки А на более далеких расстояниях,
и одновременно точка А - самая ближайшая к точке В, то отрезок АВ я называю "кратчайшим в обе стороны".
И "очевидно"(с), что этот отрезок войдет во все 17 маршрутов, построенных методом "ближайшего соседа".
Найдя такой отрезок, я его временно убираю,
а вместо него подставляю точку, которая есть средина отрезка,
и начинаю рассматривать задачу уже с меньшим количеством точек в условии...
Отредактировано Лукомор (2019-10-04 10:50:34)
Поделиться7892019-10-04 10:49:32
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
Кстати, у меня две хороших новости:
одна - персонально для Шарпера,
а вторая - вообще ни у кого не вызовет интереса! 
С которой начать?!
Поделиться7902019-10-04 17:12:24
- Ветеран
- Уважение: +3615
- Провел на форуме:
3 месяца 2 дня - Последний визит:
2024-11-11 14:12:38
#p112720,Лукомор написал(а):
У меня вообще речь не идет о количестве точек...
Оно не принципиально.
Это шутка была, а если принципиально, то количество путей от количества точек растёт экспоненциально.
#p112720,Лукомор написал(а):
Найдя такой отрезок, я его временно убираю,
а вместо него подставляю точку, которая есть средина отрезка,
и начинаю рассматривать задачу уже с меньшим количеством точек в условии...
А у меня складывается алгоритм.
1. самая дальняя точка. по дороге до дальней точке затрагиваются "попутные" точки.
2. попутные точки, это точки расположенные в радиусе (?) и имеющий вектор от 0 до 90 (?) градусов.
3. дорога домой.
#p112721,Лукомор написал(а):
С которой начать?!
С самой безопасной.
Поделиться7912019-10-04 17:38:23
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
#p112721,Лукомор написал(а):
С которой начать?!
Ты эта брось, нафиг! Мне такой текст анекдот-окошко прислало, что я даже переспрашивапть стесняюсь 
Поделиться7922019-10-04 18:08:54
- Ветеран
- Уважение: +3175
- Провел на форуме:
4 месяца 8 дней - Последний визит:
2021-08-22 02:44:39
- Как называется вещество, при приёме которого мозг атрофируется и
перестаёт отвечать за свои действия?
- Семечки!
Поделиться7932019-10-04 19:06:55
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112748,Шарпер написал(а):
Ты эта брось, нафиг!
Прекрасно! Вот с неё и начнем!
Короче, нашел я способ мусорные твои траектории вынести.
Вот, допустим для примера, в учебной какой-то задачке, пусть имеем 100 пунктов с расстояниями между ними в интервале от 3 до 300 км.
На преодоление таких расстояний свет потратит от 10 до 1000 микросекунд.
Запускаем лучик позитива, в смысле лазера, по всем маршрутам сразу.
Маршрут через ровно 100 пунктов, при таких условиях, никогда не будет короче 300 км или длиннее 30 000 км.
Теперь в каждом пункте ставим задержку калиброванной длительностью ровно 1 сек.
Тогда в конечный пункт лучи, прошедшие ровно один отрезок, придут в интервале 0,00001 - 0,001 с.
Потом будет перерывчик небольшой, и лучи прошедшие два отрезка, с учетом задержки после пераого отрезка придут в интервале
1,00002 - 1,002 сек.
...
Прошедшие 98 пунктов придут в интервале 97,00098 - 97,098.
Это все мусорные...
И вот приходят прошедшие все 99 отрезков: интервал 98,00099 - 98,099 секунд.
Луч по кратчайшему маршруту придет к финишу в этом интервале первым.
Отредактировано Лукомор (2019-10-04 19:15:18)
Поделиться7942019-10-04 19:43:05
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
#p112763,Лукомор написал(а):
Луч по кратчайшему маршруту придет к финишу в этом интервале первым.
Ты гений!!! Можешь не спрашивать, почему сразу Лукомор - патаму што гений! 
Блин, как я сам не догадался?
Поделиться7952019-10-04 19:44:50
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
Лукомор
Расстояние тоже можно эмулировать задержкой
Поделиться7962019-10-04 19:45:52
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
Лукомор
Вобщем, проверяем и двигаем за лимоном
Поделиться7972019-10-04 19:54:20
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112768,Шарпер написал(а):
и двигаем за лимоно
Двигайте!
И попутная песня в дорогу
Поделиться7982019-10-04 19:58:42
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
#p112770,Лукомор написал(а):
Двигайте!
Чо и пытаться не будешь? Зря. Не получится и фиг с ним, а попробовать надо.
Поделиться7992019-10-04 20:06:16
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
Лукомор
Интересно, что мысля использовать задержку для отсева мне приходила, но я ни разу не допетрил, что можно тупо пересчитать ребра
Поделиться8002019-10-04 20:07:01
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112745,Ал написал(а):
количество путей от количества точек растёт экспоненциально.
При полном переборе.
В эвристических методах -по разному...
Поделиться8012019-10-04 20:09:47
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
Лукомор
Короче, ушел проверять
Поделиться8022019-10-04 20:12:35
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112771,Шарпер написал(а):
и пытаться не будешь?
Некогда мне ерундой заниматься...
Поделиться8032019-10-04 20:15:57
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
#p112775,Лукомор написал(а):
Некогда мне ерундой заниматься...
Ха, а кто это сделал?
Впрочем, погоди радоваться, похоже есть прокол
Поделиться8042019-10-04 20:31:41
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
Вторая хорошая новость:
но...
сначала - предыстория.
Я нашел решение задачи коммивояжера на 17 пунктов, и оба моих метода забороли на этой задаче метод случайного соседа.
Но я не смог сравнить мои методы с методом ветвей и границ поскольку нет онлайн калькуляторов на количество пунктов больше 15.
Я нашел компромисс в том, что применил к исходной задаче первый этап моего метода объединения точек,
и получил новую задачу на 13 пунктов.
Внезапно, оба моих метода на этой новой более простой задаче проиграли не только методу ветвей и границ, но и методу ближайшего соседа.
Вчера я повторно применил первый этап метода объединения точек к уже задаче на 13 пунктов.
И получил новую задачу уже на 10 пунктов.
Я решил эту задачу всеми известными мне методами и все эти методы дали один и тот же маршрут.
Это выглядит обнадеживающе.
Теперь можно, добавляя не сразу три точки, а по одной,
как под микроскопом рассмотреть всю эту картинку,
и найти, где и на каком пункте сломался каждый из методов.
И попробовать их починить...
Отредактировано Лукомор (2019-10-04 20:32:09)
Поделиться8052019-10-04 20:35:26
- Ветеран
- Уважение: +7554
- Пол: Мужской
- Провел на форуме:
3 месяца 16 дней - Последний визит:
Вчера 23:03:16
#p112763,Лукомор написал(а):
Луч по кратчайшему маршруту придет к финишу в этом интервале первым.
А как отличить маршрут, прошедший все точки по одному разу, от маршрута с пропуском одной точки, но при этом с повторным прохождением одной из точек? Ну и далее для большего числа пропусков и повторов.
Поделиться8062019-10-04 20:37:13
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112776,Шарпер написал(а):
прокол
Есть Прокол Харум...
Поделиться8072019-10-04 20:48:54
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
Вчера 17:35:35
#p112781,Zagar написал(а):
А как отличить маршрут, прошедший все точки по одному разу, от маршрута с пропуском одной точки, но при этом с повторным прохождением одной из точек? Ну и далее для большего числа пропусков и повторов.
А я откуда знаю?!
Это - к Шарперу!
Он просил убрать более короткие и более длинные, - я убрал...
Про коллизии с одинаковым количеством отрезков вопроса не возникало... 
Поделиться8082019-10-04 20:56:41
- Ветеран
- Уважение: +7554
- Пол: Мужской
- Провел на форуме:
3 месяца 16 дней - Последний визит:
Вчера 23:03:16
#p112783,Лукомор написал(а):
Про коллизии с одинаковым количеством отрезков вопроса не возникало...
Победит вариант, в котором луч пройдет n раз от стартовой точки до ближайшей и обратно.
Поделиться8092019-10-04 23:33:08
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
#p112785,Zagar написал(а):
Лукомор
Про коллизии с одинаковым количеством отрезков вопроса не возникало...
Победит вариант, в котором луч пройдет n раз от стартовой точки до ближайшей и обратно.
угу, они самые коллизии.
Итак
1 Секунда на точку это слишком много - 1000000 точек даст время ожидания ~ 2000000/3600=555 часов или больше 20 суток. Но за счет высокой частоты калиброванные интервалы можно задавать и в пикосекундах.
2 Чтобы избежать зацикливания сигнала, нужно применять матрицу N*N в стиле Черны.
3 Чтобы избежать коллизии надо точкам назначить разные интервалы, чтобы сумма по полному пути была больше любой с пропусками вершин. Например первым точком перворго столбца - 1, второму - 2 и т.д.
Проверяйте.
Поделиться8102019-10-04 23:35:37
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 06:19:38
#p112782,Лукомор написал(а):
Прокол Харум...
Это что еще за Башировы с Петровыми на фоне шпиля? 
