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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)4 G 06 G 1 16

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4281066/24-2 (22) 09,07,87 (46) 15,04.89. Бюл; У 14 (72) Н.А.Карпушкин и К.P.Разин (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 412026, 1974.

Авторское свидетельство СССР

Ф 1171810,. кл. G 06 G 1 f1 6, 1985, (54) УСТРОЙСТВО ДЛЯ ГРАФИЧЕСКОГО

РЕШЕНИЯ ЗАДАЧ .(57) Изобретение относится к вычислительным устройствам с ручным управлением и может быть использовано для графического решения геометрических и комбинаторных задач маршрутного типа, относящихся к классу задач коммивояжера. Цель изобретения — унификация процедуры решения всего класса комбинаторных задач маршрутного типа. Сущность изобретения состоит в применении дополнительной второй поворотной планки с фиксирующим элементом, которая скрепляется с первой посредством свободно пе

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

Цель изобретения — унификация процедуры решения всего класса комбинаторных задач маршрутного типа.

На фиг.1 представлено устройство, общий вид „ на фиг.2 — процедура построения псев::; 7o÷åê маршрута.

„.SUÄÄ 1472922 А1 ремещающегося относительно выполненных в планках сквозных продольных пазов полого штифта. На штифт е размещается поворотный прозрачный сектор с оцифрованными концентрическими дугами. На линейке нанесены прямая и обратная шкалы, а на обрезе — лимб с градусной шкалой. Перечисленные признаки изобретения позволяют перейти от действительных координат точек маршрута к псевдокоорцинатам. В этом случае пространство в новых переменных будет изотропным в смысле равноценности затрат. Используя изолинии уровня затрат и эвристическое правило "идти в ближайшую точку" определяется оптимальный маршрут движения.

Работа с устройством осуществляется в два этапа. На первом этапе осуществляется построение псевдокоординат точек маршрута. На втором определяется оптимальный маршрут. Используя нормирование изолиний уровня затрат, определяются общие затраты на маршруте. 2 ил.

Устройство содержит линейку 1, на

i которой расположен ползунок 2, На ползунке посредством оси 3 с фиксирующим элементом 4 размешена первая Iloворотная планка 5. На одном конце линейки также посредством оси с фиксирующим элементом 6 размещены лимб с градусной шкалой 7 и вторая поворотная планка 8. В продольную прорезь планки 8 вставлен невыпадающий полый штифт 9, предназначенный для точного совмещения центра осевой полости с координатами точек маршрута, обеспе—

1472922

30 функции влияния, характеризующие приращение затрат при переходе из одной точки в другую, находящуюся на единичном расстоянии в X(Z)направлении; приращение координат точки N в Х(Е)-на" .

) правлении относительно 40 координат. точки N;, 1) можно записать в ви ТХ Т7 где — — (— -) 8Х ЗЕ (ЛЕ; ) Уравнение (де

1 ) + д Х; а т

)z„j

Ь. (2)

DI i DI j где а = — — -", Ь дТ /3X дI /ЗЕ

Преобразуем уравнение (2) к виду а= )Х;„. + (- аЕ;„) (3)

Обозначим коэффициент перед h Z .

i) через К, т,е. а 8I> d Ix 55

К=-= — -/ —" (4)

Ь РЕ дХ

OZ )) (5) чивающий подвижное соединение поворотных планок 5 и 8, а также круговое движение прозрачного сектора 10 с одифрованными дугами 11. Для снятия отсчета со шкалы лимба в планке выполнено окошко 12. На линейке 1 нанесены две шкалы: основная 13 с прямым направлением отсчета от нуля до десяти, обеспечивающая увеличение какойлибо иэ координат точки (Х или Е) в

К раз, и дополнительная 14 с обратным направлением отсчета от единицы до нуля, обеспечивающая уменьшение любой из координат точки в 1/К раз

К 1.

В основу решения обобщенной задачи коммивояжера положено эвристическое правило "идти в ближайшую точку".

Обобщение задачи коммивояжера заклю- 20 чается в неравноценности затрат по продольной Х и боковой Z осям при пе. реходе из одной точки в другую. В прототипе показано, что полные затраты при переходе из точки N; в точку 25

N. равны .

pI ° =-(— -) дх ° + ()dЕ, (1)

ЙТх 2 2. 3Ig 2 дХ что эквивалентно введению новой системы координат, в которой проекция точки маршрута будет отличаться от проекции в системе координат XZ в

К раз.

С учетом (4) и (5) уравнение (3) примет вид а = dX; + ЛЕ 1

Аналогичные преобразования с координатой Х приводят к выражению

b =АХ;)+ ЛЕ,, ) (6) (7) где

7)X = — BX

) К (8) Выражения (6) и (7) являются уравнениями окружностей радиусом а и

Ь соответственно. Совокупность графиков этих окружностей представляет собой иэолинии уровня затрат при переходе из центра на любую точку окружности, Переход от действительных координат точек маршрута к псевдокоординатам по формулам (5) или (8) возможен четырьмя способами:

1) при К ) 1 координаты по Z увеличиваются в К раз;

2) при К (1 координаты по Х увеличиваются в К раз;

3) при К ) 1 координаты по Z уменьшаются в К раз;

4) при,К (1 координаты по Х уменьшаются в К pas.

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

При этом необходимо также учитывать соответствующую соизмеримость масштаба карты (графика) с размерами устройства.

Таким образом, если перейти от действительных координат точек маршрута d Х, 4 Е-; к псевдокоординаij э 1) там d X;., Л Е,. по формуле (5) или к псевдокоординатам но формуле (8), то пространство в новых переменных будет изотропным в смысле равноценности затрат для любых налравлений движения. Исходя из вышеприведенных соотношений, эти затраты определяются следующим образом;

2 Тх

1)- Х,, 2 2 3Ix йХ; + hZ„) — ;а. (9) 1472922 х ах (14) dI;; =с .N, где

В свою очередь, радиус дуги окружности может быть представлен выражением о 1 1 (10) где й, — радиус первой (единичной) дуги окружности или равное ему приращение радиусов последующих дуг окружностей;

N — ближайший к рассматриваемой точке порядковый .номер дуги окружности (для большей точности определения затрат на переход от точки к точке N не обязательно должно быть целым числом).

С учетом (10) выражение (9) примет вид:

В выражении (11) произведение

r = с

Ix дХ 0 х. (12) представляет собой нормированную для конкретной задачи цену деления.

Таким образом, затраты при переходе от точки i к точке j будут вычисляться по формуле

dI; =с N

11 (13)

При введении псевдокоординат по оси затраты будут определяться аналогичным выражением I2

2 gz o

Для оценки затрат на переход иэ точки i в точку j необходимо снять отсчет с дуги окружности прозрачного сектора, которой накрывается данная псевдоточка маршрута, и умножить это число на цену деления с„ при введении псевдокоординат по оси Х или на с при введении псевдокоординат по оси Z.

Линейку и поворотные планки рекомендуется изготовлять из жесткого легкого материала. Сектор должен быть изготовлен из прозрачного материала на который наносятся оцифрованные концентрические дуги с равными приращениями радиуса. Частота нанесения дуг и масштаб, а следовательно, и размеры сектора в отличие от планщета у прототипа могут быть однотипными для широкого класса рещаемых задач. Это возможно благодаря тому, что при решении любой задачи

5 маршрутнога типа производится нормирование цены деления системы дуг с учетом заданных значений функций влияния, что оказывается на унификации процедуры решения задач и повышении

1ð точности

Такой способ подготовки планшетов позволяет не только графически определять оптимальный маршрут и затраты на каждом "переходе" от точ15 ки i к точке 1, но и производить общую оценку затрат для выбранного маршрута путем суммирования затратДТ;„

I на каждом "переход".

Работа с устройством осуществля20 ется в два этапа.

Первый этап заключается в построении псевдокоординат точек маршрута (фиг.1). С этой целью для удобства

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

На фиг.2 показано: Π— исходная точка маршрута; а — точка, принимаемая за начальную; б — одна из точек маршрута; б — псевдотачка маршрута.Для построения псевдоточки необходимо зафиксировать вторую поворотную планку перпендикулярно линейке. Подводят линейку по оси Х так, чтобы начало отсчета прямой шкалы (при увеличении в

"5 К раз координата Z) или начало. отсчета обратной шкалы (при уменьшении координаты Z в 1/К раз) находилась на одной линии в прорезе второй планки.

Далее, не нарушая положения линейки

5Р с зафиксированной второй планкой, совмещают с помощью подвижного ползунка обрез первой планки с единицей шкалы на линейке и точкой б и фиксируют первую планку относительно пол55 зунка. После этого, сдвигая ползунок до совмещения обреза первой планки с числом на линейке, равным коэффициенту К (на фиг.2"К = 5) отмечают на пе1472922 ресечении обреза первой планки и продольного паза второй планки псевдоточку маршрута б.

Из рассмотрения двух подобных пря5 моугольных треугольников, катеты которых лежат на линиях Об, а гипотенузы образованы обрезом первой подвижной планки, видно, что псевдокоордината б в пять раз больше координаты 10 точки "б". Далее подводят начало отсчета О основной шкалы линейки к линии пересечения следующей точки С с осью Х и производят аналогичные построения ее псевдокоординаты. В слу- 15 чае К < 1 координаты псевдоточек строят rio аналогичной методике, Отличие при этом состоит лишь в использовании дополнительной шкалы с обратным направлением отсчета, Закон- 20 чив построение псевдокоординат всех точек маршрута, переходят к второму этапу.

Второй этап состоит в непосредственном определении маршрута по псевдокоординатам. Для этого используют прозрачный сектор с оцифрованными концентрическими pyraMH совместно с линейкой и поворотными планками.

Линейку выставляют как и при опре- 30 делении псевдокоординат точек маршрута вдоль оси Х. Далее освобождают фиксирующие элементы на обоих поворотных планках и полость штифта (являющуюся центром концентрических дуг) 35 совмещают с точкой, принятой за начальную (точка а). Перемещая сектор вокруг штифта, определяют ближайшую к центру псевдоточку маршрута. Через эту точку проходит дуга, харак- 40 теризующая изолинию наименьших затрат ° Для вычисления затрат на переход от точки, принятой за начальную, до ближайшей псевдоточки (называемой далее первой),необходимо зафик- 45 сировать номер N ближайшей к этой псевдоточке дуги и воспользоваться формулой (13).

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

Общие затраты для найденного маршрута определяют путем суммирования затрат d I; на каждом "переходе".

Если начальная точка маршрута не задана, то она может быть определена путем решения и раз (n — количество заданных точек маршрута) аналогичных задач вышеизложенным способом, принимая последовательно в качестве начальной точки каждую из точек, Суммируя при этом обшие затраты на каждом из маршрутов и сравнивая их между собой, можно выявить маршрут с наименьшими затратами и принять

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

Формула изобретения

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

1472922

Фиа2

Составитель Г.Тимофеев

Техред Л.Олийнык Корректор Н. Король

Редакто р А. Лежнина

Заказ 1713/49 Тираж 667 Подписное

ВНИИПИ Государственного комитета о изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Рауаская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101