Задачка на сообразительность

Цитата: ip74 от 16.10.2016 14:06:14
Задам простой вопрос.
Это была курсовая работа у меня.
Есть 20 городов. Их надо объединить сетью. 1 вариант - тип звезда. 2 - й вариант - тип кольцо. 3-й вариант - фулл мэш (все со всеми).
Исходно известно - географические координаты (аля 60 градусов широты + 28 градусов долготы) городов.
По второму варианту ваши предложения Алгоритм по 1 и 3 однозначен.

Цитата: ip74 от 16.10.2016 14:06:14

 

Это виртуальная задача или реальная? В реальности междугородние каналы обычно проложены Ростелекомом или местными провайдерами, или могут проложены провайдерами, и это много дешевле самостоятельной прокладки. А при наличии TCP/IP full-mesh получается автоматически.

• +0.00 / 0

Цитата: jamaze1 от 16.10.2016 15:44:36Это виртуальная задача или реальная? В реальности междугородние каналы обычно проложены Ростелекомом или местными провайдерами, или могут проложены провайдерами, и это много дешевле самостоятельной прокладки. А при наличии TCP/IP full-mesh получается автоматически.

Цитата: jamaze1 от 16.10.2016 15:44:36

 

Нет. Это реальная курсовая
Причем пункты 1,2,3 и были разнесены. Я сварганил ПО по всем 3 пунктам, но дал коллегам сдать раньше меня.
Пояснять надо?
Если память не изменяет, то это 4-й курс специальности "инженер системотехник".

• +0.00 / 0

Цитата: jamaze1 от 16.10.2016 15:44:36Это виртуальная задача или реальная? В реальности междугородние каналы обычно проложены Ростелекомом или местными провайдерами, или могут проложены провайдерами, и это много дешевле самостоятельной прокладки. А при наличии TCP/IP full-mesh получается автоматически.

Цитата: jamaze1 от 16.10.2016 15:44:36

 

Ах да..алгоритм по 2 пункту у меня в 2 раза шустрее работал чем подбор звезды.
Ну и до кучи...по второму пункту нам предлагалось реализовать алгоритм какого-то амерского професора.
Я тупо забил болт на это дело. Придумал свой и намного проще
Решение лежит на поверхности В прямом смысле.

• +0.00 / 0

Цитата: jamaze1 от 16.10.2016 15:44:36Это виртуальная задача или реальная? В реальности междугородние каналы обычно проложены Ростелекомом или местными провайдерами, или могут проложены провайдерами, и это много дешевле самостоятельной прокладки. А при наличии TCP/IP full-mesh получается автоматически.

Цитата: jamaze1 от 16.10.2016 15:44:36

 

Судя по слову "канал", речь идет о среде передачи. IP и TCP -- это с другой оперы, чуток повыше.

• +0.00 / 0

Цитата: adolfus от 16.10.2016 21:13:54Судя по слову "канал", речь идет о среде передачи. IP и TCP -- это с другой оперы, чуток повыше.

Цитата: adolfus от 16.10.2016 21:13:54

 

Судя по "активности"...мыслей у вас нет
А задача проста как 5 копеек.

• +0.00 / 0

Цитата: ip74 от 17.10.2016 06:31:32Судя по "активности"...мыслей у вас нет
А задача проста как 5 копеек.

Цитата: ip74 от 17.10.2016 06:31:32

 

Вы сначала научитесь задачу формулировать сразу и целиком, а не цедить условия по ходу обсуждения, админ РЖД "забыл пояснить".

• +0.02 / 1

Цитата: adolfus от 18.10.2016 08:55:26Вы сначала научитесь задачу формулировать сразу и целиком, а не цедить условия по ходу обсуждения, админ РЖД "забыл пояснить".

Цитата: adolfus от 18.10.2016 08:55:26

 

Беда в том, что примерно в таком ракурсе мне её и сформулировали. Ну и до кучи на лекциях выдали алгоритмы решения.
А намек на координаты я сразу дал.
И еще...решение от амерского професора выглядело просто монструозно. Отсечение точек и т.п.
И собственно абстрагироваться от географических координат - не судьба?
Ах да...педивикия:
Оптимизационная постановка задачи относится к классу очень NP-трудных задач, впрочем как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
Для 40 координатных точек кольцо строилось за 2 секунды (ХТ машинка). 

• -0.01 / 1

Цитата: ip74 от 18.10.2016 11:40:50Беда в том, что примерно в таком ракурсе мне её и сформулировали. Ну и до кучи на лекциях выдали алгоритмы решения.
А намек на координаты я сразу дал.
И еще...решение от амерского професора выглядело просто монструозно. Отсечение точек и т.п.
И собственно абстрагироваться от географических координат - не судьба?
Ах да...педивикия:
Оптимизационная постановка задачи относится к классу очень NP-трудных задач, впрочем как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
Для 40 координатных точек кольцо строилось за 2 секунды (ХТ машинка).

Цитата: ip74 от 18.10.2016 11:40:50

 

Вы решили задачу ПРИБЛИЖЕННО с какой-то странной метрикой расстояния между точками на плоскости.
Можно придумать множество ПРИБЛИЖЕННЫХ алгоритмов. Например выбирать ближайшую непройденную точку в качестве следующей с ПРАВИЛЬНЫМ методом расчета расстояний между точками
20 точек он будет просчитывать сильно быстрее, чем за секунду
И с точки зрения теории алгоритмов, он будет ничем не хуже вашего

Кстати, в теории случайных алгоритмов, ДОКАЗЫВАЕТСЯ, что алгоритм СХОДИТЬСЯ к оптимальному решению.

• +0.01 / 1

Цитата: ip74 от 18.10.2016 11:40:50....Для 40 координатных точек кольцо строилось за 2 секунды (ХТ машинка).

Цитата: ip74 от 18.10.2016 11:40:50

 

Уважаемый, на нобилевку подавали?
Ваш вопрос к «ИТ в России» имеет отношение скорее отрицательное.
Если у вас задача просто построить цикл из всех точек множества и «не пресекаться», и вам не важно, что выглядит это как роза ветров – непонятно куда вы тратите 2 минуты. Одно из самых очевидных решений, перейти в полярные координаты от любой точки внутри множества.
Если вам нужно «что-то приемлемое» - надо сочинять субъективные оценки. Собственно, самый распространенный способ, и скорее всего ваш. И не надо разводить форум «на слабо».    
Если вас интересует Самый Оптимальный путь – решайте классическую задачу. В этом вопросе я больше доверяю американскому профессору, своим преподавателям, и собственному опыту.
PS. ps_ опердил.

• +0.00 / 0

Цитата: ip74 от 16.10.2016 14:06:14Задам простой вопрос.
Это была курсовая работа у меня.
Есть 20 городов. Их надо объединить сетью. 1 вариант - тип звезда. 2 - й вариант - тип кольцо. 3-й вариант - фулл мэш (все со всеми).
Исходно известно - географические координаты (аля 60 градусов широты + 28 градусов долготы) городов.
По второму варианту ваши предложения Алгоритм по 1 и 3 однозначен.

Цитата: ip74 от 16.10.2016 14:06:14

 

Задача ни о чём, надо указать ещё колоссальное количество параметров, только навскидку, для сферических городов в вакууме:
- скорость передачи данных, между ближайшими/дальнейшими/произвольными городами, а также суммарная
- задержка, минимальная/максимальная/средняя, между ближайшими/дальнейшими/произвольными городами
- отказоустойчивость и избыточность, опять же между ближайшими/дальнейшими/произвольными городами
- минимально допустимое время восстановления в случае аварии
- планы по расширению в будущем, а также требования к возможности срочного наращивания ресурсов сети
- бюджет на внедрение и на сопровождение
Это только навскидку в реальности надо на порядок/порядки больше требований.

Для сферически-вакуумного случая я бы начал с двойного кольца с не менее чем двойной избыточностью, а дальше уже плясал бы от него.
Кстати, в условиях ещё не указано, эти три варианта касаются логической или физической организации сети? Иногда они могут отличаться.
Кроме того на практике обычно эти варианты смешиваются.
Плюс ещё и география, в России, например, существуют такие города, как Норильск

• -0.01 / 1

Цитата: pkdr от 17.10.2016 11:50:15Задача ни о чём

Цитата: pkdr от 17.10.2016 11:50:15

 

Нормальный студент (из подачи топикстартера), на такую задачу, должен не курсовую писать, а выдать ровно 4 фразы, и забИть забыть.
1. Задача сводится к «поиск пути в графе».
2. Существует 2 базовых алгоритма решения: в длину и в ширину.
3. О-большое обоих алгоритмов оценивается как факториал от n-1.
4. В зависимости от конкретной предметной области и постановки задачи существуют различные способы существенно сократить среднее время решения задачи.   
ЗЫ. Классическая задача для лабораторной.

• +0.01 / 1

Цитата: Hadan от 17.10.2016 16:03:15Нормальный студент (из подачи топикстартера), на такую задачу, должен не курсовую писать, а выдать ровно 4 фразы, и забИть забыть.
1. Задача сводится к «поиск пути в графе».
2. Существует 2 базовых алгоритма решения: в длину и в ширину.
3. О-большое обоих алгоритмов оценивается как факториал от n-1.
4. В зависимости от конкретной предметной области и постановки задачи существуют различные способы существенно сократить среднее время решения задачи.   
ЗЫ. Классическая задача для лабораторной.

Цитата: Hadan от 17.10.2016 16:03:15

 

Тупой перебор по графу приводит к экспоненциальному времени решения в зависимости от числа городов.
И студент вполне справедливо получает 3- за подобного рода "решение"

• +0.00 / 0

Цитата: ps_ от 17.10.2016 16:08:54Тупой перебор по графу приводит к экспоненциальному времени решения в зависимости от числа городов.
И студент вполне справедливо получает 3- за подобного рода "решение"

Цитата: ps_ от 17.10.2016 16:08:54

 

Я тут слегка дискурс пропустил
Клиент утверждает, что мой вопрос (замечу 1995 года выпуска), больше чем на лабу не тянет.
Но при этом решение задачи не предоставлено.
Банзай! Я жду решения. Дело не в сложности, а в оригинальности
Блин, скоро сломаюсь....устал ждать.

• +0.00 / 0

Цитата: ps_ от 17.10.2016 16:08:54Тупой перебор по графу приводит к экспоненциальному времени решения в зависимости от числа городов.
И студент вполне справедливо получает 3- за подобного рода "решение"

Цитата: ps_ от 17.10.2016 16:08:54

 

Ладно..не буду мучать.
Именно такой подход типа тупого перебора графа и ведет в тупик.
Я решил эту задачу проще. Взял бумажку в клетку и поставил точки в виде координат.
Второй шаг был прост. Я их сложил (координаты). Потом понял, что простое сложение не катит. Добавил умножение на коэфициент (подбирал). Прошло 20 лет, поэтому коэфициент не помню. Вроде как 2 золотых числа.
Алгоритм для кольца работал в 2 раза быстрее чем для звезды.

• +0.00 / 0

Цитата: ip74 от 17.10.2016 17:33:16Ладно..не буду мучать.
Именно такой подход типа тупого перебора графа и ведет в тупик.
Я решил эту задачу проще. Взял бумажку в клетку и поставил точки в виде координат.
Второй шаг был прост. Я их сложил (координаты). Потом понял, что простое сложение не катит. Добавил умножение на коэфициент (подбирал). Прошло 20 лет, поэтому коэфициент не помню. Вроде как 2 золотых числа.
Алгоритм для кольца работал в 2 раза быстрее чем для звезды.

Цитата: ip74 от 17.10.2016 17:33:16

 

А у вас был курс по randomized algorithms (теория случайных алгоритмов) в которой собственно и рассматривается как решать
NP complete  задачи за полиномиальное время?

• +0.00 / 0