Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Комбинаторика  [new]
Yura1989
Member

Откуда: Днепропетровск
Сообщений: 31
Необходимо реализовать перебор всех возможных комбинаций точек выгрузки. Например, маршрут построен следующим образом:
1
2
3
4
5

Мне нужно получить все возможные комбинации

1
3
2
4
5

2
1
3
4
5

и тд.

Дайте пожалуйста толчок куда капнуть, как реализовать. Цель стоит в том, что бы перебрать все возможные варианты маршрута, и выбрать оптимальный исходя из суммы пробега по рейсу. ПО сделано в winforms, работает с БД, возможно делать этот перебор лучше в самом ПО или все таки на SQL ? Видел кучу костылей для c# с кучей for, мне этот вариант не нравится.
23 сен 16, 11:19    [19699507]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
Ken@t
Member

Откуда: 大地
Сообщений: 3264
Yura1989,

Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.
23 сен 16, 11:22    [19699522]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
Yura1989
Member

Откуда: Днепропетровск
Сообщений: 31
Ken@t,

его сейчас и использую, но ближайшее не всегда короче. Сейчас я делаю так, получаю точку отправки, в маршруте например 5 точек выгрузки, и циклом проверяю какая точку ближе всего, нахожу её и инсертю, потом уже от точки которую нашел ищу следующую и так далее. но как выяснилось это не всегда оптимально, иногда начать не с ближайшей точки а с последней или любой другой лучше, общий пробег по маршруту сокращается в разы. Вот и не придумал другого варианта, как перебор всех возможных комбинаций, пересчет км по ним исходя из моей матрицы км, и определением наиболее короткого по кольцу.
23 сен 16, 11:37    [19699600]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20603
Yura1989
Видел кучу костылей для c# с кучей for, мне этот вариант не нравится.

Ну если делать чисто на SQL - то для показанного примера придётся брать 5 копий таблицы, и из общего итогового числа записей, равного 3125, условиями отбирать 120 (менее 4%) подходящих. И чем больше записей, тем больше эта разница... ты правда думаешь, что ЭТО будет лучше?
23 сен 16, 11:41    [19699624]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
Yura1989
Member

Откуда: Днепропетровск
Сообщений: 31
Akina,

не совсем понял что вы имеете в виду, 5 точек это 120 комбинаций, значит это 600 строк, где каждые 5 строк - комбинация маршрута. Страшно что максимально в рейсе может быть 15 точек, а это - 1307674368000 комбинаций = (
23 сен 16, 12:06    [19699797]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6087
Yura1989
Ken@t,

его сейчас и использую, но ближайшее не всегда короче. Сейчас я делаю так, получаю точку отправки, в маршруте например 5 точек выгрузки, и циклом проверяю какая точку ближе всего, нахожу её и инсертю, потом уже от точки которую нашел ищу следующую и так далее. но как выяснилось это не всегда оптимально, иногда начать не с ближайшей точки а с последней или любой другой лучше, общий пробег по маршруту сокращается в разы. Вот и не придумал другого варианта, как перебор всех возможных комбинаций, пересчет км по ним исходя из моей матрицы км, и определением наиболее короткого по кольцу.


у вас Задача коммивояжёра
Википедия
Относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
- на SQL, ага...
23 сен 16, 13:19    [19700285]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
iap
Member

Откуда: Москва
Сообщений: 47001
Можно же запустить запрос на нескольких миллиардах айфонов!
23 сен 16, 13:21    [19700300]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
Yura1989
Member

Откуда: Днепропетровск
Сообщений: 31
kealon(Ruslan)
Yura1989
Ken@t,

его сейчас и использую, но ближайшее не всегда короче. Сейчас я делаю так, получаю точку отправки, в маршруте например 5 точек выгрузки, и циклом проверяю какая точку ближе всего, нахожу её и инсертю, потом уже от точки которую нашел ищу следующую и так далее. но как выяснилось это не всегда оптимально, иногда начать не с ближайшей точки а с последней или любой другой лучше, общий пробег по маршруту сокращается в разы. Вот и не придумал другого варианта, как перебор всех возможных комбинаций, пересчет км по ним исходя из моей матрицы км, и определением наиболее короткого по кольцу.


у вас Задача коммивояжёра
Википедия
Относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
- на SQL, ага...


Спасибо, буду думать другие варианты.
23 сен 16, 14:44    [19700834]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
ViPRos
Member

Откуда:
Сообщений: 9883
Yura1989,

ла фиг ли думать
это не жизненная задача
в жизни много ограничений, которые снижают размерность задачи
если бы не так, то самолеты бы не летали, поезда не ходили и т.д.
давай ограничения (типа можно доехать используя только ОДИН бак бензина, или количество точек заправки только 2 и там то и там то, или продолжительность поездки одного водилы не дольше смены и т.д.)
23 сен 16, 20:21    [19702489]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
ViPRos
Member

Откуда:
Сообщений: 9883
ViPRos,


Никаких NP задач в жизни нет - это только в вакууме (в умах математиков)
23 сен 16, 20:21    [19702492]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6087
ViPRos
ViPRos,


Никаких NP задач в жизни нет - это только в вакууме (в умах математиков)

пример, факторизация БОЛЬШИХ чисел - уже можете взламывать RSA?
26 сен 16, 08:41    [19707111]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
ViPRos
Member

Откуда:
Сообщений: 9883
kealon(Ruslan),

можно взламывать все что угодно сделанное человеком - цена взлома будет на порядок ниже чем разработка сделанного
заплати и лети
26 сен 16, 11:21    [19707702]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6087
ViPRos
kealon(Ruslan),

можно взламывать все что угодно сделанное человеком - цена взлома будет на порядок ниже чем разработка сделанного
заплати и лети

Пример NP-полной задачи из реальности, а не вакуумной математики. Зашифровать с помощью RSA пока гораздо проще чем взломать.
Сможете, вас будут искать сильнее Сноудена.
26 сен 16, 12:06    [19707933]     Ответить | Цитировать Сообщить модератору
 Re: Комбинаторика  [new]
aleks2
Guest
kealon(Ruslan)
ViPRos
kealon(Ruslan),

можно взламывать все что угодно сделанное человеком - цена взлома будет на порядок ниже чем разработка сделанного
заплати и лети

Пример NP-полной задачи из реальности, а не вакуумной математики. Зашифровать с помощью RSA пока гораздо проще чем взломать.
Сможете, вас будут искать сильнее Сноудена.

Зачем такие сложности?
ViPRos задачку тредстартера решить не может. Для 15 точек.

ЗЫ. Болтать - не мешки ворочать.
26 сен 16, 12:59    [19708228]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить