Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Сортировка географических координат по близости друг к другу - Страница 2 - Мир MS Excel

Старая форма входа
  • Страница 2 из 2
  • «
  • 1
  • 2
Модератор форума: китин, _Boroda_  
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Сортировка географических координат по близости друг к другу (Формулы/Formulas)
Сортировка географических координат по близости друг к другу
MCH Дата: Среда, 13.08.2014, 08:07 | Сообщение № 21
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

Решение задачи коммивояжера, как готовое решение опубликовал здесь: http://www.excelworld.ru/forum/3-12090-1
Там есть решение полным перебором, для 12 городов и менее - подходит.
 
Ответить
СообщениеРешение задачи коммивояжера, как готовое решение опубликовал здесь: http://www.excelworld.ru/forum/3-12090-1
Там есть решение полным перебором, для 12 городов и менее - подходит.
Автор - MCH
Дата добавления - 13.08.2014 в 08:07
SLAVICK Дата: Четверг, 14.08.2014, 14:12 | Сообщение № 22
Группа: Модераторы
Ранг: Старожил
Сообщений: 2290
Репутация: 766 ±
Замечаний: 0% ±

2019
Пытаюсь разобраться в Вашем коде %)
На сколько я понял - сначала создается массив с комбинациями, потом идет просчет расстояний.
Я добавил в код вывод хода выполнения в статусбар.
Получается что дольше всего создается этот самый массив комбинаций. Просчет расстояний в десятки раз быстрее - особенно если выбирать 11-12 городов.

У Вас в коде есть строка перескока по строкам общего массива :[vba]
Код
"i = i + f(n - 1 - j) - 1"
[/vba]
Может можно обойтись без массива комбинаций и как-то создавать временный массив на основании текущего положения "I"(формулой)?
Пока не нашел решения.
Кроме того не будет грузится комп. У меня например на компе хватает оперативки для массива в 49 000 000стр., а на виртуалбоксе - не хватает.
К сообщению приложен файл: Travelling_sale.zip (28.5 Kb)

Иногда все проще чем кажется с первого взгляда.

Сообщение отредактировал SLAVICK - Четверг, 14.08.2014, 14:18
 
Ответить
СообщениеПытаюсь разобраться в Вашем коде %)
На сколько я понял - сначала создается массив с комбинациями, потом идет просчет расстояний.
Я добавил в код вывод хода выполнения в статусбар.
Получается что дольше всего создается этот самый массив комбинаций. Просчет расстояний в десятки раз быстрее - особенно если выбирать 11-12 городов.

У Вас в коде есть строка перескока по строкам общего массива :[vba]
Код
"i = i + f(n - 1 - j) - 1"
[/vba]
Может можно обойтись без массива комбинаций и как-то создавать временный массив на основании текущего положения "I"(формулой)?
Пока не нашел решения.
Кроме того не будет грузится комп. У меня например на компе хватает оперативки для массива в 49 000 000стр., а на виртуалбоксе - не хватает.
Автор - SLAVICK
Дата добавления - 14.08.2014 в 14:12
SLAVICK Дата: Четверг, 14.08.2014, 23:49 | Сообщение № 23
Группа: Модераторы
Ранг: Старожил
Сообщений: 2290
Репутация: 766 ±
Замечаний: 0% ±

2019
Нашел на форуме старую тему:
[http://www.planetaexcel.ru/forum/index.php?PAGE_NAME=read&FID=8&TID=35378]
Там Вы делали похожий расчет, который на основании числа выдавал комбинацию... но не совсем то.
Мне кажется так будет быстрее.

Иногда все проще чем кажется с первого взгляда.

Сообщение отредактировал SLAVICK - Пятница, 15.08.2014, 01:02
 
Ответить
СообщениеНашел на форуме старую тему:
[http://www.planetaexcel.ru/forum/index.php?PAGE_NAME=read&FID=8&TID=35378]
Там Вы делали похожий расчет, который на основании числа выдавал комбинацию... но не совсем то.
Мне кажется так будет быстрее.
Автор - SLAVICK
Дата добавления - 14.08.2014 в 23:49
SLAVICK Дата: Пятница, 29.08.2014, 10:35 | Сообщение № 24
Группа: Модераторы
Ранг: Старожил
Сообщений: 2290
Репутация: 766 ±
Замечаний: 0% ±

2019
Благодаря этой теме нашлось неплохое решение :D
В приложении файл.
В зеленой ячейке можно проставить ограничение количества повторений результата.
Если число удалить цикл проход будет с 1 до конца комбинаций по большим блокам, потом рядом с большим блоком(в котором было найдено наименьшее расстояние) пробегает по меньшим блокам и т.д. пока не дойдет до наименьшего блока.
Для количества комбинаций больше 20 - рекомендую ставить ограничение... можно 100 000 - 1000 000. Можно и больше.... чем больше число тем дольше будет работать функция.
Дальше думаю можно было бы как-то подключить случайные числа... вот только не уверен что они помогут... да и с ними результат при повторном результате может быть другим. %)
К сообщению приложен файл: Travelling_sale.xlsm (52.5 Kb)

Иногда все проще чем кажется с первого взгляда.

Сообщение отредактировал SLAVICK - Пятница, 29.08.2014, 11:19
 
Ответить
СообщениеБлагодаря этой теме нашлось неплохое решение :D
В приложении файл.
В зеленой ячейке можно проставить ограничение количества повторений результата.
Если число удалить цикл проход будет с 1 до конца комбинаций по большим блокам, потом рядом с большим блоком(в котором было найдено наименьшее расстояние) пробегает по меньшим блокам и т.д. пока не дойдет до наименьшего блока.
Для количества комбинаций больше 20 - рекомендую ставить ограничение... можно 100 000 - 1000 000. Можно и больше.... чем больше число тем дольше будет работать функция.
Дальше думаю можно было бы как-то подключить случайные числа... вот только не уверен что они помогут... да и с ними результат при повторном результате может быть другим. %)
Автор - SLAVICK
Дата добавления - 29.08.2014 в 10:35
SLAVICK Дата: Пятница, 29.08.2014, 11:00 | Сообщение № 25
Группа: Модераторы
Ранг: Старожил
Сообщений: 2290
Репутация: 766 ±
Замечаний: 0% ±

2019
Думаю оптимальным будет сделать просчет при помощи связки функций поиска мин расстояния по комбинации просчитанной графическим способом(который предложил МСН) - потом запустить с начальной комбинацией - макрос перебора... таким образом будет быстро и точное расстояние. Поскольку графический способ дает путь по прямой, а перебор берет расстояния из матрицы расстояний.
Перебором можно быстро определить близкий к оптимальному маршрут уже сейчас... но так будет точнее... и для больших комбинаций(больше 20) - быстрее.

Иногда все проще чем кажется с первого взгляда.
 
Ответить
СообщениеДумаю оптимальным будет сделать просчет при помощи связки функций поиска мин расстояния по комбинации просчитанной графическим способом(который предложил МСН) - потом запустить с начальной комбинацией - макрос перебора... таким образом будет быстро и точное расстояние. Поскольку графический способ дает путь по прямой, а перебор берет расстояния из матрицы расстояний.
Перебором можно быстро определить близкий к оптимальному маршрут уже сейчас... но так будет точнее... и для больших комбинаций(больше 20) - быстрее.
Автор - SLAVICK
Дата добавления - 29.08.2014 в 11:00
MCH Дата: Понедельник, 01.09.2014, 15:24 | Сообщение № 26
Группа: Админы
Ранг: Старожил
Сообщений: 2003
Репутация: 751 ±
Замечаний: ±

Свое решение перебором обновил http://www.excelworld.ru/forum/3-12090-1
Избавился от генерации массива перестановок, это ускорило решение более чем в 2 раза
 
Ответить
СообщениеСвое решение перебором обновил http://www.excelworld.ru/forum/3-12090-1
Избавился от генерации массива перестановок, это ускорило решение более чем в 2 раза
Автор - MCH
Дата добавления - 01.09.2014 в 15:24
dadade Дата: Понедельник, 07.10.2019, 19:09 | Сообщение № 27
Группа: Пользователи
Ранг: Новичок
Сообщений: 11
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
С обеда изучаю ваши фалы и пытаюсь сделать свое но никак не получается ввиду того что у меня двоичный массив примерно на 500x500 значении.
У каждой точки координаты, и нужно вычислить расстояние между точками вот на этом застрял. Задача найти самые близкие точки.
Файл с коммивояжерами не подходит, так как не показывает расстояние между точками.
Помогите пжл решить данную задачу.
Заранее спасибо!


Сообщение отредактировал dadade - Понедельник, 07.10.2019, 19:11
 
Ответить
СообщениеС обеда изучаю ваши фалы и пытаюсь сделать свое но никак не получается ввиду того что у меня двоичный массив примерно на 500x500 значении.
У каждой точки координаты, и нужно вычислить расстояние между точками вот на этом застрял. Задача найти самые близкие точки.
Файл с коммивояжерами не подходит, так как не показывает расстояние между точками.
Помогите пжл решить данную задачу.
Заранее спасибо!
Автор - dadade
Дата добавления - 07.10.2019 в 19:09
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Сортировка географических координат по близости друг к другу (Формулы/Formulas)
  • Страница 2 из 2
  • «
  • 1
  • 2
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!