Применение графов при построении алгоритма решения задач

С помощью графов (блок-схем) естественно задавать алгоритмы решения различных задач. В алгоритмы могут быть встроены как арифметические, так и логические операции. Такое задание имеет большую наглядность и облегчает школьнику понимание работы алгоритма. Ему становится ясно, почему он должен выполнять те или иные действия при различных возникающих ситуациях. Кроме того, такая форма задания дисциплинирует мышление школьника, позволяет описать все возможные случаи, не пропустив ни одного из них и не рассмотреть никакой случай дважды. Результаты выполнения действий будут меняться в зависимости от начальных условий, и школьнику станет ясно, что алгоритм нацелен на решение не конкретной, а массовой задачи, т.е. такой задачи, в которой исходные параметры могут принимать различные значения.

Рассмотрим на примере модель поиска рационального решения задачи.

Задача. Из двух точек, расстояние между которыми 1320 м, выходят навстречу друг другу 2 тела. Одно из них может пройти это расстояние за 12 минут; скорость другого в 2 раза больше скорости первого. Через сколько минут тела встретятся?

Покажем модель поиска некоторых уравнений к данной задаче, именно тех, которые расположены в ближайших строках графа, т.е. наиболее рациональных. Вершины 1, 2, 3, 4 расположены в первой строке и моделируют данные искомые задачи.

На рисунке указаны краткие обозначения моделируемых ими объектов. Так, вершина 1 моделирует расстояние АВ (1320 м); вершина 2 – время движения первого тела на пути АВ (12 мин.); вершина 3 – соотношения: «скорость второго тела больше скорости первого в 2 раза» или «время движения первого тела на каком-то пути больше времени движения второго на том же пути в 2 раза»; вершина 4 – искомое время движения первого тела на участке АС или второго на участке ВС.

Во второй строке графа расположены вершины 5 – 9, моделирующие первую группу следствий условия задачи, полученных путем возможных операций между данными и искомыми. Так, вершина 1 соединена единственным ненаправленным ребром с вершиной 2. Это значит, что возможна единственная операция между данными 1 и 2. Операция (1, 2) определяет следствие 5 (скорость первого тела). Из вершины 2 исходят два ненаправленных ребра к вершинам 3 и 4. Операция (2, 3) определяет следствие 6 (возможное время движения первого тела на участке ВС). Между объектами 3 и 4 можно произвести две операции и получить следствие 8 (время движения второго тела на участке АС) и 9 (время движения первого тела на участке ВС). Следствие 10 есть результат операции между объектами 4 и 9 (первой и второй строк графа) и помещено в третью строку.

Ребра «равно» соединяют вершины 7 и 9 второй строки, вершины 2 первой и 10 третьей строк. Значит, можно составить уравнения:

2 х = 12 – х (1)

и

3 х = 12(2)

Уравнение (1) 2 + 2 – 2 = 2-й сложности, уравнение (2) 3 + 1 – 2 = 2-й сложности, т.е. оба пути получения уравнений (1) и (2) одинаковой сложности. Если же продолжить граф поиска решений и дальше, то найдем иные пути решения задачи той же или большей сложности. Так, традиционное арифметическое решение, выраженное числовой формулой

будет решением 1 + 6 – 2 = 5-й сложности.

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

Например, с помощью блок-схемы естественно задать алгоритм решения квадратного уравнения и системы линейных уравнений с двумя переменными (рис.1, 2).

Рис.1

Рис.2

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