Задача, конечно, нехилая…Часть 1

Сообщение №2149 от - 29 декабря 2001 г. 22:54
Тема: Задача, конечно, нехилая…Часть 1

Задача, конечно, нехилая…Часть 1

14 ноября 2001 г. 10:58: №1692 Ana ,
14 ноября 2001 г. 11:16: №1693 Михалыч ,
18 ноября 2001 г. 16:25: №1715 Саша ,
26 ноября 2001 г. 12:24: №1835 Михалыч-Саше ,
27 ноября 2001 г. 11:14: №1853 Михалыч-Саше ,
27 ноября 2001 г. 22:28: №1854 Саша ,
28 ноября 2001 г. 11:54: №1857 Михалыч-Саше ,
28 ноября 2001 г. 17:03: №1860 Ivan-Михалычу ,
29 ноября 2001 г. 07:33: №1866 Composer ,
29 ноября 2001 г. 18:08: №1869 Саша ,

01 декабря 2001 г. 06:06: №1879 Б.Б. ,
01 декабря 2001 г. 09:46:№1880 Михалыч ,
01 декабря 2001 г. 13:59:№1881 Саша ,
02 декабря 2001 г. 09:11:№1882 Б.Б . ,
02 декабря 2001 г. 09:56:№1883 Б.Б . ,
02 декабря 2001 г. 10:27:№1884 Sson ,
03 декабря 2001 г. 09:26:№1886 Б.Б . ,
03 декабря 2001 г. 10:02:№1887 Ana == Б.Б. (№1882) ,
03 декабря 2001 г. 11:10:№1888 Михалыч - Б.Б . ,
03 декабря 2001 г. 12:04:№1890 Б.Б . ,
03 декабря 2001 г. 12:30:№1892 Б.Б . ,
03 декабря 2001 г. 12:39:№1893 Михалыч ,

---------------
Тема Михалыч! Докажите теорему! - Ana 14 ноября 10:58
№1692 от Ana , 14 ноября 2001 г. 10:58:

Уважаемый Михалыч!
Вот достойная для вас задачка.

Рассматривается навигационная система GPS (Global Position System),
Известная также как
Navstar (Navigation System with Time and Ranging), т.е.
Навигационная система определения времени и дальности.
Вычленяем из неё математическую часть и формулируем теорему.

Теорема.
«Минимальное число спутников для обеспечения задач (*) GPS
при условиях (**) равно N (приводите число)..

(*) Задачи:
Для любого момента времени и из любой точки поверхности Земли должны наблюдаться 4 аппарата GPS. (Можете и обобщить задачу и решать для К аппаратов, т.е. видно К аппаратов)

(**)
Орбиты аппаратов GPS круговые.
Высота над поверхностью Земли 20000 км.»

Может быть Вам удастся получить общее решение,
т.е. получить зависимость (таблицу):
«Для К-покрытия необходимо N- аппаратов и не менее).

PS. Думаю, что если Вам удастся найти оптимальное решение по отношению к известным. – Это будет кое что!

-------------------------------------------------------------
№1693 от Михалыч , 14 ноября 2001 г. 11:16:
В ответ на: Михалыч! Докажите теорему! от Ana , 14 ноября 2001 г.:

Два года назад я оппонировал диссертацию Анатолия Леухина из Йошкар-Олы по близкой теме.
По слухам, сейчас у него крупный договор с ИКИ по предлагаемой задаче, по-моему.

Вы предлагаете мне "между прочим" выполнить эту работу в свободное от работы время?
Предложение, конечно, интересное...
А с Толей могу связать Вас напрямую.

-------------------------------------------------------
№1715 от Саша , 18 ноября 2001 г. 16:25:
В ответ на: Докажите теорему! от Михалыч , 14 ноября 2001 г.:

Добрый день, Михалыч!

Как следует из вашего поста, вы знакомы с методами решений подобных задач.
Хотелось бы понять, какие ключевые разделы математики используются при решении подобных экстремальных задач.

Благодарю за ответ!

----------------------------------------------------------
№1835 от Михалыч-Саше , 26 ноября 2001 г. 12:24:
В ответ на: Какая математика? от Саша , 18 ноября 2001 г.:

Саша!
Извините за задержку ответа - был в командировке.
Наше предыдущее общение(?) вынуждает меня в переписке с Вами очень осторожно относиться к словам типа "подобные задачи", извините.
Кроме того, хотелось бы понять, что именно Вас интересует: "используются традиционно" или "могут быть использованы" (или уже иногда используются, не всеми, но есть работы, их преимущества, кто, где, итп?).

Подробности, пожалуйста.

----------------------------------------------------------------
№1843 от Саша , 26 ноября 2001 г. 18:43:
В ответ на: Re: Какая математика? от Михалыч-Саше , 26 ноября 2001 г.:

Михалыч!

адача (теорема) в сообщении № 1692
Сформулирована четко!

В сообщение №1693 вы утверждали, что
«оппонировали диссертацию по близкой теме»

Именно это позволило мне применить «конструкцию»:
«вы знакомы с методами решений подобных задач»

С учетом такого счастливого обстоятельства мне бы очень интересно было бы услышать мнение специалиста по поводу того, какие методы : "используются традиционно" при решении подобных задач.

---------------------------------------------------------------
№1853 от Михалыч-Саше , 27 ноября 2001 г. 11:14:
В ответ на: Re: Какая математика? от Саша , 26 ноября 2001 г.:

Саша!

> Задача (теорема) в сообщении № 1692
> Сформулирована четко!

В этом сообщении меня особенно расстрогала финансовая сторона проекта...

> В сообщение №1693 вы утверждали, что
> «оппонировали диссертацию по близкой теме»

Да, диссертация была посвящена остроумному поиску "оптимальных" ЕСТЕСТВЕННЫХ ориентиров на звездном небе (т.н. "вторичных звездных образований" - авторский термин).

> Именно это позволило мне применить «конструкцию»:
> «вы знакомы с методами решений подобных задач»

Что-то подобное приходилось делать и самому: вместе с коллегами из Германии делали математику для задачи оптимизации расположения видеодатчиков в computer vision.

> С учетом такого счастливого обстоятельства

Думаю, ирония неуместна - получите сдачи.

> мне бы очень интересно было бы услышать мнение специалиста по поводу того, какие методы : "используются традиционно" при решении подобных задач.

Не думаю, что (посильные) подробные ответы на Ваши вопросы заинтересуют учасников Форума. А он, вроде бы, стал модерироваться.

Есть желание - мыльте.
Ваш, Михалыч

---------------------------------------------------------------
№1854 от Саша , 27 ноября 2001 г. 22:28:
В ответ на: Re: Какая математика? от Михалыч-Саше , 27 ноября 2001 г.:

> > Задача (теорема) в сообщении № 1692
> > Сформулирована четко!
> В этом сообщении меня особенно расстрогала финансовая сторона проекта...


Внимательно и несколько раз прочитала текст №1692
Так и не поняла, что вас особенно растрогало!
Финансовой стороны не нашла.
Может быть, мы говорим про разные посты?
Сообщите!

> > В сообщение №1693 вы утверждали, что
> > «оппонировали диссертацию по близкой теме»
> Да, диссертация была посвящена остроумному поиску "оптимальных" ЕСТЕСТВЕННЫХ ориентиров на звездном небе (т.н. "вторичных звездных образований" - авторский термин).

Но это же не имеет никакого отношения к задаче, сформулированной в №1692

> > Именно это позволило мне применить «конструкцию»:
> > «вы знакомы с методами решений подобных задач»
> Что-то подобное приходилось делать и самому: вместе с коллегами из Германии делали математику для задачи оптимизации расположения видеодатчиков в computer vision.

Похоже, что и это не имеет отношение к теме!

> > С учетом такого счастливого обстоятельства
> Думаю, ирония неуместна - получите сдачи.

Очень удивлена, что это вы восприняли как иронию!
Про «сдачу» просто ШОК!

> > мне бы очень интересно было бы услышать мнение специалиста по поводу того, какие методы : "используются традиционно" при решении подобных задач.
> Не думаю, что (посильные) подробные ответы на Ваши вопросы заинтересуют учасников Форума. А он, вроде бы, стал модерироваться.

Разве я упоминала про степень подробностей ответов.
И вы разве до сих пор не поняли, что задача чисто математическая (это про модерирование). Кстати по моим сведениям (как говорит Кim- сорока на хвосте принесла) математика «традиционная» и очень интересная!!! Вот я и думала у вас подробности есть.

---------------------------------------------------------------
№1857 от Михалыч-Саше , 28 ноября 2001 г. 11:54:
В ответ на: Re: Какая математика? от Саша , 27 ноября 2001 г.:

Саша!
Ну нет у меня ни времени ни желания препираться...
Желаете по существу - пожалуйста.

1. одни и те же математические методы и теории могут лежать в основе решения задач, поставленных в РАЗЛИЧНЫХ предметных областях. Математика часто является ивариантной относительно предметных постановок задач. Слышали о таком феномене?
И позвольте все-таки мне решать, какие задачи решаются (могут быть решены) похожими методами, а какие, на мой взгляд, нет. Вы же моего мнения спрашиваете.
(Вы же интересуетесь математикой, а не спутниками. Так я понял Ваш вопрос.)

2. я не вижу разницы между задачей построения оптимальной пространственной конфигурации датчиков для (шарового) "объекта" на карданном подвесе для "похожего" критерия видимости.
Да, на "объекте" нет лесов и океанов, Саш и Михалычей. Ну и что?

3. Да, математика интересная и весьма "крутая" - от кватернионов до теории представлений групп.

4. Решение КОНКРЕТНОЙ прикладной задачи в интересах фирмы или "народного хозяйства" оформляется соответствующими финансовыми соглашениями,
потому, что получение ЗАКОНЧЕННОГО решения такой задачи - это время, люди и деньги.

5. Хотите более подробную информацию (бесплатную, разумеется) о используемых подходах, методах, командах - пишите. Чем смогу - поделюсь.
Нет - значит нет.

Ваш Михалыч.

----------------------------------------------------------------
№1860 от Ivan-Михалычу , 28 ноября 2001 г. 17:03:
В ответ на: Re: Такая математика от Михалыч-Саше , 28 ноября 2001 г.:

Уважаемый Михалыч.

Задача, сформулированная в сообщении № 1692, действительно, весьма интересна с позиций математики.

Возникнув в той форме, в которой она представлена на форуме, она наверняка станет вечной задачей Человечества, видоизменясь и «варьируясь».

На форуме представлена простейшая формулировка.
Задача относится к новой отрасли знаний и приложений математики с известной уже многим аббревиатурой ГИС ( ГеоИнформационныеСистемы).
Весьма много (в основном «прикладного») «народа» включилось в эту тематику.
И мне представляется, что решение фундаментальных задач ГИС может быть интересным участникам форума.

Особенность этой задачи заключается в том, что, имея внешний вид как геометрическая задача, она представляет собой задачу на динамику системы (невзаимодействующих) материальных точек.
Почему я пишу вам?
Я думаю, что Саша вполне резонно среагировала на ваше текст, предположив, что вы можете открыть интересную дискуссию о направлениях решений этой задачи.
Я присоединяюсь к её просьбе.

С уважением Иван Ларионов.

-----------------------------------------------------------------------------------
№1866 от Composer , 29 ноября 2001 г. 07:33:
В ответ на: Re: Какая математика? от Саша , 27 ноября 2001 г.:

Рассмотрим сферу (Земля) и точку вне неё (спутник).
С каждым спутником можно связать область на сфере, из которой он виден (область видимости). Предполагается, что спутник виден из точки на сфере, если он расположен выше касательной плоскости, проведённой в этой точке.

Отсюда нетрудно понять, что есть область видимости. Проведём из спутника всевозможные касательные прямые к сфере. Они образуют конус. Пересечение этого конуса со сферой есть окружность, которая делит сферу на 2 части. Область сферы, ограниченная этой окружностью и находящаяся прямо под спутником (под колпаком), и есть область видимости. Она представляет собой сферический круг (шапочку). Размер шапочки (радиус) легко найти (по формулам из справочника), зная радиус Земли и высоту спутника.

Таким образом, задача может быть переформулирована таким образом.
Имеется сфера радиуса R. Требуется найти наиболее экономное покрытие её шапочками радиуса r такое, чтобы каждая точка сферы принадлежала бы как минимум 4 элементам покрытия (шапочкам). (*)

Это "статическая" задача.
Динамика состоит в том, что центры каждой из шапочек с течением времени движутся на сфере по большим окружностям. То есть в каждый момент времени покрытие меняется. При этом необходимо, чтобы свойство (*) имело место быть всегда.

Это только переформулировка. Как решать эту задачу, не понятно (мне).
Наверное, сначала надо решить "статическую" задачу.
Тематика таких задач (об экономных покрытиях) связано с понятием метрической энтропии (в данном случае, на сфере).

Можно что-нибудь поискать об этом.
А, вообще, задача, конечно, нехилая... Правда, и очень интересная.

-------------------------------------------------------------------------------------
№1869 от Саша , 29 ноября 2001 г. 18:08:
На: №1866 от Composer , 29 ноября 2001 г. 07:33:

Рассмотрим сферу (Земля) и точку вне неё (спутник).
С каждым спутником можно связать область на сфере, из которой он виден (область видимости). Предполагается, что спутник виден из точки на сфере, если он расположен выше касательной плоскости, проведённой в этой точке.
Отсюда нетрудно понять, что есть область видимости. Проведём из спутника всевозможные касательные прямые к сфере. Они образуют конус. Пересечение этого конуса со сферой есть окружность, которая делит сферу на 2 части. Область сферы, ограниченная этой окружностью и находящаяся прямо под спутником (под колпаком), и есть область видимости. Она представляет собой сферический круг (шапочку). Размер шапочки (радиус) легко найти (по формулам из справочника), зная радиус Земли и высоту спутника.

Вероятно, что «радиус шапочки» можно считать входным параметром задачи. Ваш вариант - предельное (максимальное) значение радиусов То же и о высоте над поверхностью Земли. Высота нужна лишь для задания угловой скорости движения точек «по окружностям». Наверное, можно все нормировать, и рассматривать задачу покрытия единичной сферы.

Таким образом, задача может быть переформулирована таким образом.
Имеется сфера радиуса R. Требуется найти наиболее экономное покрытие её шапочками радиуса r такое, чтобы каждая точка сферы принадлежала бы как минимум 4 элементам покрытия (шапочкам). (*)

Постановка задачи в №1692 относится к навигационным системам типа Navstar (Navigation System with Time and Ranging) и российского аналога ГЛОНАСС (Глобальная Навигационная Спутниковая Система). Существует масса подобных задач и для систем связи, и вероятно будут системы экологического мониторинга.

Я «пошарила» в сети, чтобы получить представление о количестве спутников в реальных системах.
Получилась очень интересная картина.
Первая коммерческая система глобальной сотовой связи «Iridium» уже создана и успела разориться.

«Трубка» (телефон) этой системы стоит около 500$, минута разговора 1.5$. Но вроде бы систему за бесценок купило МинОбороны США.
Число спутников в этой системе 111.

Сейчас «раскручивается другой проект системы «Teledesic».
Число спутников 288
(В первоначальном варианте было втрое больше).

Меня поразило, что вывод спутников этой системы на орбиту осуществляется с борта самолета.
(Информацию по «Teledesic» записала на форуме «Наука и Образование». Мне кажется она интересной «в принципе».)

К чему я всё это?
Вероятно, целесообразно сначала понять как решить задачу «одноразового покрытия».

Это "статическая" задача.
Динамика состоит в том, что центры каждой из шапочек с течением времени движутся на сфере по большим окружностям. То есть в каждый момент времени покрытие меняется. При этом необходимо, чтобы свойство (*) имело место быть всегда.

Это только переформулировка. Как решать эту задачу, не понятно (мне).
Наверное, сначала надо решить "статическую" задачу.
Тематика таких задач (об экономных покрытиях) связано с понятием метрической энтропии (в данном случае, на сфере).


Про метрической энтропии на сфере ничего не слышала. .
Очевидно, что система покрытия сферы должна быть симметричной.
Отсюда понятно, что как-то должны работать теории, описывающие понятия симметрии..
Мне не ясно, система должна оставаться все время симметричной или как-то деформируясь вновь возвращаться к симметричной.

Можно что-нибудь поискать об этом.
А, вообще, задача, конечно, нехилая... Правда, и очень интересная.

----------------------------------------------------------------------------------
№1879 от Б.Б. , 01 декабря 2001 г. 06:06:
На: Задача, конечно, нехилая. от Саша , 29 ноября 2001 г.:

Очевидно, орбиты спутников должны удовлетворять ряду прикладных требований.
Я в этом не разбираюсь, но слышал, что все спутники связи (ретрансляторы) - геостационарны.

А про GPS я читал, что для решения задач навигации контакта с одним спутником мало. Даже "бытовые" (автомобильные) GPS выполняют все свои функции, только если видят три спутника одновременно. (А если на клиенте функционирует компас, вроде бы достаточно и двух).

Так что задача может оказаться вовсе и не о покрытии сферы шапочками.

---------------------------------------------------------------------------------
да нехилая она, нехилая
№1880 от Михалыч , 01 декабря 2001 г. 09:46:
В ответ на: Задача, конечно, нехилая. от Саша , 29 ноября 2001 г.:

Задача трудная даже в статике. Знал бы как делать - давно бы договор заключил.
Прикладное значение "аграмадное", можно не объяснять.
И про ГИС я в курсе. (Кстати, одно из мест, где я работаю - кафедра геоинформатики).
Оставим пока приклад в покое. Там и с математикой куча проблем "в тему". Причем вроде бы и не делал этого никто.
Например, хорошо бы было, если бы наша вселенная была плоской. Окружность аппроксимируется правильным многоугольником с любой точностью, что позволяет строить дискретные корреляторы, использовать ДПФ и проч.
А сферу гладко причесать нельзя. И "правильная" дискретизация сферы невозможна, за исключением всяких там икосаэдров и т.п.
Как выглядит "сферический коррелятор", "сферическое ДПФ", неясно. Это - для дальнейшей задачи ориентации, в предположении, что "какая-то" пространственная конфигурация ориентиров все-таки построена.
Как мне кажется, оптимальное по числу ориентиров решение достигается при "многоэтажном" расположении ориентиров (спутников).
Не знаю, почему. Некоторые зацепки - были при знакомстве с
Дж.Конвей, Н. Слоэн. "Упаковки шаров, решетки и группы" (в 2т.), Мир, 1990.
Материала там много, математика тяжелая, но без явной привязки именно к сформулированной задаче.
То есть, попытаться найти "многоэтажный" оптимум, а потом подвинуть всю конструкцию на один этаж с некоторой потерей оптимальности.
Поковыряться можно, конечно. В одиночку не хочется.
А что, есть желающие?

------------------------------------------------------------------------
Re: Задача, конечно, нехилая.
№1881 от Саша , 01 декабря 2001 г. 13:59:
В ответ на: Re: Задача, конечно, нехилая. от Б.Б. , 01 декабря 2001 г.:

Очевидно, орбиты спутников должны удовлетворять ряду прикладных требований.

В сообщении №1692, с которого началась эта цепочка было сформулировано требование для конкретной навигационной системы

((*) Задачи: Для любого момента времени и из любой точки поверхности Земли должны наблюдаться 4 аппарата GPS. (Можете и обобщить задачу и решать для К аппаратов, т.е. видно К аппаратов))

Composer ( в №1866) сделал шаг в математической формализации задачи, оставив это требование 4-хкратного покрытия.
Но вполне обосновано отметил, что задачку необходимо начинать решать со «статического» варианта.
И, как я понимаю, с однократного покрытия.
Это позволит получить нижнюю оценку числу точек (при любой кратности покрытия) и позволит оценивать близость получаемых решений к «оптимальному» при возникновении «прикладных требований» (ограничений).

Обращает на себя внимание «забавное совпадение». И «Navstar» и ГЛОНАСС проектировались (вероятно) несколько десятков лет назад, но орбитальные архитектуры их практически абсолютно совпали.
Что это? Единственность оптимального решения (при технических ограничениях) или просто «разумное» решение, интуитивно (технически) близкое к оптимальному

Я в этом не разбираюсь, но слышал, что все спутники связи (ретрансляторы) - геостационарны.


Для связи с геостационарными спутниками нужна «тарелка», диаметром порядка полметра. В карман не положишь.

Для «глобального покрытия Земли связью через стационары достаточно тех спутников. Однако для географических широт выше 80 с чем то градусов доступ невозможен.

Я писала в сообщении № 1869, что некоторые материалы из Интернета записала на форуме «Наука и образование»
(№№ 196,197,198).

А про GPS я читал, что для решения задач навигации контакта с одним спутником мало. Даже "бытовые" (автомобильные) GPS выполняют все свои функции, только если видят три спутника одновременно. (А если на клиенте функционирует компас, вроде бы достаточно и двух).


В №1866 я, как мне показалось, ясно обратила внимание на то, что кратность покрытия – это какой-то внутренний параметр математической формализации задачи.
Вот как её формализовать – это вопрос.

Так что задача может оказаться вовсе и не о покрытии сферы шапочками.

А чем?

---------------------------------------------------------
Re: Задача, конечно, нехилая.
№1882 от Б.Б . , 02 декабря 2001 г. 09:11:
В ответ на: Re: Задача, конечно, нехилая. от Саша , 01 декабря 2001 г.:

Простите, я забыл, что в вашем оригинальном сообщении упоминалась кратность покрытия.
А задача с однократным покрытием показалась мне слишком далекой от приложения, поэтому я и решил напомнить.

Скажите, а кратность покрытия - единственное существенное требование? Орбиты могут лежать в произвольных плоскостях, иметь произвольный радиус?

Разве нет требований к угловому расстоянию между спутниками, видимыми из данной точки?
Мне просто кажется, что оптимальная практически реализуемая конфигурация может оказаться очень далека от идеальной.

И наверное "забавное совпадение" - это "интуитивно разумное" технически реализуемое (и не дорогое!) решение.
И оно вполне возможно даже не удовлетворяет условию полного покрытия, т.е. есть зоны, которые периодически (или постоянно) вне сервиса.

Сильно подозреваю, что задачу решали на модели с заранее заданными "прикладными ограничениями".

Да, никаких идей по поводу решения "идеальной" задачи у меня нет. Я просто подчеркиваю ее отличия от "прикладной", а также сложность и первой и второй.

--------------------------------------------------------
Re: Кстати
№1883 от Б.Б . , 02 декабря 2001 г. 09:56:
В ответ на: Re: Задача, конечно, нехилая. от Б.Б. , 02 декабря 2001 г.:

Если брать совсем "идеальную" задачу - однократное покрытие шапочками без всяких ограничений, статическое, то вроде бы достаточно пяти больших шапочек. А может и четырех. Нет шарика под рукой, чтоб на нем порисовать. Единственное ограничение - радиус шапочки меньше радиуса сферы.

Кстати, если взять Солнце, Луну и Полярную звезду, то в северном полушарии что-то одно из них видно почти всегда и везде ;)

----------------------------------------------------------
Re: Кстати
№1884 от Sson , 02 декабря 2001 г. 10:27:
В ответ на: Re: Кстати от Б.Б. , 02 декабря 2001 г.:

> Кстати, если взять Солнце, Луну и Полярную звезду, то в северном полушарии что-то одно из них видно почти всегда и везде ;)

Во-первых. Это неверно.
Во-вторых. Какое отношение имеет к рассматриваемой задаче?

------------------------------------------------------------
Re: Кстати
№1886 от Б.Б . , 03 декабря 2001 г. 09:26:
В ответ на: Re: Кстати от Sson , 02 декабря 2001 г.:

> > Кстати, если взять Солнце, Луну и Полярную звезду, то в северном полушарии что-то одно из них видно почти всегда и везде ;)
> Во-первых. Это неверно.
Я имел в виду "почти" не в смысле меры, поэтому мое предложение ни истинным ни ложным не является.

> Во-вторых. Какое отношение имеет к рассматриваемой задаче?
Я как раз пытаюсь выяснить, какая задача рассматривается.

Все мои сообщения в этой теме - это намеки на то, что решать эту задачу, пока не даны ограничения параметров орбит - бессмысленно.

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

----------------------------------------------------------------
Задача, конечно, нехилая.
№1887 от Ana == Б.Б. (№1882) , 03 декабря 2001 г. 10:02:
В ответ на: Re: Кстати от Б.Б. , 03 декабря 2001 г.:

Как мне показалось, в вашем сообщении выражено «смущение» по трем аспектам.

ПЕРВОЕ.
О «далёкости» от приложений.
По этому поводу весьма убедительно сказано у Михалыча (№1880)

Прикладное значение "аграмадное", можно не объяснять.
Оставим пока приклад в покое.
Там и с математикой куча проблем "в тему".
Причем вроде бы и не делал этого никто.

ВТОРОЕ.
Ограничений, которые возникают в приложениях много. Хороших и разных.
Но многие (пусть некоторые) из этих ограничений врЕменные.
Где-то читала, что в свое время (может быть как раз на момент начала проектирования рассматриваемых навигационных систем) М.Ботвинник написал письмо в ЦК КПСС с просьбой выделить 10 000$ для его шахматной школы на покупку АТ386 для работ над программами игры в шахматы.

ТРЕТЬЕ.
В сообщении «Кстати» №1886 вы (не поняла совершенно зачем) упомянули северное полушарие.
По «поводу полушария» можно попутно заметить, что вполне уместны постановки задачи об оптимальных покрытиях заданных регионов.
Например, только северного полушария.
Но это, как модно говорить - отдельная песня. С эллиптическими орбитами.

--------------------------------------------------------
О задачах
№1888 от Михалыч - Б.Б . , 03 декабря 2001 г. 11:10:
В ответ на: Re: Кстати от Б.Б. , 03 декабря 2001 г.:

Уважаемый Б.Б.!
Думаю, что Вы наиболее близко подошли к пониманию того, что задача "о шапочках", даже если и будет решена,
неэквивалентна поставленной прикладной задаче. Гипотетическое оптимальное решение задачи о 4-покрытии не будет оптимальным для задачи
GPS. И решающую роль играют как раз прикладные ограничения. Допустим, что оптимальное по числу ориентиров решение найдено. Далее, а КАК ориентироваться по четырем точкам?
Думаю, что есть прикладное ограничение не только на число ориентиров, но и на их конфигурацию.

Я не занимался именно поставленной задачей, но имел отношение к "инвертированным" задачам.
Именно, Объект (субъект) активно ищет ориентиры и определяется по ним. Здесь обратная ситуация: объект пассивен, ориентиры активны.
Насколько эта инвертированная постановка отражается на методах и подходах к решению - не знаю.
Допустим, что методы и проблемы сходны.

Тогда об "инвертированной" задаче.
Четырех ориентиров достаточно. Но не всяких!
Видимая конфигурация РЕАЛЬНО должна удовлетворять противоречивым(!) требованиям.
Во-первых, она должна быть "локально-симметрична" для применения корреляционных методов обнаружения ориентиров.
Правильный треугольник, например.
Во-вторых, "асимметричной" для идентификации параметров (грубо говоря, для понимания того, по какую именно
из равных сторон треугольника находится (активный) объект). Необходим четвертый ориентир, ассимеризирующий конфигурацию.
Тогда задача о покрытиях, в первом приближении, расслаивается. Ищутся ДВЕ точечные конфигурации - "локально-симметричная" и "асимметризирующая".
Это в статике. А в динамике появляющиеся при вращении новые точки локально-симметричной
системы могут играть асимметризирующую роль.
Конечно, задача о покрытии, без ограничений на конфигурацию интересна и математически
вполне самодостаточна.
Но мне все-таки кажется, что прикладные ограничения на алгоритмы ориентации переводят сформулированную авторами задачу в совершенно другую,
с другими критериями оптимальности.
Все четыре(?) задачи (про шапочки, статическая и динамическая; то же с ограничениями на конфигурацию)- трудные, на мой взгляд.
Трудные и ОЧЕНЬ дорогие.
Поэтому, оптимизма в отношении решения этих задач на Форуме методом "мозгового штурма" у меня нет.
Кстати, последний метод предполагает категорический запрет на критику идей участников и модерирование в стиле "это не относится к поставленной задаче".

--------------------------------------------------------
Извинения, разъяснения.
№1890 от Б.Б . , 03 декабря 2001 г. 12:04:
На: Задача, конечно, нехилая. от Ana== Б.Б. (№1882) , 03 декабря 2001 г

Во-первых, прошу прощения за "полушарие" - это в самом деле был бред, далекий от темы. (хотя в свете гипотезы о симметричности покрытия....)

Во-вторых, прошу прощения за невнятный стиль дискусси вообще.

Мое смущение вызвано тем, что задачу попытались сильно редуцировать.
Выражаю сомнение в том, что задача однократнаго покрытия сферы (неподвижными) областями произвольного радиуса, меньшего чем радиус сферы, представляет ценность.

Ответ: минимальное число областей - 5. Что дальше? Если решать задачу покрытия N областями, минимизируя радиус областей, то для каждого N будет своя оптимальная конфигурация.

Если задан радиус (радиусы) областей, и надо минимизировать N, то конфигурация не единственна.

В статическом случае мы можем сэкономить спутник скорее за счет увеличения радиуса орбит, чем за счет изменения конфигурации. Опять спрашиваю - каков максимальный радиус орбиты? Каков характерный размер зоны видимости?
Есть ли какие-то идеи, как перейти к динамическому случаю от статического?

Еще "кстати". Здесь недавно промелькнул вопрос о разбиении сферы на многоугольники. Он имел отношение к этой задаче?

На шестиугольники нельзя разбить. Это просто доказать с формулой Эйлера.
Разбиения типа "футбольный мяч" существуют на сколь угодно большое число многоугольников.
Пятиугольников в таких разбиениях всегда 12, а шестиугольников - много. Общего метода построения таких разбиений вроде бы нет.

-----------------------------------------------------
Re: О задачах
№1892 от Б.Б . , 03 декабря 2001 г. 12:30:
В ответ на: О задачах от Михалыч - Б.Б. , 03 декабря 2001 г.:

> Конечно, задача о покрытии, без ограничений на
> конфигурацию интересна и математически
> вполне самодостаточна.
> Но мне все-таки кажется, что прикладные ограничения на
> алгоритмы ориентации переводят сформулированную авторами
> задачу в совершенно другую,
> с другими критериями оптимальности.

Спасибо Вам, Михалыч. Именно об этом я и твержу, но у меня плохо получается выразить эти мысли.
О методах ориентирования и о технологиях спутниковой связи я не знаю ничего, поэтому и требую все ограничения как входные параметры.

Что касается "задачи о покрытии, без ограничений на конфигурацию":
За эти выходные я попытался ознакомиться с задачами, близкими (и более простыми), на мой взгляд, к "задаче о шапочках". Это задачи о покрытии круга кругами и о "детекторе лучей". (Если Вы не знаете о чем речь, и Вам интересно, то я сформулирую в отдельной ветке). Задачи для меня оказались невероятно сложны.
Поэтому и над "шапочками" я размышлять прекращаю.

-----------------------------------------------------------
Re: О задачах
№1893 от Михалыч , 03 декабря 2001 г. 12:39:
В ответ на: Re: О задачах от Б.Б. , 03 декабря 2001 г.:

> Что касается "задачи о покрытии, без ограничений на конфигурацию":
> За эти выходные я попытался ознакомиться с задачами, близкими (и более простыми), на мой взгляд, к "задаче о шапочках". Это задачи о покрытии круга кругами и о "детекторе лучей". (Если Вы не знаете о чем речь, и Вам интересно, то я сформулирую в отдельной ветке). Задачи для меня оказались невероятно сложны.
> Поэтому и над "шапочками" я размышлять прекращаю.

Лучше по e-mail.
Иначе опять пойдут разговоры об "увиливании" от решения предложенной задачи.
А появится что-нибудь интересное в дебюте - поставим на Форум.

------------------------------------------


Отклики на это сообщение:

О покрытии Земли «шапочками».

В этой теме (вверху) есть сообщение №1866 от Composer , 29 ноября 2001 г. 07:33:
Я привожу его копию (полностью) внизу после черты из плюсиков.

Дело в том, что сейчас в книжных магазинах лежит книжка.
Горностаев Ю.М., Соколов И.И., Невдяев Л.М.
«Перспективные спутниковые системы связи»

В этой книжке (на стр 79) приводится частное решение задачи о покрытии «шапочками» радиуса 359 км на поверхности Земли.
Авторы утверждают, что для этого частного случая (359 км) оптимальное покрытие требует 2084 «шапочки».
«Упакковка» шапочек создается при их гексогональной структуре с одной центральной «шапочко».


+++++++++++++++++++++++++++++++++++++++++++++++++
№1866 от Composer , 29 ноября 2001 г. 07:33:
В ответ на: Re: Какая математика? от Саша , 27 ноября 2001 г.:

Рассмотрим сферу (Земля) и точку вне неё (спутник).
С каждым спутником можно связать область на сфере, из которой он виден (область видимости). Предполагается, что спутник виден из точки на сфере, если он расположен выше касательной плоскости, проведённой в этой точке.

Отсюда нетрудно понять, что есть область видимости. Проведём из спутника всевозможные касательные прямые к сфере. Они образуют конус. Пересечение этого конуса со сферой есть окружность, которая делит сферу на 2 части. Область сферы, ограниченная этой окружностью и находящаяся прямо под спутником (под колпаком), и есть область видимости. Она представляет собой сферический круг (шапочку). Размер шапочки (радиус) легко найти (по формулам из справочника), зная радиус Земли и высоту спутника.

Таким образом, задача может быть переформулирована таким образом.
Имеется сфера радиуса R. Требуется найти наиболее экономное покрытие её шапочками радиуса r такое, чтобы каждая точка сферы принадлежала бы как минимум 4 элементам покрытия (шапочкам). (*)

Это "статическая" задача.
Динамика состоит в том, что центры каждой из шапочек с течением времени движутся на сфере по большим окружностям. То есть в каждый момент времени покрытие меняется. При этом необходимо, чтобы свойство (*) имело место быть всегда.

Это только переформулировка. Как решать эту задачу, не понятно (мне).
Наверное, сначала надо решить "статическую" задачу.
Тематика таких задач (об экономных покрытиях) связано с понятием метрической энтропии (в данном случае, на сфере).

Можно что-нибудь поискать об этом.
А, вообще, задача, конечно, нехилая... Правда, и очень интересная.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100