vampirich Опубліковано 18 Серпня, 2014 в 13:48 Поділитися #1 Опубліковано 18 Серпня, 2014 в 13:48 Є кільканадцять сіл в одному районі, які потрібно об"їхатиі хотілося б скласти маршрут з найменьшим кілометражемВсі ті картографічні сервіси що находив, або вимагають щоб послідовність відвідування вибиралась вручну, або не вміють працювати з одинаковими назвами насерених пунктів (тобто коли мені треба добавити точку "городище" луцького району, скоріше за все мене відправлять у київську область абощо)Хтось працював з подібними задачами? порадить якийсь простий сервіс?У мене не постійна а разова задача, тому зручність сервісу питання другорядне Посилання на коментар Поділитись на інші сайти Поділитися
Saddy Опубліковано 18 Серпня, 2014 в 14:01 Поділитися #2 Опубліковано 18 Серпня, 2014 в 14:01 в свій час в інституті вручну розв'язували подібні задачі (т.з. званий маршрут листоноші) - погугли, знайдеш приклади розв'язання. Посилання на коментар Поділитись на інші сайти Поділитися
vampirich Опубліковано 18 Серпня, 2014 в 14:09 Автор Поділитися #3 Опубліковано 18 Серпня, 2014 в 14:09 Про таке знаю Але таке ускладняє задачу в моєму конкретному випадку є 27 точок маршруту І щоб скористатися задачою листоноші треба знати відстані: 1 - 2 1 - 3 ... 1 - 27 2 - 3 .... 2 - 27 ... 3 -4 ... ітого 27! раз порахувати відстаней між точками а потім іще рахувати оптимальні маршрути не радує така перспектива Посилання на коментар Поділитись на інші сайти Поділитися
Саня Опубліковано 18 Серпня, 2014 в 14:15 Поділитися #4 Опубліковано 18 Серпня, 2014 в 14:15 або ще називать транспортна задача чи задача комівояжера. Бувають різні варіації. Посилання на коментар Поділитись на інші сайти Поділитися
MaestroA Опубліковано 18 Серпня, 2014 в 14:19 Поділитися #5 Опубліковано 18 Серпня, 2014 в 14:19 Якщо це разова задача, то чим Вас не влаштовує задати послідовність вручну? Так як я їзджу досить багато, то постійно займаюсь маршрутизацією. Google Maps мені цілком вистачає. Посилання на коментар Поділитись на інші сайти Поділитися
vampirich Опубліковано 18 Серпня, 2014 в 14:21 Автор Поділитися #6 Опубліковано 18 Серпня, 2014 в 14:21 задати вручну - не проблемаЯк взнати найкращу послідовність з мінімальним кілометражем?якщо 3-5 точок, то методом "пересунув - прикинув" легко вибрати найкращий маршрута якщо 27? Посилання на коментар Поділитись на інші сайти Поділитися
Deemon Опубліковано 18 Серпня, 2014 в 14:29 Поділитися #7 Опубліковано 18 Серпня, 2014 в 14:29 а банально-популярні - карти гугл, навітел - не зроблять такого? Посилання на коментар Поділитись на інші сайти Поділитися
Artem158 Опубліковано 18 Серпня, 2014 в 14:34 Поділитися #8 Опубліковано 18 Серпня, 2014 в 14:34 постав api easyway Посилання на коментар Поділитись на інші сайти Поділитися
vampirich Опубліковано 18 Серпня, 2014 в 14:36 Автор Поділитися #9 Опубліковано 18 Серпня, 2014 в 14:36 карти гугла хочуть щоб я їм сказав що я хочу спочатку в точку а потім в б потім в с і т да мені треба щоб я ввів послідовність точок, а мені сказало: для найкоротшого маршруту їдьте спочатку в с, потім а і аж тоді в б Посилання на коментар Поділитись на інші сайти Поділитися
Dream Опубліковано 18 Серпня, 2014 в 14:41 Поділитися #10 Опубліковано 18 Серпня, 2014 в 14:41 Почнемо з того чи всі села треба об'їхати за один день? Якщо ні, то де ночувати - в одному з сіл чи вертатись на початок маршруту? Якщо кілька днів, то задача значно спрощується. Посилання на коментар Поділитись на інші сайти Поділитися
vampirich Опубліковано 18 Серпня, 2014 в 14:43 Автор Поділитися #11 Опубліковано 18 Серпня, 2014 в 14:43 за день. фактично треба об"їхати більшість сіл одного району, що в принципі за день цілком реально Посилання на коментар Поділитись на інші сайти Поділитися
MaestroA Опубліковано 18 Серпня, 2014 в 14:45 Поділитися #12 Опубліковано 18 Серпня, 2014 в 14:45 Ради цікавості, поділіться списком населених пунктів. Посилання на коментар Поділитись на інші сайти Поділитися
Saddy Опубліковано 18 Серпня, 2014 в 14:46 Поділитися #13 Опубліковано 18 Серпня, 2014 в 14:46 до речі, найкоротший шлях не завжди буває найоптимальнішим, тим паче по дорогах через села. Деякі відрізки шляху можуть бути розмиті/розбиті і т.д. Посилання на коментар Поділитись на інші сайти Поділитися
MaestroA Опубліковано 18 Серпня, 2014 в 14:50 Поділитися #14 Опубліковано 18 Серпня, 2014 в 14:50 Якщо й існує программа, яка сама задає послідовність точок для маршруту, то з великою вірогідністю вона прокладе маршрут через такі дрищі, що будете нераді такій "оптимальності" і останньою точкою стане СТО. Посилання на коментар Поділитись на інші сайти Поділитися
Will Опубліковано 18 Серпня, 2014 в 14:53 Поділитися #15 Опубліковано 18 Серпня, 2014 в 14:53 до речі, найкоротший шлях не завжди буває найоптимальнішим, тим паче по дорогах через села. Деякі відрізки шляху можуть бути розмиті/розбиті і т.д.згадати хоча б відрізок Стоянів - Кам’янка Бузька траси Луцьк-Львів... Посилання на коментар Поділитись на інші сайти Поділитися
vampirich Опубліковано 18 Серпня, 2014 в 14:55 Автор Поділитися #16 Опубліковано 18 Серпня, 2014 в 14:55 БережанкаБрани Бужани Ватин Вільхівка ГаличаниГорішненє ГубинЖабчеЖуравникиЗвиняченськКвасівКолодежнеЛемешівЛобачівМерваМирківМирнеМихлинНовосілкиПеремильПечихвостиПідбереззяПірванчеПіски ПустомитівРачинСкірчеСкобелкаСкригівСмоляваТерешківціУгринівХолонівЦегівШкліньмарянівкасенкивечівкаMaestroA, згідний. Але з чогось почати ж треба.Маршрут "наугад" може бути в рази довшим за оптимальний Посилання на коментар Поділитись на інші сайти Поділитися
MaestroA Опубліковано 18 Серпня, 2014 в 14:57 Поділитися #17 Опубліковано 18 Серпня, 2014 в 14:57 MaestroA, згідний. Але з чогось почати ж треба. Маршрут "наугад" може бути в рази довшим за оптимальнийЯ б почав з паперової карти Волині на столі та маркета в руках. Посилання на коментар Поділитись на інші сайти Поділитися
Saddy Опубліковано 18 Серпня, 2014 в 14:58 Поділитися #18 Опубліковано 18 Серпня, 2014 в 14:58 найпростіше, можливо не самий коротший варіант - позначити усі точки на детальній карті і намалювати такий собі круг, який буде проходити через них усі і почати з точки, яка найближче від старту. Посилання на коментар Поділитись на інші сайти Поділитися
vampirich Опубліковано 18 Серпня, 2014 в 15:57 Автор Поділитися #19 Опубліковано 18 Серпня, 2014 в 15:57 так то воно так, але хотілося б "автоматизовано" + такий сервіс не одному мені мабуть згодився б Посилання на коментар Поділитись на інші сайти Поділитися
b0rg Опубліковано 18 Серпня, 2014 в 16:07 Поділитися #20 Опубліковано 18 Серпня, 2014 в 16:07 погугли "задача коммивояжера" типу цього Посилання на коментар Поділитись на інші сайти Поділитися
Vadimm Опубліковано 18 Серпня, 2014 в 17:29 Поділитися #21 Опубліковано 18 Серпня, 2014 в 17:29 Людина шукає готове рішення а ви його "грузите" паперовими картами і матрицями з алгоритмом Літтла З власного досвіду скажу що часто буває так, що там де Гугл Мапс показує дорогу, насправді її нема, або вона з'являється лише коли добряче просохне після весни. Тому зауваження Якщо й існує программа, яка сама задає послідовність точок для маршруту, то з великою вірогідністю вона прокладе маршрут через такі дрищі, що будете нераді такій "оптимальності" і останньою точкою стане СТО. вважаю слушним і здатним перекреслити любі результати які покаже програма. Посилання на коментар Поділитись на інші сайти Поділитися
Єретик Опубліковано 18 Серпня, 2014 в 17:35 Поділитися #22 Опубліковано 18 Серпня, 2014 в 17:35 БережанкаБраниБужаниВатинВільхівкаГаличаниГорішненєГубинЖабчеЖуравникиЗвиняченськКвасівКолодежнеЛемешівЛобачівМерваМирківМирнеМихлинНовосілкиПеремильПечихвостиПідбереззяПірванчеПіскиПустомитівРачинСкірчеСкобелкаСкригівСмоляваТерешківціУгринівХолонівЦегівШкліньмарянівкасенкивечівкаMaestroA, згідний. Але з чогось почати ж треба.Маршрут "наугад" може бути в рази довшим за оптимальнийЯкщо це всі населені пункти, то задачу можна вирішити тривіально. Просто, надійно, але довго! Для цього можна зробити таблицю відстаней між усіма населенними пунктами, а далі в циклі знайти найменші значення і вивести маршрут. А намалювати це все можна в картах від гугля. Посилання на коментар Поділитись на інші сайти Поділитися
vampirich Опубліковано 18 Серпня, 2014 в 18:02 Автор Поділитися #23 Опубліковано 18 Серпня, 2014 в 18:02 Для цього можна зробити таблицю відстаней між усіма населенними пунктами це треба 378 варіантів перебрати до холєри Чесно кажучи дивує що немає якогось готового рішення для цього на картографічних сервісах Посилання на коментар Поділитись на інші сайти Поділитися
guest Опубліковано 18 Серпня, 2014 в 19:13 Поділитися #24 Опубліковано 18 Серпня, 2014 в 19:13 це треба 378 варіантів перебрати1.0888869e+28 Посилання на коментар Поділитись на інші сайти Поділитися
LSD Опубліковано 18 Серпня, 2014 в 23:55 Поділитися #25 Опубліковано 18 Серпня, 2014 в 23:55 Ось варіант з програмкою при умові що у Вас вийде гамільтоновий граф ...http://www.kursovik....ing/320357.htmlТут задача комівояжера повним перебором:http://www.kursovik.com/programming/106018.html Посилання на коментар Поділитись на інші сайти Поділитися
Рекомендовані повідомлення
Заархівовано
Ця тема знаходиться в архіві та закрита для подальших відповідей.