Лукомор
Траекторный вычислитель - триумфальное подтверждение
Сообщений 301 страница 330 из 451
Поделиться3012019-08-28 12:17:29
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
Поделиться3022019-08-28 12:50:43
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p109783,Шарпер написал(а):
Сегодня 12:17:29
Вы там аккуратнее...
завязывайте... с этим делом!
Минздрав сомневается...
Но!!!
Алкоголизм - не шутка!
Отредактировано Лукомор (2019-08-28 12:54:57)
Поделиться3032019-08-28 13:18:58
- Модератор
- Уважение: +14531
- Провел на форуме:
7 месяцев 13 дней - Последний визит:
Сегодня 17:17:31
#p109762,Шарпер написал(а):
У меня есть мысль и я ее думаю. Бойтесь!
Ага, ага. Что-то про улучшение алгоритма. 
Поделиться3042019-08-28 16:24:46
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
Поделиться3052019-08-31 15:29:30
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
Короче, мысь я додумал. Опять про коммивояжера. Заикнулись мы, напоминаю, на том, что так и не нашли способа отсеять отсеять запретные пути и отловить первый кратчайший разрешенный, чтобы потом, зная точку выхода двоичным поиском восстановить путь обратным ходом. Так вот, оказалось, что способ есть. Надо просто сначала вычислить кратчайшее время по сумме отрезков отсортированных по величине. Это будет теоретический разрешенный минимум, все меньшие значения автоматом отсеиваем. А затем, начиная с большего или равного теоретическому по времени реальному результату проверять нашим обратным ходом каждый путь, пока не обнаружится разрешенный. Это и будет кратчайший путь. Сколько испытаний понадобится посчитать невозможно, разве Лукомор сумеет, но очевидно, что кратчайший будет ближе к теоретическому,
Поделиться3062019-08-31 19:36:25
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110052,Шарпер написал(а):
Надо просто сначала вычислить кратчайшее время по сумме отрезков отсортированных по величине.
Вот учебная задачка на 17 пунктов.
Матрица расстояний между пунктами:
Как отсортировать отрезки по величине?
Поделиться3072019-08-31 20:34:59
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110071,Лукомор написал(а):
Как отсортировать отрезки по величине?
Как отсортировать отрезки по величине?
Элементарно, дорогой Ватсон! Разбираешь многоугольник по ребрышкам и кладешь их в линию, начиная с короткого по возрастанию так, чтобы все вершины были перечислены ровно по одному разу, т.е. лишние ребра выкидываешь. Это и будет кратчайший теоретический маршрут, котороого на самом деле в фигуре нет, поскольку мы наплЮвали на последователшьность соединения вершин. Просто задаемся такой длиной и временем по ней.
Поделиться3082019-08-31 20:49:31
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110072,Шарпер написал(а):
начиная с короткого по возрастанию так, чтобы все вершины были перечислены ровно по одному разу
Одно ребро перечисляет сразу две вершины.
На семнадцать вершин в некоторых случаях будет достаточно и восемь с половиной ребер....
Поделиться3092019-08-31 20:54:34
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110074,Лукомор написал(а):
На семнадцать вершин в некоторых случаях будет достаточно и восемь с половиной ребер....
Что тебя смущает? Мы ж начхали на истинное положение ребер и располагаем их в линию по возрастанию. В ёкселе отсортируй и выкинь лишние
Поделиться3102019-08-31 20:58:14
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
Лукомор
Это нужно чтоб отсеять заведомо запретные неполные пути. В принципе можно этого и вовсе не делать, а начинать отсеивать запретные с первого кратчайшего.
Поделиться3112019-08-31 21:06:41
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110074,Лукомор написал(а):
Одно ребро перечисляет сразу две вершины.
А, понял. Ну по два раза - вход, выход. Или как там, а то башка уже не варит?
Поделиться3122019-08-31 21:30:59
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110075,Шарпер написал(а):
В ёкселе отсортируй и выкинь лишние
Ёксель-шмоксель не понимает, что такое:
#p110072,Шарпер написал(а):
Разбираешь многоугольник по ребрышкам и кладешь их в линию, начиная с короткого по возрастанию так, чтобы все вершины были перечислены ровно по одному разу, т.е. лишние ребра выкидываешь.
Пришлось в рукопашную, получилось вот так:
Поделиться3132019-08-31 21:52:23
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110080,Лукомор написал(а):
Пришлось в рукопашную, получилось вот так:
И Фурманов говорит это ножницы? По-моему здесь второй вариант.
Поделиться3142019-08-31 22:44:34
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110081,Шарпер написал(а):
По-моему здесь второй вариант.
Ладно, я сегодня подозрительно добрый.
Вот подарок от меня бегемоту на 1 сентября.
На схеме 19 самых коротких отрезков между пунктами, как и требовалось согласно техзадания выданного бегемотом.
Два отрезка лишних, но это не важно, так как три самых длинных отрезка, изображенных красным, имеют строго одинаковую длину.
Разумеется при суммировании я взял только одну длину, а две других отбросил.
Вопрос, что теперь с этим лучезарным счастьем нам делать?
Отредактировано Лукомор (2019-09-01 06:00:09)
Поделиться3152019-09-01 05:55:26
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110084,Лукомор написал(а):
Вопрос, что теперь с этим лучезарным счастьем нам делать?
Вытянуть в линию, просуммировать для получемя длины и вычислить время прохождения. Использовать это время в качестве минимального теорнтического, игнорируя все более короткие и завеломо неполные пути.
Повторяю, можно и без этого этапа, а сразу отсеивать запретные начиная с заведомо неполных
Поделиться3162019-09-01 06:40:34
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110095,Шарпер написал(а):
Вытянуть в линию, просуммировать для получемя длины и вычислить время прохождения.
Я же уже просуммировал!
Там где L = 323.716
- это сумма длин 17 самых коротких отрезков.
Поделиться3172019-09-01 06:41:57
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110095,Шарпер написал(а):
Использовать это время в качестве минимального теорнтического, игнорируя все более короткие и завеломо неполные пути.
А как будем игнорировать более длинные и заведомо неполные пути?
Сумма длин вот этих трех отрезков больше, чем сумма семнадцати самых коротких, на.
Отредактировано Лукомор (2019-09-01 06:50:29)
Поделиться3182019-09-01 06:51:50
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110098,Лукомор написал(а):
Я же уже просуммировал!
Ну вот, искомый будет равен или больше. Т.е начинать проверять с этой длины и времени
#p110099,Лукомор написал(а):
А как будем игнорировать более длинные и заведомо неполные пути?
А они не придут раньше кратчайшего разрешенного, потому что длиннее. Аогоритм остановится раньше
Поделиться3192019-09-01 06:58:18
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110099,Лукомор написал(а):
Сумма длин вот этих трех отрезков больше, чем сумма семнадцати самых коротких, на.
Или ты спрашиваешт о запретных длиннее вычисленного, но короче искомого? Дык обратным ходом через восстановление каждого пути с проверкой на запретность
Поделиться3202019-09-01 07:07:09
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110052,Шарпер написал(а):
А затем, начиная с большего или равного теоретическому по времени реальному результату проверять нашим обратным ходом каждый путь, пока не обнаружится разрешенный. Это и будет кратчайший путь.
С этого места попо дробнее.
До сиз пор мы не использовали "наш обратный ход" для нахождения разрешенного пути.
Никогда такого не было и вот снова!
Мы "наш обратный ход" использовали для восстановления пути по известной длине кратчайшего разрешенного пути.
Но если мы не знаем, разрешенный или не разрешенный путь имеет длину 399.999 км, то мы не сможем установить этот факт обратным ходом.
Точнее сможем, но для данного случая это равносильно полному прямому перебору, и даже хуже...
Поделиться3212019-09-01 07:55:31
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110102,Лукомор написал(а):
Никогда такого не было и вот снова!
Да
#p110102,Лукомор написал(а):
Мы "наш обратный ход" использовали для восстановления пути по известной длине кратчайшего разрешенного пути.
Да. Но дык, потом выяснилось, что кратчайший по времени сигнал не отсеивает автоматически неполные еще более короткие пути и на этом остановились. А оказаывается, что обратным ходом их отсеять можно
#p110102,Лукомор написал(а):
Но если мы не знаем, разрешенный или не разрешенный путь имеет длину 399.999 км, то мы не сможем установить этот факт обратным ходом.
Точнее сможем, но для данного случая это равносильно полному прямому перебору, и даже хуже...
Нет. Приводит к перебору до первого кратчайшего разрешенного. Это далеко не полный перебор, поскольку алгоритм остановится раньше, чем придут более длинные пути - искомый будет уже найден.
Так что перебор будет лежать в диапазоне коротких путей от неполных, до первого кратчайшего полного.
Ну, а сам отсев обратным ходом элементарен - восстановленный путь не будет проходить все вершины.
Поделиться3222019-09-01 08:18:35
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110103,Шарпер написал(а):
А оказаывается, что обратным ходом их отсеять можно
Да, но мы об этом ничего не знаем...
Оказывается, что обратным ходом их отсеять можно...
Оказывается, оказывается, но пока еще не оказалось!
Поделиться3232019-09-01 08:34:10
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110104,Лукомор написал(а):
Да, но мы об этом ничего не знаем...
Оказывается, что обратным ходом их отсеять можно...
Оказывается, оказывается, но пока еще не оказалось!
Это ж элементарно! Во всех восстановленных неполных путях будут пропущенные вершины. Их и отсеем.
Поделиться3242019-09-01 08:35:33
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110103,Шарпер написал(а):
Так что перебор будет лежать в диапазоне коротких путей от неполных, до первого кратчайшего полного.
То-есть мы можем уже разбить весь интервал времен прихода по всем <17!> возможным путям на два подынтервала:
- со временем прихода меньшим чем проход по сумме кратчайших отрезков.
- со временем прихода большим чем проход по сумме кратчайших отрезков, но меньшим чем проход по кратчайшему полному пути,
-со временем прохода большим чем проход по кратчайшему полному пути...
Пусть в каждом интервале находится соизмеримое, с точностью до порядка, хотя-бы, количество возможных маршрутов, в том числе недопустимых...
Тогда, после отбрасывания первого и третьего интервалов, у нас останется всего лишь каких-то
(1/3)х(17!)
вариантов...
Это всё то же экспоненциальное время работы алгоритма, поскольку никакие коэффициенты перед, не отменяют факториала в скобках...
Аттракцион "бегемот в колесе" продолжается... 
Отредактировано Лукомор (2019-09-01 08:36:19)
Поделиться3252019-09-01 08:38:23
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110106,Шарпер написал(а):
Это ж элементарно! Во всех восстановленных неполных путях будут пропущенные вершины. Их и отсеем.
Отсеем полным перебором неполных путей...
Поделиться3262019-09-01 08:58:24
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110108,Лукомор написал(а):
Отсеем полным перебором неполных путей...
Да! Но диапазон перебора будет не (N-1)!, а в промежутке между кратчайшим неполным и кратчайшим полным = искомым. А, если за минимум взять теоретический кратчайший, с которого я сегодня начал, то и того меньше.
Поделиться3272019-09-01 09:03:22
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110107,Лукомор написал(а):
Тогда, после отбрасывания первого и третьего интервалов, у нас останется всего лишь каких-то
(1/3)х(17!)
Это неверно! Ты перечислил ВСЕ варианты, а алгоритм остановится на первом кратчайшем разрешенном
Поделиться3282019-09-01 09:06:28
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110109,Шарпер написал(а):
Да! Но диапазон перебора будет не (N-1)!
Я уже прикинул...
При равномерном распределении будет (1/3)(N!), но подозреваю, что распределение длин маршрутов будет типа нормального, или какого-нибудь гипергеометрического, с горбом как-раз в нашем интервале между теоретическим кратчайшим и полным кратчайшим, тогда всё еще хуже...
Поделиться3292019-09-01 09:26:30
- Дичинка
- Уважение: +1388
- Пол: Мужской
- Провел на форуме:
5 месяцев 27 дней - Последний визит:
Сегодня 21:12:43
#p110112,Лукомор написал(а):
но подозреваю, что распределение длин маршрутов будет типа нормального
Это неверно. Распределение будет строго по возрастанию длины - сигналы будут поступать именно в этой последовательности - по возрастанию времени.
Поделиться3302019-09-01 09:38:01
- Ветеран
- Уважение: +5821
- Провел на форуме:
6 месяцев 5 дней - Последний визит:
2024-11-10 09:19:26
#p110110,Шарпер написал(а):
Ты перечислил ВСЕ варианты, а алгоритм остановится на первом кратчайшем разрешенном
Но этот первый кратчайший разрешенный будет после всех запрещенных более коротких...
Еще раз:
Всего 17! вариантов.
Мы откинем сразу (1/3)х17! запрещенных, которые короче чем 323.716. (Это сумма 17 самых коротких путей).
Кратчайший разрешенный маршрут через 17 пунктов в этой задаче имеет длину 448.150.(на сегодняшний день).
Нам надо перебрать все из этого интервала, начиная с длины 323.716...
Это еще (1/3)х17! вариантов. После этого алгоритм остановится,
И этим мы откинем все разрешенные, кроме кратчайшего, и все запрещенные длиннее кратчайшего разрешенного.
Это еще ( 1/3)х17!...
