УДК 372.8

ЭКСПЕРИМЕНТ НА ЗАНЯТИЯХ ПО ИНФОРМАТИКЕ

Лялин Андрей Васильевич
Вятский государственный университет
магистрант кафедры прикладной информатики

Аннотация
В статье мы рассказываем о том, как организовать эксперимент на уроках информатики.

Ключевые слова: , ,


Рубрика: 13.00.00 ПЕДАГОГИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Лялин А.В. Эксперимент на занятиях по информатике // Современные научные исследования и инновации. 2018. № 1 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2018/01/85647 (дата обращения: 25.09.2018).

Актуальность

С одной стороны, в своей работе [2] польский педагог Винценты Оконь озвучил и обосновал следующий тезис. Образование тем успешнее и тем больше развивает интеллект, чем больше ученик попадает на тот путь, по которому идёт учёный в ходе исследования.

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

Рисунок. 1. Полный цикл научного познания

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

Далее мы приводим пример такой задачи.

Задача о минимальном штрафе

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

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

Точный алгоритм для задачи о минимальном штрафе. Динамическое программирование

Для примера возьмём следующую таблицу штрафов.

Заведём дополнительный двумерный массив B, размерами n на m. В него будем записывать решения подзадач. Пусть B[i,j] – это минимальный штраф от клетки (1,1) до (i, j).

Наша цель – найти B[n,m]. Заполняем массив постепенно.

Очевидно, есть один способ добраться до клетки (1,1). Штраф, который при этом придётся заплатить, равен числу, записанному в этой клетке. B[1,1]=A[1,1].

В любую клетку первой строки (1,j), кроме первой, можно прийти из клетки левее – из (1,j-1). Поэтому B[1,j]=B[1,j-1]+A[1,j]. По этой формуле вычисляем первую строку массива B.

В любую клетку первого столбца (i,1), кроме первой, можно прийти из клетки выше – из (i-1,1). То есть B[i,1]=B[i-1,1]+A[i,1]. По этой формуле находим первый столбец массива B.

В любую оставшуюся клетку можно шагнуть либо из клетки левее, либо из клетки выше – либо из (i, j-1), либо из (i-1,j). Выгоднее выбрать ту, где штраф минимален.

Значит, B[i,j]=min{B[i,j-1], B[i-1,j]}+A[i,j]. По этой формуле определяем оставшиеся элементы массива B. Строка за строкой.

Итак, минимальный штраф за весь путь хранится в клетке B[n,m] и равен 13 .

Приближенный алгоритм для задачи о минимальном штрафе. Муравьиный алгоритм

Алгоритм имитирует поведение колонии муравьёв [1, 4]. Колония муравьев легко находит кратчайший путь от муравейника к пище. Вначале муравьи двигаются произвольно. При этом оставляя за собой дорожки из особых веществ – феромонов. Нашедшие самый короткий путь к «кормушке» успевают по нему пробежать больше раз. Путь становится всё заметнее. Привлекает муравьев. Они всё чаще сворачивают на него. На остальных путях феромон постепенно испаряется и они исчезают. Через некоторое время, большинство муравьёв передвигаются по одному кратчайшему пути.

Как использовать этот факт для решения задачи? Запустим муравьев из первой клетки. И пусть они бегают по различным возможным маршрутам. На дешёвых оставляют больше феромона. На дорогих – меньше. Через некоторое время их остановим. Наилучший маршрут, который они найдут, и будем считать решением задачи.

Алгоритм.

1. Строим случайный маршрут. Считаем его наилучшим. Пусть Q – его стоимость.

2. Задаем начальный уровень феромона. Вводим ещё одну таблицу F, размерности n*m. Вначале в каждую её клетку записываем одно и то же небольшое положительное число. Поэтому при первом запуске муравьи будут двигаться произвольно, «не принюхиваясь».

3. Выбираем коэффициент испарения феромона p, из промежутка (0;1). Чем больше возьмём p, тем быстрее будет происходить испарение.

4. Повторяем k раз (k можно считать временем жизни муравьиной колонии).

    4.1. Запускаем d муравьёв от стартовой клетки. Они пробегают до финиша. Для каждого находим маршрут и его стоимость.

Как муравей, путешествуя, определяет следующую клетку? По методу «рулетки». Возможным клеткам ставим в соответствие сектор рулетки. Чем больше феромона, тем больше сектор. Запускаем рулетку. Случай выбирает одну клетку. В неё и отправляется муравей.

   4.2.  Если какой-то муравей нашёл лучший маршрут, чем ранее, то запоминаем стоимость этого маршрута.

   4.3.  Увеличиваем феромон вдоль всех маршрутов, по которым прошли муравьи. Берём первого муравья, просматриваем клетки из его маршрута и на каждое добавляем феромон. По формуле F[i,j]:=F[i,j]+Q/L, где Lстоимость маршрута. Затем берём второго муравья и так далее. Тем самым, на лучших (дешёвых) маршрутах оставляем больше феромона.

   4.4.  Испаряем феромон во всех клетках. По формуле F[i,j]:=(1-p)*F[i,j].  Таким образом, постепенно удаляем клетки, которые меньше всего используются.

5. Выводим стоимость наилучшего маршрута.

Параметры p, k и d подбираем эмпирически.

Эксперимент

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

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

Поделиться в соц. сетях

0

Библиографический список
  1. Джонс М.Т. Программирование искусственного интеллекта в приложениях.  М.:ДМК-Пресс, 2004.
  2. Оконь В. Основы проблемного обучения. М.: Просвещение, 1968.
  3. Окулов С. М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний, 2002.
  4. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. 2003. №4. с.70-75.


Количество просмотров публикации: Please wait

Все статьи автора «Лялин Андрей Васильевич»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

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

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться:
  • Регистрация