Метод машинного решения задач

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

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

Таким образом, мы приходим к двум взаимно исключающим выводам: с одной стороны, форма задания исходных данных требует графического метода решения; с другой — реализация процесса решения на ЭЦВМ допускает применять только аналитический метод.

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

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

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

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

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

* Подробно аспекты машинного "чтения" чертежа, а также другие вопросы автоматизации процесса графического решения задач изложены в книге С. А. Фролова "Кибернетика и инженерная графика". М.: Машиностроение, 1974.

ческие построения заменялись алгебраическими решениями, характерными для аналитического метода.

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

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

Если при решении задачи по определению точки пересечения двух линий "вручную" не имеет значения, какие линии пересекаются, то для машинного решения мы должны четко различать следующие случаи:

1) пересечение двух прямых;

2) пересечение прямой с кривой (в частном случае с окружностью);

3) пересечение двух кривых (в частности, двух окружностей).

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

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

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

В отличие от человека для машины определение точки пересечения двух линий является не элементарной операцией, а задачей. Число и характер команд, которые должна выполнить машина для ее решения, во всех перечисленных выше случаях будут различными. Если для определения координат точки пересечения двух прямых (случай 1), или пересечения прямой и окружности, или двух окружностей (частные варианты случаев 2 и 3) машине достаточно решить систему уравнений, которыми описываются эти линии, то в общем варианте случая 2 (рис. 321) машина должна сначала на кривой выделить точки 1 и 2, расположенные ближе к прямой (множество М₁ {... }), чем любые другие точки множества М₂ {...}; составить уравнение прямой, проходящей через эти точки, и лишь после этого приступить к определению координат точки

пересечения К. В случае 3 (рис. 322) машина предварительно должна выделить две пары таких точек (по одной паре из каждого множества M₁ {...} и M₂ {...}), чтобы расстояние между ними было наименьшим из всех возможных в данной ситуации, и только после этого приступить к составлению уравнений прямых, проходящих через эти точки 1, 2 и 3, 4, и совместному решению этих уравнений.

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

Во втором варианте (кривая линия) отыскания в множестве М₁ {...} точки (растрэлемента) с абсциссой х является случайностью (рис. 323). Как правило, такой точки в М₁ { ... } не будет, поэтому можно говорить только о нахождении в М₁{...} точек 1 и 2, у которых абсолютное значение разности |x_K - x₁| и |х₂ - x_K| - меньше наперед заданной величины Δd. Затем машина составляет уравнение прямой, проходящей через выявленные точки 1 и 2, и на ней определяет искомую точку (так, как это делается в первом варианте).

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

Для ЭЦВМ "провести" прямую или окружность означает составить ее уравнение. Проведение прямых нужно для того, чтобы в дальнейшем выделить на них какие-либо точки (в частности, точки пересечения с другими линиями); проведение окружностей необходимо для решения таких задач, как:

1) определение на заданной линии точек, удаленных от данной точки на расстояние d;

2) определение на плоскости точек, удаленных от данной точки А на расстояние d₁ и от точки В на расстояние d₂.

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

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

В табл. 10 приведен перечень операций, которые должна "уметь" выполнять ЭЦВМ.

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

Таблица 10