Устройство для решения геометрических и комбинаторных задач
Изобретение относится к устройствам для решения геометрических и комбинаторных задач маршрутного типа. Данное устройство позволяет решать задачи типа задачи коммивояжера. Цель изобретения - повышение точности. Устройство состоит из основания 1, соединенного со столом с помощью пантографа 2, на которое устанавливается вертикальная поворотная штанга 4 с втулкой 20, жестко скрепленной с втулкой 21, являющейся направляющей для штанги 17. Со штангой 17 шарнирно соединена втулка 15, являющаяся направляющей для штанги 12. Со штангой 12 шарнирно соединен осветитель 7, снабженный объективом 8 и непрозрачной блендой 9, который служит для получения изображения эллипса (конического сечения светового потока ) на карте местности, закрепленной на рабочем столе. Для задания направления , перемещая по которому штангу 12 вместе с осветителем 7 добиваются увеличения (уменьшения) размеров эллипса без изменения положения его центра на карте, в состав устройства входят нижний 11 и верхний 16 транспортиры и шкалы 22 и 23, а для задания направления большой оси эллипса на карте местности - транспортир 3. Устройство позволяет формировать на карте изображение эллипса любой заданной условиями задачи формы и размера и ориентированного своей большой осью в требуемом направлении. 5 ил. о .19 гСО со Ci О СО ОО
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (5114 G06G I 16
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н А BTOPCKOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4064012/24-24 (22) 30.04.86 (46) 07.09.87. Бюл. № 33 (72) А. А. Зайцев (53) 681.3(088.8) (56) Патент США № 4483073, кл. 33 — 1, 1982.
Авторское свидетельство СССР № 1171810, кл. G 06 G 1/16, 1981. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ГЕОМЕТРИЧЕСКИХ И КОМБИНАТОРНЫХ
ЗАДАЧ (57) Изобретение относится к устройствам для решения геометрических и комбинаторных задач маршрутного типа. Данное устройство позволяет решать задачи типа задачи коммивояжера. Цель изобретения повышение точности. Устройство состоит из основания 1, соединенного со столом с помощью пантографа 2, на которое устанавливается вертикальная поворотная штанга 4 с втулкой 20, жестко скрепленной с втулкой
„„SU„„1336038 А1
21, являющейся направляющей для штанги 17. Со штангой 17 шарнирно соединена втулка 15, являющаяся направляющей для штанги 12. Со штангой 12 шарнирно соединен осветитель 7, снабженный объективом 8 и непрозрачной блендой 9, который служит для получения изображения эллипса (конического сечения светового потока) на карте местности, закрепленной на рабочем столе. Для задания направления, перемещая по которому штангу 12 вместе с осветителем 7 добиваются увеличения (уменьшения) размеров эллипса без изменения положения его центра на карте, в состав устройства входят нижний 11 и верхний 16 транспортиры и шкалы 22 и 23, а для задания направления большой оси эллипса на карте местности — транспортир
3. Устройство позволяет формировать на карте изображение эллипса любой заданной условиями задачи формы и размера и ориентированного своей большой осью в требуемом направлении. 5 ил.
1336038
Изобретение относится к устройствам для решения геометрических и комбинаторных задач маршрутного типа и может быть использовано в организациях, связанных с необходимостью оперативного решения задач определения такой последовательности посещения городов или иных объектов транспортным средством, которая минимизирует суммарные потребные энергозатраты на обход при возможных заданных ограничениях.
Цель изобретения — повышение точности решения задачи.
Применение устройства при решении задач позволяет непрерывно изменять размеры и форму эллипсов, что существенно повышает оперативность и точность получаемого решения, так как в процессе решения не требуется проводить дополнительную аппроксимацию изолинии уровня при попадании очередной исследуемой точки в интервал между двумя соседними концентрическими эллипсами. Кроме того, исключается особенно трудоемкая операция аппроксимации целого семейства концентрических эллипсов определенной формы, задаваемой соотношением функций влияния.
На фиг. 1 изображено коническое сечение, представляющее собой правильный эллипс, получаемый проекцией светового потока на карту местности (при фиксированном значении угла полураствора конуса светового потока р и фиксированном соотношении полуосей эллипса, равного отношению функций влияния, форма эллипса задается углом наклона а оси конуса светового потока и плоскости карты местности); на фиг. 2 — схема взаимного расположения конуса светового потока к плоскости рабочей карты; на фиг. 3 — предлагаемое устройство, общий вид; на фиг. 4 — устройство в ра.. очем положении; на фиг. 5 — порядок выбора очередной точки маршрута по эвристическому правилу «Иди в ближайшую точку», Устройство содержит следующие элементы (фиг. 3). Основание 1 соединено с помощью пантографа 2 со столом, на котором размещается карта местности с нанесенными на нее точками обхода. Пантограф 2 обеспечивает при перемещении основания 1 по карте местности постоянство выбранного направления. Для установки заданного условиями задачи направления ориентации эллипсов в состав устройства входят транспортер 3, жестко скрепленный с вертикальной поворотной штангой 4, риска 5, нанесенная на основание 1 и фиксирующий элемент 6, фиксирующий положение вертикальной поворотной штанги 4 в нужном направлении. Для задания требуемой формы эллипса устройство содержит осветитель
7, снабженный объективом 8 и непрозрачной блендой 9 для задания угла в полураствора светового потока (фиг. 2). Осветитель фиксируется фиксирующими элемента5
55 ми 10 под требуемым углом а (фиг. 4), откладываемым с помощью прозрачного транспортера 11, жестко скрепленного с корпусом осветителя 7. Для отсчета угла а на подвижную штангу 12 нанесена риска 13. 3афиксированный осветитель 7 может перемещаться вместе со штангой 12 вдоль направляющей втулки 14. В случае необходимости штанга 12 может быть зафиксирована фиксирующим элементом 15. Транспортир служит для задания направления движения штанги 12, перемещая по которому можно изменять размеры эллипса без изменения его формы, а также без изменения положения его центра на карте местности. Транспортир 16 жестко скреплен с горизонтальной штангой 17. Фиксирующий элемент 18 фиксирует положение направляющей втулки 14 в заданном направлении. Это направление задается углом а (фиг. 4). Для установки угла у на штангу нанесена риска 19.
Для компенсации ухода центра эллипса из заданной точки при указанных изменениях положение осветителя 7 и штанги 12, приводящих устройство в рабочее положение, служат две взаимно перпендикулярные направляющие втулки 20 и 21, положение штанг определяется по шкалам 22 и 23, нанесенным соответственно на вертикальную 4 и горизонтальную 17 штанги, фиксирующие элементы 24 и 25 предназначены для фиксации этих штанг. Для приведения центра эллипса в исследуемую точку на объективе
8 осветителя 7 нанесено перекрытие, проекция которого на карте местности обозначена позицией 26. Для получения информации о размерах эллипса служит шкала 27, нанесенная на штангу 12.
Все отсчеты на прямолинейных шкалах
22, 23 и 27 снимаются от нулевых отметок до пересечения с кромками соответствующих втулок 20, 21 и 14. Все отсчеты на транспортных шкалах 11 и 16 снимаются от нулевых отметок, за которые принимают направление отвесной линии в исходном положении, до рисок 13 и 19, нанесенных на штанге 12.
Для приведения устройства в рабочее положение необходимо на транспортирной шкале 16 установить значение угла у, на транспортирной шкале 11 — значение угла а, горизонтальную штангу 17 совместить вправо вдоль направляющей втулки 21 на величину,1, а направляющую втулку 20 вниз на величину h. Отсчеты в этом случае снимаются соответственно по шкалам 16, 11, 23 и 22. Формулы для определения величин у, a, l и Ьиспользуются для градуировки соответствующих шкал G>, б, бз в зависимости от заданного коэффициента К (величина отношения функций влияния — — — —, задаваемая условиями задачи). а1. la
OIz./да
После градуировки шкал предлагаемого устройства установка соответствующих коi,36038 эффициенту К значений угловых 7 и а линейных, 1 и л h величин сводится фактически к установке на всех этих шкалах непосредственно значения задаваемого условиями задачи коэффициента К.
Работу устройства продемонстрируем на примере решения геометрической задачи коммивояжера. В этом случае устройство работает следующим образом.
Исходное положение устройства показано на фиг. 3. На всех шкалах выставляются нулевые отметки. При этом проекция светового потока представляет собой круг.
Вертикальная штанга 4 поворачивается вокруг своей оси в заданном направлении, устанавливаемом с помощью транспортира 3 по риске 5 и фиксируется фиксируюгцим элементом 6. Затем,перемещая Основание 1 с помощью пантографа 2, добиваются того, чтобы центр круга, определяемый проекцией 26 перекрестья на карту, совместился с первой исследуемой точкой
Далее заданную величину отношения функций влияния (коэффициент К) устанавливают на соответствующих шкалах с целью приведения устройства в рабочее положение. Указанное приведение устройства в рабочее положение схематично изображено на фиг. 4 (всего требуется установить значение коэффициента К на четырех шкалах
G, бь бз и G4.).
Выбор ближайшей точки маршрута осуществляется с помощью увеличения (уменьшения) размеров эллипса заданной формы и ориентированного в заданном направлении (фиг. 6). Такое увеличение (уменьшение) размеров эллипса достигается перемещением штанги 12 с зафиксированным на ней осветителем 7 вдоль направляющей втулки 14. При этом, чем меньше размер эллипса, который накрывает точку, тем меньше затрат требуется для перехода из центра эллипса в эту точку и, следовательно, такая точка будет ближайшей. Ьлижайшей к центру будет точка б, а не точка а, так как точка б достигается при движении от центра быстрее, чем точка а (т.е. через точку б проходит изолиния меньших затрат, чем через точку а).
После определения очередной точки устройство возвращается в исходное положение; перемещением основания 1 с помощью пантографа 2 добиваются совмещения с ней центра окруж ноетv, изложенным способом определяют следующую точку, т. д. до получения последней точки.
Если начальная точка маршрута не задана, то она может быть определена путем решения и раз (где и — число заданных точек маршрута) аналогичных задач изложенным способом, принимая последовательно в качестве начальной точки каждую из и точек. Суммируя при этом общие затраты на каждом из и маршрутов и сравнивая их между собой, можно выявить маршрут с наименьшими затратами и принять его в качестве решения. При условии определения маршрута, затраты на который не превосходят заданной величины, 5 процедура Определения маршрута прекра- щается при выполнении этого условия и он принимается в качестве решения. Для операции оценки затрат на переход из одной точки в другую необходимо снять отсчет со шкалы 27 и умножить это число на цену, т.е. на затраты, необходимые на переход из центра на эллипсе, соответствующий перемещению на одно деление шкалы 27. Общие затраты, потребленные для обеспечения всего маршрута, определяются путем суммирования затрат»а каждом шаге.
Формулы, необходимые для градуирования шкал Gi. G, ба, G< (фиг. 4) в зависимости от задаваемого условиями задачи коэффициента К (отношение функций влияния): щ д1х дх д1г/дг
1. = ac csin (cos Д вЂ” КП
G,(К) =у = arctg 0,5(tg(p+a ) — tg(p — ));
G (Ê) = . = n --у; з(К) = . I = ВС+ I ising;
G„(K) = 35 1 — фиксированная величина, равная расстоянию от фокуса объектива 8 осветителя 7 в исходное положении до рабочей поверхности стола (т.е. до нижней поверхности основания 1), этому расстоянию соответствует нулевая отметка шкалы 22; I> — фиксированная величина, равная длине штанги 12 от нулевой отметки шкалы 27 до фокуса объектива 8 (фиг. 4). Форл ула изобретения Устройство для решения геомстричсских и комбинаторных задач, содержа щсе первую штангу с нанесенной на нес шкалой, первый транспортер, жестко соединен50 ный с первой штангой, первый фиксирующий элемент, отличающееся тем, что, с цслью повышения точности, в него введсны прибор для формирования эллипсов, содержащий осветитель, снабженный объсктивом с блендой, корпус объектива жестко сосдинсн с вторым транспортером и шарнирно соединен с первой ц тангой, помещенной внутри первой направляющей втулки, снабженной первым и вторым фиксирующими элемен1336038 Фиг. 1 тами, первая направляющая втулка соединена с второй штангой, с которой жестко скреп, ен третий транспортер, вторая штанга расположена вну гри второй направляющей втулки, которая жестко соединена с третьей втулкой, являющейся направляющей для поворотной штанги, установленной на основании, выполненном с воэможностью горизонтального и вертикального перемещения относительно плоскости стола, вторая и третья втулки и основание снабжены с третьего по пятый фиксирующими элементами соответственно, вторая и третья штанги снабжены нанесенными на них шкалами. 1336038 1336038 Фиг.5 Составитель 3. Шершнева Редактор С. Патрушева Техред И. Верес Корректор И. Муска За каз 3805/46 Тираж 672 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий ! 13035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4
