Как можно осуществлять поиск пути решения задачи в начальной

Обновлено: 30.06.2024

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

Деятельность по решению задачи арифметическим методом вклю­чает следующие основные этапы:

1. Анализ задачи.

2. Поиск плана решения задачи.

3. Осуществление плана решения задачи.

4. Проверка решения задачи.

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

1. Анализ задачи

Основное назначение этого этапа - понять в целом ситуацию, опи­санную в задаче; выделить условия и требования: назвать известные и искомые объекты, выделить все отношения (зависимости) между ними.

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

Известно несколько приемов, которые можно использовать при анализе задачи.

Разобраться в содержании задачи, вычленить условия и требова­ния можно, если задать специальные вопросы и ответить на них:

Очем задача, т.е. о каком процессе (явлении, ситуации) идет речь в задаче, какими величинами характеризуется этот процесс?

Что требуется найти в задаче?

Что обозначают те или иные слова в тексте задачи:

Что в задаче известно о названных величинах?

Что является искомым?

Воспользуемся указанным приемом

1) О чем эта задача?

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

2) Что требуется найти в задаче?

- В задаче требуется найти расстояние, которое пробежит собака
за все время от начала движения, пока мальчики не окажутся рядом,
т.е. второй не догонит первого.

3) Что в задаче известно о движении каждого из его участников 9

- В задаче известно, что: а) мальчики идут в одном направлении;

б) до начала движения расстояние между мальчиками было 2 км;

в) скорость первого мальчика, идущего впереди. 4 км/ч; г) скорость
второго мальчика, идущею позади, 5 км/ч: д) скорость, с которой бежит
собака, 8 км/ч; е) время движения, когда расстояние между мальчиками
было 2 км, до момента встречи.

4) Что в задаче неизвестно?

- В задаче неизвестно время, за которое второй мальчик догонит
первого, т.е. неизвестно время движения всех его участников. Неизвестно
также, с какой скоростью происходит сближение мальчиков. И неизвестно расстояние, которое пробежала собаки, это требуется узнать в задаче.

5) Что является искомым: число, значение величины, вид некоторого отношения?

Искомым является значение величины расстояния, которое про­бежала собака за время от начала движения мальчиков до момента встречи

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

Особенно эффективно использование данного приема в сочетании с разбиением текста на смысловые части.

Результатом перефразировки должно быть выделение основных ситуаций.

Поскольку в задаче, рассмотренной выше, речь идет о движении, ее можно перефразировать следующим образом:

Перефразированный текст часто бывает полезно записать в таблице.

Например, рассматриваемую задачу можно записать с помощью таблицы такого вида:

Скорость Время Расстояние
1-й мальчик 4 км/ч 2-й мальчик 5 км/ч Собака 8 км/ч ? ? ? Одинаковое ? ? ? На 2 км больше 1-го мальчика ?


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

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

После построения вспомогательной модели необходимо проверить:

1) все ли объекты задачи и их величины показаны на модели;

2) все ли отношения между ними отражены;

3) все ли числовые данные приведены;

4) есть ли вопрос (требование) и правильно ли он указывает искомое?

2. Поиск и составление плана решения задачи

Назначение этого этапа: установить связь между данными и иско­мыми объектами, наметить последовательность действий.

План решения задачи - это лишь идея решения, его замысел. Может случиться, что найденная идея неверна. Тогда надо вновь возвращаться к анализу задачи и начинать все сначала.

Как искать план решения текстовой задачи? Односложного ответа на этот вопрос нет. Поиск плана решения задачи является трудным процессом, который точно не определен. Можно только указать неко­торые приемы, которые позволят осуществлять этот этап. Одним из наиболее известных приемов поиска плана решения задачи арифме­тическим способом является разбор задачи по тексту или по ее вспо­могательной модели.

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

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

Рассуждения ведем от данных к вопросу: известно, что 6 ч турист проехал на поезде, который шел со скоростью 56 км/ч; по этим данным можно узнать расстояние, которое проехал турист за 6 ч, для этого достаточно скорость умножить на время. Зная пройденную часть рас­стояния и то, что оставшееся расстояние в 4 раза больше, можно найти, ему оно равно. Для этого пройденное расстояние нужно умножить на 4 (увеличить в 4 раза). Зная, сколько километров турист проехал и сколько ему осталось ехать, можем найти весь путь, выполнив сложение най­денных отрезков пути. Итак, первым действием будем находить расстояние, которое турист проехал на поезде; вторым действием расстояние, которое ему осталось проехать; третьим - весь путь.

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

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

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

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

Заметим, что поиск плана решения данной задачи по схематиче­скому чертежу может быть проведен иначе (сделайте это самостоя­тельно), - в результате мы получим различные арифметические способы ее решения.

3. Осуществление плана решения задачи

Назначение данного этапа найти ответ на требование задачи, выполнив все действия в соответствии с планом.

Для текстовых задач, решаемых арифметическим способом, исполь­зуются следующие приемы:

- запись по действиям (с пояснением, без пояснения, с вопросами);

- запись в виде выражения.

1. Запись решения по действиям с пояснением к каждому выполненному действию.

1) 56 ∙ 6 = 336 (км) - турист проехал за 6 ч

2) 336 ∙ 4 = 1344 (км) - осталось проехать туристу

3) 336 + 1344 = 1680 (км) - должен был проехать турист.

Если пояснения даются в устной форме (или совсем не даются), то запись будет следующей: 1)56 ∙ 6 = 336 (км) 2)336 ∙ 4= 1344 (км) 3)336+ 1344= 1680 (км)

2. Запись решения по действиям с вопросами:

1) Сколько километров проехал турист на поезде?
56 ∙ 6 = 336 (км)

2) Сколько километров осталось проехать туристу?
336∙ 4= 1344 (км)

3) Сколько километров турист должен был проехать?
336 + 1344 = 1680(км)

3. Запись решения в виде выражения.

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

Так, для рассматриваемой задачи эта форма записи имеет вид:

56 • 6 (км) - расстояние, которое проехал турист на поезде за 6 ч

56•6•4 (км) - расстояние, которое осталось проехать туристу

56•6 + 56•6•4 (км) - путь, который должен проехать турист

56•6 + 56•6•4 = 1680 (км)

Пояснения к действиям можно не записывать, а давать их в устной форме. Тогда запись решения задачи примет вид: 56•6 + 56•6•4 = 1680 (км)

Проверка решения задачи

Назначение данного этапа — установить правильность или оши­бочность выполненного решения.

Известно несколько приемов, помогающих установить, верно ли решена задача. Рассмотрим основные.

1. Установление соответствия между результатом и условиями за­дачи.

Для этого найденный результат вводится в текст задачи и на ос­нове рассуждений устанавливается, не возникает ли при этом проти­воречия.

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

Заметим, что при использовании данного приема проверяются все отношения, имеющиеся в задаче, и если устанавливается, что противо­речия не возникает, то делают вывод о том, что задача решена верно.

2. Решение задачи другим способом.

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

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

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

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

Содержание

Введение
Глава I. Задача и её функции.
Глава II. Методика обучения решению текстовых задач
2.1. Понятие текстовая задача
2.2. Классификация текстовых задач
2.3. Обучение учащихся решению текстовых задач методом составления уравнений
2.4. Этапы решения текстовых задач с помощью уравнений
Глава III. Практическая реализация этапов решения текстовых задач с помощью уравнений
3.1. Решение задач с помощью составления уравнений в теме “Уравнение”
Заключение
Используемая литература

Вложенные файлы: 1 файл

реферат по математике.docx

Итак, основные назначения этапа – осмыслить ситуацию, отраженную в задаче; выделить условия и требования, назвать данные и искомые, выделить величины и зависимости между ними (явные и неявные). На этом этапе решения задачи можно использовать такие приемы:

а) представление той жизненной ситуации, которая описана в задаче;

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

Первый прием – представление той жизненной ситуации, которая описана в задаче, - выполняется фактически при чтении или слушании задачи. Вместе с тем мысленное воспроизведение всех объектов задачи и связей между ними может проводиться и позже. Цель такого воспроизведения – выявление основных количественных и качественных характеристик ситуации, представленной в задаче.

1. О чем говорится в задаче?

2. Что известно в задаче?

3. Что требуется найти в задаче?

4. Что в задаче неизвестно? и др.

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

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

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

Пример. В первом бидоне краски в 2 раза больше, чем во втором. Если из первого бидона взять 2 л краски, а во второй добавить 5 л краски, то в обоих бидонах станет поровну. Сколько краски было в каждом бидоне первоначально?

Вспомогательная модель задачи (в виде схематического чертежа) показана на рисунке.

Пример. Одна машинистка тратит на печатание 12 страниц текста столько же времени, сколько вторая машинистка на печатание 16 страниц. Сколько времени первая машинистка тратит на печатание одной страницы, если вторая печатает одну страницу за 12 мин?

Вспомогательная модель задачи (в виде чертежа) показана на рисунке.

Пример. В первую неделю типография получила с фабрики шесть рулонов бумаги одного сорта и заплатила за них 204 р. Сколько рублей должна заплатить типография за месяц, если она получила 10 таких же рулонов бумаги того же сорта?

Вспомогательная модель задачи (в виде таблицы) показана на рисунке.

Число рулонов (шт.) Стоимость (р.) Цена (р.)
6 204 Одинаковая
10 ?

На втором этапе процесса решения задачи важным моментом является выяснение стратегии решения задачи:

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

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

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

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

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

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

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

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

Пример. В трех школах 1072 ученика, во второй на 16 учеников больше, чем в третьей, и на 14 учеников меньше, чем в первой. Сколько учеников в каждой школе?

Краткая запись задачи показана на рисунке.

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

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

1. На сколько учеников увеличилось бы общее число трех школ, если бы в каждой школе число учеников было бы таким же, как во второй?

2. Сколько учеников было бы в трех школах, если бы число учеников в каждой школе было бы таким же, как во второй школе?

3. Сколько учеников во второй школе?

4. Сколько учеников в первой школе?

5. Сколько учеников в третьей школе?

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

Пример. У трех братьев была некоторая сумма денег: у первого и второго вместе 600 р., у второго и третьего вместе 500 р., у третьего и первого 700 р. Сколько денег было у каждого брата в отдельности?

Решение. Краткая запись задачи показана на рисунке.

II и III - 500 р.

Сколько денег было у каждого брата в отдельности?

Поиск пути решения. Зная, что у первого и второго братьев вместе 600 р., а у второго и третьего вместе 500 р., можем найти, на сколько денег у первого брата больше, чем у третьего.

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

1. На сколько рублей у первого брата больше, чем у третьего?

2. Чему равно удвоенное количество денег третьего брата?

3. Сколько денег имел третий брат?

4. Сколько денег имел первый брат?

5. Сколько денег имел второй брат?

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

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

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

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

Задача. По плану бригада должны была выполнить заказ за 10 дней. Но фактически она перевыполняла норму на 27 деталей в день и за 7 дней работы не только выполнила предусмотренное планом задание, но и изготовила сверх плана 54 детали. Сколько деталей в день должна была изготовить бригада по плану?

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

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

• Структура текстовой задачи. Методы и способы решения текстовых задач

Опр.1. Текстовая задача – есть описание на естественном языке некоторого явления (ситуации, процесса) с требованием дать количественную характеристику какого-либо компонента этого явления, установить наличие или отсутствие некоторого отношения между компонентами или определить вид этого отношения.

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

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

Условия задачи: 1) Две девочки бегут навстречу друг другу. 2) Движение они начали одновременно. 3) Расстояние, которое они пробежали – 420м.4) Одна девочка пробежала на 60м больше, чем другая. 5) Девочки встретились через 30с. 6) Скорость движения одной девочки больше скорости другой.

Требования задачи: 1) С какой скоростью бежала первая девочка. 2) С какой скоростью бежала вторая девочка.

По отношению между условиями и требованиями различают следующие виды задач.

• Определенные задачи – в них условий столько, сколько необходимо и достаточно для выполнений требований (В букете 5 красных роз, а белых на 3 розы меньше. Сколько всего роз в букете?).

• Недоопределенные задачи – в них условий недостаточно для получения ответа (Из зала вынесли сначала 12 стульев, потом еще 5. Сколько стульев осталось в зале?).

• Переопределенные задачи – в них имеются лишние условия (Возле дома росло 5 яблонь, 2 вишни и 3 березы. Сколько фруктовых деревьев росло возле дома?).

• результат, т.е. ответ на требование задачи;

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

Основными методами решения текстовых задач являются арифметический и алгебраический.

Решить задачу арифметическим методом – это значит найти ответ на требование задачи посредством выполнения арифметических действий над числами. Одну и туже задачу можно решить различными арифметическими методами.

• 43=12 (м) – столько было ткани

• 122=6 (к) – сшили из 12м ткани

• 42=2 (раза) – больше ткани идет на платье, чем на кофту

• 32=6 (к) – можно сшить из этой ткани

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

Обозначим через х(г) массу шерсти, израсходованную на шапку. Тогда на шарф будет израсходовано (х+100)г, а на свитер ((х+100)+400)г. Так как на все три вещи израсходовано 1200г, то можно составить уравнение: х+(х+100)+((х+100)+400)=1200. Решив данное уравнение, получим х=200, т.е. если на шапку ушло 200г шерсти, то на шарф – 200+100=300(г), а на свитер (200+100)+400=700(г).

Обозначим через х(г) массу шерсти, израсходованную на шарф. Тогда на шапку будет израсходовано (х-100)г, а на свитер (х+400)г. Так как на все три вещи израсходовано 1200г, то можно составить уравнение: х+(х-100)+(х+400)=1200. Решив данное уравнение, получим х=300, т.е. если на шарф ушло 300г шерсти, то на шапку – 300-100=200(г), а на свитер 300+400=700(г).

Обозначим через х(г) массу шерсти, израсходованную на свитер. Тогда на шарф будет израсходовано (х-400)г, а на шапку ((х-400)-100)г. Так как на три вещи израсходовано 1200г, то можно составить уравнение: х+(х-400)+((х-400)-100)=1200. Решив данное уравнение, получим х=700(г), т.е. если на свитер ушло 700г шерсти, то на шарф – (700-400=300)г, а на шапку ((700-400)-100=200)г.

• Этапы решения текстовой задачи и приемы их выполнения

Деятельность по решению задачи арифметическим методом включает следующие основные этапы: анализ задачи; поиск и составление плана решения задачи; осуществление плана решения задачи; проверка решения задачи.

Название этапа Цель этапа Приемы выполнения этапа
Анализ задачи Понять в целом ситуацию, описанную в задаче; Выделить условия и требования; Назвать известные и искомые объекты, выделить все отношения (зависимости) между ними • Задать специальные вопросы и ответить на них • Перефразировка текста задачи • Построение вспомогательной модели задачи
Поиск и составление плана решения задачи Установить связь между данными и искомыми объектами, наметить последовательность действий • Разбор задачи по тексту (от условия к требованию; от требования к условию) • Разбор по вспомогательной модели
Осуществление плана решения задачи Найти ответ на требование задачи, выполнив все действия в соответствии с планом • Запись решения по действиям (с пояснением; без пояснения; с вопросами) • Запись решения в виде выражения
Проверка решения задачи Установить правильность или ошибочность выполненного решения • Установление соответствия между результатом и условиями задачи • Решение задачи другим способом

Рассмотрим подробнее приемы выполнения этапов решения задачи.

Анализ задачи.

Первый прием - Специальные вопросы.

• О чем задача, т.е. о каком процессе (явлении, ситуации) идет речь в задаче, какими величинами характеризуется этот процесс?

• Что в задаче известно о названных величинах?

• Что неизвестно о названных величинах?

• Что требуется найти в задаче?

• О чем задача? Задача о движении двух мальчиков и собаки. Она характеризуется для каждого участника движения скоростью, временем и пройденным расстоянием.

• Что известно о названных величинах? В задаче известно, что: а) мальчики идут в одном направлении; б) до начала движения расстояние между мальчиками было 2км; в) скорость первого мальчика (идущего впереди) 4 км/ч; г) скорость второго мальчика (идущего позади) 5км/ч; д) скорость, с которой бежит собака, 8км/ч; е) время движения собаки – это время, за которое второй мальчик догонит первого.

• Что неизвестно о названных величинах? В задаче неизвестно: за какое время второй мальчик догонит первого; с какой скоростью происходит сближение мальчиков; расстояние, которое пробежала собака.

• Что требуется найти в задаче? В задаче требуется найти, какое расстояние пробежит собака за время, за которое второй мальчик догонит первого.

Второй прием – Перефразировка текста задачи.

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

Третий прием – Построение вспомогательной модели задачи.

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

После построения вспомогательной модели необходимо проверить:

• Все ли объекты задачи и их величины показаны на модели.

• Все ли отношения между ними отражены.

• Все ли числовые данные приведены.

• Есть ли вопрос (требование) и правильно ли он указывает искомое?

Пример. Построим вспомогательную модель рассмотренной выше задачи. В данной задаче вспомогательной моделью целесообразно выбрать таблицу.

Участники движения Скорость Время Расстояние
Первый мальчик 4км/ч Одинаковое -
Второй мальчик 5км/ч На 2 км больше 1-го мальчика
Собака 8км/ч ?км

Поиск и составление плана решения задачи.

Первый прием – Разбор задачи по тексту.

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

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

Разбор текста задачи от данных к вопросу:

Известно, что 6ч турист проехал на поезде, который шел со скоростью 56км/ч. По этим данным можно узнать расстояние, которое проехал турист за 6ч – для этого нужно скорость умножить на время (566=336). Зная пройденную часть расстояния и то, что оставшееся расстояние в 4 раза больше, можно найти, чему оно равно (3664=1344). Зная, сколько километров турист проехал и сколько ему осталось ехать. Можем найти весь путь, выполнив сложение найденных расстояний (336+1344=1680). Итак, первым действием будем находить расстояние, которое турист проехал на поезде, вторым действием – расстояние, которое ему осталось проехать и третьим – весь путь туриста.

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

Пример. Решим задачу, описанную в предыдущем примере, используя данный прием.

Разбор текста задачи от вопроса к данным:

В задаче требуется узнать весь путь туриста, который состоит из двух частей. Значит, чтобы найти ответ на вопрос задачи достаточно знать, сколько километров турист проехал, и сколько километров ему осталось проехать. И то и другое неизвестно. Чтобы найти пройденный путь, достаточно знать время и скорость, с которой ехал турист – это в задаче известно. Умножив скорость на время, узнаем путь, который турист проехал (566=336). Оставшийся путь можно найти, увеличив пройденный путь в 4 раза (3364=1344). Итак, вначале можно узнать пройденный путь, затем оставшийся, после чего сложением найти весь путь туриста.

Второй прием – Поиск плана решения задачи по вспомогательной модели.

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

Из таблицы видно, что для того, чтобы найти расстояние, которое пробежала собака достаточно знать ее скорость и время движения. Скорость известна, а время движения собаки такое же, как у мальчиков. Чтобы найти это время, нужно знать какое расстояние было между мальчиками и скорость их сближения. Расстояние известно, а скорость сближения мальчиков можно найти, так как скорость каждого известна. Скорость сближения мальчиков найдем разностью, так как они двигаются в одном направлении (5-4=1). Затем узнаем, сколько времени понадобилось, чтобы второй мальчик догнал первого, для этого расстояние между мальчиками разделим на скорость их сближения (21=2). И наконец, мы можем узнать расстояние, которое пробежала собака за это время, для этого ее скорость умножим на время движения собаки (82=16). Итак, вначале найдем скорость движения мальчиков, затем время движения всех участников (оно одинаковое), а потом расстояние, которое пробежала собака.

Осуществление плана решения задачи.

Первый прием – Запись плана решения задачи по действиям (с пояснениями, без пояснений, с вопросами).

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

• 566=336(км) – турист проехал за 6ч

• 3364=1344(км) – осталось проехать туристу

• 336+1344=1680(км) – весть путь туриста

• Сколько километров проехал турист на поезде? 566=336(км)

• Сколько километров осталось проехать туристу? 3364=1344(км)

• Каков весь путь туриста? 336+1344=1680(км)

Второй прием – Запись решения задачи в виде выражения.

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

Пример. Рассмотрим предыдущую задачу.

• 566 (км) – турист проехал за 6ч

• 5664 (км) – осталось проехать туристу

• 566+5664 =1680(км) – весть путь туриста

Пояснения к действиям можно не записывать, а давать их в устной форме, тогда запись решения задачи примет вид: 566+5664 =1680(км).

Проверка решения задачи.

Прием первый – Установление соответствия между результатом и условиями задачи.

Для этого найденный результат вводится в текст задачи и на основе рассуждений устанавливается, не возникает ли противоречия.

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

Мы установили, что турист должен был проехать 180км. Пусть этот результат будет одним из данных задачи. Как известно, за 6ч турист проедет 336км (56=336) и ему останется проехать 1680-336=1344(км). Согласно условию задачи это расстояние должно быть в 4 раза больше того, что он проехал на поезде. Разделив 1344 на 336, получим 4. Следовательно, противоречий с условиями задачи не возникает. Значит, задача решена верно.

Второй прием – Решение задачи другим способом.

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

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

Рассматриваемые в таких задачах величины состоят из частей. В некоторых из них части представлены явно, в других эти части надо суметь выделить, приняв подходящую величину за 1 часть и определить, из каких таких частей состоят другие величины, о которых идет речь в задаче.

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

Решение: В задаче речь идет о массе ягод и массе сахара, необходимых для варки варенья. Известно, что всего ягод 10кг и что на две части ягод надо три части сахара. Требуется найти массу сахара, чтобы сварить варенье из 10кг ягод.

Вспомогательная модель будет иметь вид:

По условию задачи 10кг ягод составляют 2 части, следовательно, на 1 часть приходится 102=5(кг). Сахара надо взять три таких части, получаем, что 53=15(кг).

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

Решение: В задаче речь идет о двух кусках ткани одинаковой длины. От первого отрезали 18м, от второго 25м. После этого в первом куске осталось вдвое больше ткани, чем во втором. Требуется найти первоначальную длину кусков ткани.

Вспомогательная модель будет иметь вид:

• Решение задач на движение

Задачи на движение решаются на основании зависимости между тремя величинами, характеризующими движение: скоростью, расстоянием и временем. Во всех случаях речь идет о равномерном прямолинейном движении.

Итак, движение, рассматриваемое в текстовых задачах, характеризуют три величины: пройденный путь (расстояние) (s), скорость (v), время (t). Основное отношение (зависимость) между ними выражается формулой: s=vt.

Поиск пути — это одна из тех тем, которые обычно представляют самые большие сложности для разработчиков игр. Особенно плохо люди понимают алгоритм A*, и многим кажется, что это какая-то непостижимая магия.

Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.

Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.

В первой части мы объясним простейшие концепции поиска пути. Разобравшись с этими базовыми концепциями, вы поймёте, что A* на удивление очевиден.

Простая схема

Хотя вы сможете применять эти концепции и к произвольным сложным 3D-средам, давайте всё-таки начнём с чрезвычайно простой схемы: квадратной сетки размером 5 x 5. Для удобства я пометил каждую ячейку заглавной буквой.


Простая сетка.


Узлы, обозначающие ячейки сетки.


Дуги обозначают допустимые перемещения между ячейками сетки.

Пример

Допустим, мы хотим переместиться из A в T. Мы начинаем с A. Можно сделать ровно два действия: пройти в B или пройти в F.

Допустим, мы переместились в B. Теперь мы можем сделать два действия: вернуться в A или перейти в C. Мы помним, что уже были в A и рассматривали варианты выбора там, так что нет смысла делать это снова (иначе мы можем потратить весь день на перемещения A → B → A → B…). Поэтому мы пойдём в C.

Находясь в C, двигаться нам некуда. Возвращаться в B бессмысленно, то есть это тупик. Выбор перехода в B, когда мы находились в A, был плохой идеей; возможно, стоит попробовать вместо него F?

Мы просто продолжаем повторять этот процесс, пока не окажемся в T. В этот момент мы просто воссоздадим путь из A, вернувшись по своим шагам. Мы находимся в T; как мы туда добрались? Из O? То есть конец пути имеет вид O → T. Как мы добрались в O? И так далее.

Общий алгоритм

Этот раздел — самая важная часть всей статьи. Вам абсолютно необходимо понять его, чтобы уметь реализовывать поиск пути; остальное (в том числе и A*) — это просто детали. В этом разделе вы будете разбираться, пока не поймёте смысл.

К тому же этот раздел невероятно прост.

Давайте попробуем формализовать наш пример, превратив его в псевдокод.


Также нам нужно отслеживать уже рассмотренные узлы, чтобы не рассматривать их снова. Назовём их explored :


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

Так просто, что даже разочаровывает? И это верно. Но из этого и состоит весь алгоритм. Давайте запишем его пошагово псевдокодом.

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


Мы выбираем один из узлов, до которого знаем, как добраться, и который пока не исследован:


Если мы только что узнали, как добраться до конечного узла, то задача выполнена! Нам просто нужно построить путь, следуя по ссылкам previous обратно к начальному узлу:


Нет смысла рассматривать узел больше одного раза, поэтому мы будем это отслеживать:


Мы определяем узлы, до которых не можем добраться отсюда. Начинаем со списка узлов, соседних с текущим, и удаляем те, которые мы уже исследовали:


Мы берём каждый из них:


Если мы уже знаем, как достичь узла, то игнорируем его. В противном случае добавляем его в список reachable , отслеживая, как в него попали:


Нахождение конечного узла — это один из способов выхода из цикла. Второй — это когда reachable становится пустым: у нас закончились узлы, которые можно исследовать, и мы не достигли конечного узла, то есть из начального в конечный узел пути нет:


И… на этом всё. Это весь алгоритм, а код построения пути выделен в отдельный метод:


Вот функция, которая строит путь, следуя по ссылкам previous обратно к начальному узлу:


Вот и всё. Это псевдокод каждого алгоритма поиска пути, в том числе и A*.

Перечитывайте этот раздел, пока не поймёте, как всё работает, и, что более важно, почему всё работает. Идеально будет нарисовать пример вручную на бумаге, но можете и посмотреть интерактивное демо:

Интерактивное демо

Вот демо и пример реализации показанного выше алгоритма (запустить его можно на странице оригинала статьи). choose_node просто выбирает случайный узел. Можете запустить алгоритм пошагово и посмотреть на список узлов reachable и explored , а также на то, куда указывают ссылки previous .

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

Заключение

Представленный здесь алгоритм — это общий алгоритм для любого алгоритма поиска пути.

Но что же отличает каждый алгоритм от другого, почему A* — это A*?

Вот подсказка: если запустить поиск в демо несколько раз, то вы увидите, что алгоритм на самом деле не всегда находит один и тот же путь. Он находит какой-то путь, и этот путь необязательно является кратчайшим. Почему?

Часть 2. Стратегии поиска

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

Секретный ингредиент

В конце предыдущей части я оставил открытыми два вопроса: если каждый алгоритм поиска использует один и тот же код, почему A* ведёт себя как A*? И почему демо иногда находит разные пути?

Ответы на оба вопроса связаны друг с другом. Хоть алгоритм и хорошо задан, я оставил нераскрытым один аспект, и как оказывается, он является ключевым для объяснения поведения алгоритмов поиска:


Именно эта невинно выглядящая строка отличает все алгоритмы поиска друг от друга. От способа реализации choose_node зависит всё.

Так почему же демо находит разные пути? Потому что его метод choose_node выбирает узел случайным образом.

Длина имеет значение

Когда мы рассматривали узлы, соседние с текущим, то игнорировали те, которые уже знаем, как достичь:


Это ошибка: что если мы только что обнаружили лучший способ добраться до него? В таком случае необходимо изменить ссылку previous узла, чтобы отразить этот более короткий путь.

Чтобы это сделать, нам нужно знать длину пути от начального узла до любого достижимого узла. Мы назовём это стоимостью ( cost ) пути. Пока примем, что перемещение из узла в один из соседних узлов имеет постоянную стоимость, равную 1 .

Прежде чем начинать поиск, мы присвоим значению cost каждого узла значение infinity ; благодаря этому любой путь будет короче этого. Также мы присвоим cost узла start_node значение 0 .

Тогда вот как будет выглядеть код:

Одинаковая стоимость поиска

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

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

Вот возможный пример функции choose_node :

Заключение

Простое изменение в способе выбора рассматриваемого следующим узла позволило нам получить достаточно хороший алгоритм: он находит кратчайший путь от начального до конечного узла.

Можно ли сделать choose_node умнее? Можем ли мы сделать так, чтобы он направлял поиск в сторону конечного узла, даже не зная заранее правильного пути?

Оказывается, что можем — в следующей части мы наконец-то дойдём до choose_node , позволяющей превратить общий алгоритм поиска пути в A*.

Часть 3. Снимаем завесу тайны с A*

Полученный в предыдущей части алгоритм достаточно хорош: он находит кратчайший путь от начального узла до конечного. Однако, он тратит силы впустую: рассматривает пути, которые человек очевидно назовёт ошибочными — они обычно удаляются от цели. Как же этого можно избежать?

Волшебный алгоритм

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


Звучит соблазнительно, но магическим чипам всё равно требуется какой-то низкоуровневый код. Вот какой может быть хорошая аппроксимация:


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

Также мы минимизировали количество используемой магии: мы точно знаем, какова стоимость перемещения от начального узла к каждому узлу (это node.cost ), и используем магию только для предсказания стоимости перемещения от узла к конечному узлу.

Не магический, но довольно потрясающий A*

К сожалению, магические чипы — это новинка, а нам нужна поддержка и устаревшего оборудования. БОльшая часть кода нас устраивает, за исключением этой строки:


То есть мы не можем использовать магию, чтобы узнать стоимость ещё не исследованного пути. Ну ладно, тогда давайте сделаем прогноз. Будем оптимистичными и предположим, что между текущим и конечным узлами нет ничего, и мы можем просто двигаться напрямик:


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

Эту оценку получить достаточно просто. В наших примерах с сетками это расстояние городских кварталов между двумя узлами (то есть abs(Ax - Bx) + abs(Ay - By) ). Если бы мы могли двигаться по диагонали, то значение было бы равно sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) , и так далее. Самое важное то, что мы никогда не получаем слишком высокую оценку стоимости.

Итак, вот немагическая версия choose_node :


Функция, оценивающая расстояние от текущего до конечного узла, называется эвристикой, и этот алгоритм поиска, леди и джентльмены, называется … A*.

Интерактивное демо

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

Заключение

Наконец-то мы дошли до алгоритма A*, который является не чем иным, как описанным в первой части статьи общим алгоритмом поиска с некоторыми усовершенствованиями, описанными во второй части, и использующим функцию choose_node , которая выбирает узел, который по нашей оценке приближает нас к конечному узлу. Вот и всё.

Вот вам для справки полный псевдокод основного метода:


А вот метод choose_node , который превращает его в A*:

А зачем же нужна часть 4?

Теперь, когда вы поняли, как работает A*, я хочу рассказать о некоторых потрясающих областях его применения, которые далеко не ограничиваются поиском путей в сетке ячеек.

Часть 4. A* на практике

Первые три части статьи начинаются с самых основ алгоритмов поиска путей и заканчиваются чётким описанием алгоритма A*. Всё это здорово в теории, но понимание того, как это применимо на практике — совершенно другая тема.

Например, что будет, если наш мир не является сеткой?

Что если персонаж не может мгновенно поворачиваться на 90 градусов?

Как построить граф, если мир бесконечен?

Что если нас не волнует длина пути, но мы зависим от солнечной энергии и нам как можно больше нужно находиться под солнечным светом?

Как найти кратчайший путь к любому из двух конечных узлов?

Функция стоимости

В первых примерах мы искали кратчайший путь между начальным и конечным узлами. Однако вместо того, чтобы хранить частичные длины путей в переменной length , мы назвали её cost . Почему?

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

Функция критерия

Допустим, наш объект — это автомобиль, и ему нужно добраться до заправки. Нас устроит любая заправка. Требуется кратчайший путь до ближайшей АЗС.

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

Что если бы мы могли заменить один goal_node на метод, который по заданному узлу может сообщить, является ли тот конечным или нет. Благодаря этому мы сможем искать несколько целей одновременно. Также нам нужно изменить эвристику, чтобы она возвращала минимальную оцениваемую стоимость всех возможных конечных узлов.

Полная определённость не обязательна

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

Но есть проблема и посерьёзней: что если мир бесконечен? В таком случае, даже если мы сможем представить его в виде сетки, то у нас просто не будет возможности построить соответствующий сетке граф, потому что он должен быть бесконечным.

Однако не всё потеряно. Разумеется, для алгоритма поиска по графам нам определённо нужен граф. Но никто не говорил, что граф должен быть исчерпывающим!

Если внимательно посмотреть на алгоритм, то можно заметить, что мы ничего не делаем с графом, как целым; мы исследуем граф локально, получая узлы, которых можем достичь из рассматриваемого узла. Как видно из демо A*, некоторые узлы графа вообще не исследуются.

Так почему бы нам просто не строить граф в процессе исследования?

Мы делаем текущую позицию персонажа начальным узлом. При вызове get_adjacent_nodes она может определять возможные способы, которыми персонаж способен переместиться из данного узла, и создавать соседние узлы на лету.

За пределами трёх измерений

Даже если ваш мир действительно является 2D-сеткой, нужно учитывать и другие аспекты. Например, что если персонаж не может мгновенно поворачиваться на 90 или 180 градусов, как это обычно и бывает?

Состояние, представляемое каждым узлом поиска, не обязательно должно быть только позицией; напротив, оно может включать в себя произвольно сложное множество значений. Например, если повороты на 90 градусов занимают столько же времени, сколько переход из одной ячейки в другую, то состояние персонажа может задаваться как [position, heading] . Каждый узел может представлять не только позицию персонажа, но и направление его взгляда; и новые рёбра графа (явные или косвенные) отражают это.

Если вернуться к исходной сетке 5x5, то начальной позицией поиска теперь может быть [A, East] . Соседними узлами теперь являются [B, East] и [A, South] — если мы хотим достичь F, то сначала нужно скорректировать направление, чтобы путь обрёл вид [A, East] , [A, South] , [F, South] .

Шутер от первого лица? Как минимум четыре измерения: [X, Y, Z, Heading] . Возможно, даже [X, Y, Z, Heading, Health, Ammo] .

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

Заключение

Цель этой статьи — раз и навсегда развеять миф о том, что A* — это некий мистический, не поддающийся расшифровке алгоритм. Напротив, я показал, что в нём нет ничего загадочного, и на самом деле его можно довольно просто вывести, начав с самого нуля.

Дальнейшее чтение

Читайте также: