Устройство для графического решения задач

(51)4 С 06 6 1 16 АНИЕ ИЗОБРЕТЕНИ ремещающегося относительно выполненных в планках сквозных продольных пазов полого штифта. На штифте размещается поворотный прозрачный секторс оцифрованными концентрическими дугами. На линейке нанесены прямая иобратная шкалы, а на обрезе - лимбс градусной шкалой, Перечисленныепризнаки изобретения позволяют перейти от действительных координат точекмаршрута к псевдокоорцинатам. В этомслучае пространство в новых переменных будет изотропным в смысле равноценности затрат. Используя изолинииуровня затрат и эвристическое правило "идти в ближайшую точку" определяется оптимальный маршрут движения.Работа с устройством осуществляетсяв два этапа. На первом этапе осуществляется построение псевдокоординатточек маршрута. На втором определяется оптимальный маршрут. Используянормирование изолиний уровня затрат,определяются общие затраты на маршруте. 2 ил. Устройство содержит линейку 1, на которой расположен ползунок 2, На ползунке посредством оси 3 с фиксирующим элементом 4 размешена первая поворотная планка 5, На одном конце линейки также посредством оси с фиксирующим элементом 6 размещены лимб с градусной шкалой 7 и вторая поворотная планка 8. В продольную прорезь планки 8 вставлен невыпадающий полый штифт 9, предназначенный для точного совмещения центра осевой полости с координатами точек маршрута, обеспеГОСУДАРСТВЕННЫЙ КОМИТЕПО ИЗОБРЕТЕНИЯМ И ОТКРЫТПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССР У 412026, 1974.Авторское свидетельство СССР Ф 1171810,. кл. 6 06 С 1 д 6, 1985. (54) УСТРОЙСТВО ДЛЯ ГРАФИЧЕСКОГО РЕШЕНИЯ ЗАДАЧ(57) Изобретение относится к вычис" лительным устройствам с ручным управлением и может быть использовано для графического решения геометрических и комбинаторных задач маршрутного типа, относящихся к классу задач коммивояжера. Цель изобретения - унификация процедуры решения всего класса комбинаторных задач маршрутного типа. Сущность изобретения состоит в применении дополнительной второй поворотной планки с фиксирующим элементом, которая скрепляется с первой посредством свободно пе 1Изобретение относится к вычислительным устройствам с ручным управлением и может быть использовано для графического решения геометрических и комбинаторных задач маршрутного типа, относящихся к классу задач коммивояжера.Цель изобретения - унификация процедуры решения всего класса комбинаторных задач маршрутного типа,На фиг,1 представлено устройство, общий вид на фиг,2 - процедура построения псев,оточек маршрута. 1472922 А(2)45 с 1 хах" Л Е,чивающий подвижное соединение поворотных планок 5 и 8, а также круговоедвижение прозрачного сектора 10 содифрованными дугами 11. Для снятияотсчета со шкалы лимба в планке выполнено окошко 12. На линейке 1 нанесены две шкалы: основная 13 с прямымнаправлением отсчета от нуля до десяти, обеспечивающая увеличение какойлибо иэ координат точки (Х или Е) вК раз, и дополнительная 14 с обратным направлением отсчета от единицыдо нуля, обеспечивающая уменьшениелюбой из координат точки в 1/К разК )1,В основу решения обобщенной задачи коммивояжера положено эвристическое правило "идти в ближайшую точку",Обобщение задачи коммивояжера заключается в неравноценности затрат попродольной Х и боковой Е осям при пе. реходе из одной точки в другую, Впрототипе показано, что полные затраты при переходе из точки И; в точку 2511. равны:1д 1=( - -) дх. + ( )д Е, (1)Лх гг. д 1, аЗХ 3 дЕ 30 функции влияния, характеризующие приращение затрат при переходе из одной точки в другую, находящуюся на единичном расстоянии в Х(Е)- направлении;приращение координат точки Б в Х(Е)-на"1правлении относительно 40 координат. точки Б;.1) можно записать в вигде а= -- -"; Ь З 1/ЗХ д 1/3 Е Преобразуем уравнение (2) к видуа= дХ;+ (- ДЕ,) (3)50 Обозначим коэффициент перед Л Е . через К, т,е. а д 1 31 х 55 Ь / (4) Ь ЙЕ йХчто эквивалентно введению новой системы координат, в которой проекция точки маршрута будет отличаться от проекциив системе координат ХЕ в К раз,С учетом (4) и (5) уравнение (3) примет вида = дХ, + ЛЕ;Аналогичные преобразования с координатой Х приводят к выражениюЬ =дх;, + аЕ Выражения (6) и (7) являются уравнениями окружностей радиусом а и Ь соответственно. Совокупность графиков этих окружностей представляет собой иэолинии уровня затрат при переходе из центра на любую точку окружности.Переход от действительных координат точек маршрута к псевдокоординатам по формулам (5) или (8) возможен четырьмя способами:1) при К ) 1 координаты по Е увеличиваются в К раз;2) при К ( 1 координаты по Х увеличиваются в К раз;3) при К ) 1 координаты по Е уменьшаются в К раз;4) при,К ( 1 координаты по Х уменьшаются в К раз.При выборе способа предпочтение следует отдавать первым двум,поскольку увеличение координат не скажется на потере точности решения задачи. При этом необходимо также учитывать соответствующую соизмеримость масштаба карты (графика) с размерами устройства,Таким образом, если перейти от действительных координат точек маршрута Л Х , Л Е к псевдокоординай 1 там Л Х, , Д Е,. по формуле (5) или к псевдокоординатам о формуле (8), то пространство в новых переменных будет изотропным в смысле равноценности затрат для любых налравлений движения. Исходя из вышеприведенных соотношений, эти затраты определяются следующим образом11 х(14) й 1=с Н,где 5В свою очередь, радиус дуги окружности может быть представлен выражениема =1, И, (10) где й, - радиус первой (единичной)дуги окружности или равноеему приращение радиусов последующих дуг окружностей;Б - ближайший к рассматриваемойточке порядковый .номер дугиокружности (для большей точности определения затрат напереход от точки к точке Яне обязательно должно бытьцелым числом).С учетом (10) выражение (9) примет вид: В выражении (11) произведение г = с1 ко к(12) представляет собой нормированную для конкретной задачи цену деления.Таким образом, затраты при переходе от точкик точке 1 будут вычисляться по формуле д 1; =с И (13)При введении псевдокоординат по оси затраты будут определяться аналогичным выражением д 12 дЕ оДля оценки затрат на переход иэ точкив точку 1 необходимо снять отсчет с дуги окружности прозрачного сектора, которой накрывается данная псевдоточка маршрута, и умножить это число на цену деления с при вве" дении псевдокоординат по оси Х или на с при введении псевдокоординат по оси Е.Линейку и поворотные планки рекомендуется изготовлять из жесткого легкого материала, Сектор должен быть изготовлен из прозрачного материала на который наносятся оцифрованные концентрические дуги с равными приращениями радиуса, Частота нанесения дуг и масштаб, а следовательно, и размеры сектора в отличие от планщета у прототипа могут быть однотипными для широкого класса рещаемых задач. Это возможно благодарятому, что при решении любой задачи5маршрутного типа производится нормирование цены деления системы дуг сучетом заданных значений функций влияния, что оказывается на унификациипроцедуры решения задач и повышении1 О точностиТакой способ подготовки планшетов позволяет не только графическиопределять оптимальный маршрут изатраты на каждом "переходе" от точ 15 ки д к точке 1, но и производить общую оценку затрат для выбранного маршрута путем суммирования эатрат 31;Цна каждом ппереходРабота с устройством осуществля 20 ется в два этапа,Первый этап заключается в построении псевдокоординат точек маршрута(фиг,1), С этой целью для удобства25;работы прозрачный сектор может бытьснят с полого штифта (на фиг.2 устройство показано без сектора), С помощью линейки проводят через исход.ную точку маршрута и точку, выбираемую за начальную ась Х, Перпендикулярно к оси Х с помощью градусноголимба и второй поворотной пленки через первую точку маршрута ось Е. Далее оценивают, по какой из осей Хили Е целесообразно увеличиватьЗ 5 (уменьшать) координаты псевдоточек,На фиг,2 показано: 0 - исходная точка маршрута; а - точка, принимаемаяза начальную; б - одна из точек маршрута; б - псевдотачка маршрута.Дляпостроения псевдоточки необходимо зафиксировать вторую поворотную планкуперпендикулярно линейке. Подводятлинейку по оси Х так, чтобы начало отсчета прямой шкалы (при увеличении в"5 К раз координата Е) или начало. отсчета обратной шкалы (при уменьшении координаты Е в 1/К раз) находилась наодной линии в прорезе второй планки.Далее, не нарушая положения линейки5 О с зафиксированной второй планкой,совмещают с помощью подвижного ползунка обрез первой планки с единицейшкалы на линейке и точкой б и фиксируют первую планку относительно пол 55 зунка, После этого, сдвигая ползунокдо совмещения обреза первой планки счислом на линейке, равным коэффициенту К (на фиг.2"К = 5) отмечают на пе 1472922ресечении обреза первой планки и продольного паза второй планки псевдоточку маршрута б.Из рассмотрения двух подобных пря 5 моугольных треугольников, катеты которых лежат на линиях Об, а гипотенузы образованы обрезом первой подвижной планки, видно, что псевдокоордината б в пять раз больше координаты 1 О точки "б", Далее подводят начало от" счета О основной шкалы линейки к линии пересечения следующей точки С с осью Х и производят аналогичные построения ее псевдокоординаты. В слу чае К ( 1 координаты псевдоточек строят по аналогичной методике, Отличие при этом состоит лишь в использовании дополнительной шкалы с обратным направлением отсчета, Закон чив построение псевдокоординат всех точек маршрута, переходят к второму этапу.Второй этап состоит в непосредственном определении маршрута по псев докоординатам. Для этого используют прозрачный сектор с оцифрованными концентрическими дугами совместно с линейкой и поворотными планками.Линейку выставляют как и при опре делении псевдокоординат точек маршрута вдоль оси Х. Далее освобождают фиксирующие элементы на обоих поворотных планках и полость штифта (являющуюся центром концентрических дуг) З 5 совмещают с точкой, принятой за начальную (точка а). Перемещая сектор вокруг штифта, определяют ближайшую к центру псевдоточку маршрута, Через эту точку проходит дуга, харак теризующая изолинию наименьших затратДля вычисления затрат на переход от точки, принятой за начальную, до ближайшей псевдоточки (называемой далее первой),необходимо зафик сировать номер И ближайшей к этой псевдоточке дуги и воспользоваться формулой (13).Для определения последующей точки маршрута необходимо, сохраняя поло жение линейки неизменным, выставить полость штифта на первую точку и,перемещая сектор вокруг штифта, определить ближайшую псевдоточку маршрута, которая и будет второй на маршруте, Аналогично описанному определяют затраты на переход от первой к второй точке. Изложенные процедуры повторяют до прохождения всех точек,Общие затраты для найденного маршрута определяют путем суммирования затрат Я 1; на каждом "переходе".Если начальная точка маршрута не задана, то она может быть определена путем решения и раз (и - количество заданных точек маршрута) аналогичных задач вышеизложенным способом, принимая последовательно в качестве начальной точки каждую из точек, Суммируя при этом обшие затраты на каждом из маршрутов и сравнивая их между собой, можно выявить маршрут с наименьшими затратами и принять его в качестве решения. При условии определения маршрута, затраты на который не превосходят заданной величины, процедура определения маршрута прекращается при выполнении этого условия, и он принимается в качестве решения. Формула изобретенияУстройство для графического решения задач, содержащее линейку -с нанесенной шкалой, на которой расположен первый ползунок с фиксирующим элементом, на оси которого закреплена подвижная планка, о т л и ч а ю - щ е е с я тем, что, с целью унификации процедуры решения всего класса комбинаторных задач маршрутного типа, на одном. конце линейки расположена вторая поворотная планка с фиксирующим элементом, которая скреплена с первой планкой посредством свободно перемещающегося относительно выполненных в планках сквозных продольных пазов полого штифта, несущего на себе поворотный прозрачный сектор с оцифрованными концентрическими дугами, кроме того, линейка содержит дополнительную обратную шкалу и на одном конце лимб с градусной шкалой,1472922 Фиаг оставитель Г.Тимофеевехред Л.Олийнык РектоР Н,коро раж 667 Подп ГКНТ ССС о изобретениям и открытиям 35, Рауюская наб д. 4/5 ьский ент", г комбин акто р А. Лежнин каз 1713/49 НИИПИ Государственно 11303