Карты метро и нейронные сети. Теория графов
Шрифт:
* * *
ТЕОРИЯ ИГР
Теория игр была создана Джоном фон Нейманом и Оскаром Моргенштерном с целью разработки новых моделей для решения экономических задач. Развитие этой теории позволило использовать ее не только в экономике, но и в социологии, политике, маркетинге, финансах, психологии и других областях.
Изначально создатели теории игр полагали, что «типичные задачи, в которых рассматривается экономическое поведение, полностью идентичны математическому представлению соответствующих стратегических игр». На основе этого сравнения стало возможным проанализировать игры для одного и нескольких игроков, ввести понятие функции
Так как в общем случае число «игроков» (инвесторов, работников, банков) является конечным, так же как и число игр, стратегий и возможных вариантов, то при анализе задач теории игр часто применяется теория графов.
* * *
Интенсивное развитие теории графов на протяжении всего XX века и ее применение во множестве самых разных задач пробудили интерес к преподаванию этой дисциплины в высшей школе.
Курс «Теория графов и ее применение» сегодня изучается как часть курса математики, исследования операций, дискретной математики, входит в программу различных инженерных специальностей (строительство, электроэнергетика, телекоммуникации) и, разумеется, в курс информатики.
Однако до сих пор не решен вопрос о преподавании теории графов в старшей школе. Речь не идет о том, чтобы изучать теорию графов в том же объеме, что и арифметику или геометрию, однако различные эксперименты в сфере образования показывают, что элементы теории графов имеют высокую образовательную ценность и должны быть включены в школьную программу.
Среди преимуществ теории графов применительно к образованию выделим следующие.
1. Графы часто представляют собой прекрасные примеры математических моделей. Несмотря на простоту графов, с их помощью можно описывать и изучать интересные реальные ситуации.
2. Графы — прекрасный пример использования математики в повседневной жизни. Они помогают увидеть, что математика постоянно присутствует в окружающем нас мире.
3. Изучение графов стимулирует индуктивное, комбинаторное и пространственное мышление, что имеет высокую образовательную ценность.
4. Графы помогают решать занимательные и прикладные задачи. Благодаря работам Дьёрдя Пойа мы знаем, что решение задач — один из двигателей обучения математике.
С учетом вышесказанного будет уместно привести цитату из «Алисы в стране чудес» Льюиса Кэрролла, где Алиса разговаривает с Котом:
«— Скажите, пожалуйста, куда мне отсюда идти?
— А куда ты хочешь попасть? — ответил Кот.
— Мне все равно… — сказала Алиса.
— Тогда все равно, куда и идти, — заметил Кот».
Путь, которым должно следовать образование, подразумевает качественное обучение для всех. Образование должно гарантировать актуальность теоретических и практических знаний. Нельзя, чтобы школьная программа ограничивалась рассмотрением задач столетней давности, чтобы в ней не рассматривались важные современные задачи.
Развитие информатики привело к тому, что многие математические модели стали использоваться в автоматических процессах (выполняемых машинами), которые, безусловно, способствуют прогрессу. Учитывая невероятную сложность человеческого мозга, модели искусственного интеллекта должны содержать нетривиальные способы обработки данных. Машина легко справляется с вычислениями, но порекомендовать один из нескольких возможных вариантов — задача намного более сложная.
На начальном этапе развития искусственного интеллекта особое внимание привлекали так называемые экспертные системы — программы, которые на основе знаний людей-экспертов могли давать рекомендации, помогающие принимать решения. Экспертные системы имели особый успех в медицине: они помогали ставить диагноз с учетом определенных параметров на основе множества реальных историй болезни. Появились и другие алгоритмы, например генетические, в которых используются механизмы, напоминающие биологическую эволюцию. В генетических алгоритмах случайные ситуации обрабатываются статистическими методами и влияют на алгоритм решения конкретной задачи. Эти алгоритмы применяются в эволюционном и генетическом программировании. Графы в них используются как способ визуализации процессов. В свою очередь, эти алгоритмы, которые можно встретить в различных системах, сетях, в задачах прогнозирования и других, также связаны с теорией графов, теорией игр и логикой.
Моделирование нейронов человеческого мозга и принципа их действия легло в основу новой теории, известной как теория искусственных нейронных сетей, или просто теория нейронных сетей.
Нейронная сеть состоит из единичных элементов, называемых нейронами, которые получают входные сигналы и выдают результат — выходной сигнал. Между нейронами существуют различные взаимосвязи, сами нейроны могут объединяться в слои. В нейронах могут использоваться функции распределения или веса, присваиваемые входным значениям (функции распределения могут изменяться и применяться только к определенным множествам значений). В классическом программировании конкретный алгоритм по очереди выполняет определенные действия и вычисляет результат на основе входных значений. Нейронная же сеть может «обучаться» автоматически на основе больших объемов данных, а затем обрабатывать новые входные данные на основе изученных. Заметим, что в этой теории не только проводится аналогия с нейронами человеческого мозга, но также используются те же понятия, что и при обучении людей: «обучение», «гибкость», «терпимость», «самоорганизация».
Анализ медицинских изображений, распознавание рукописных текстов и голоса, управление работой электростанций, принятие инвестиционных решений, интеллектуальный анализ крупных баз данных, контроль работы промышленных предприятий — теория нейронных сетей находит интересное применение в этих и многих других областях. Очевидно, что нейронные сети можно объединять с экспертными системами, генетическими алгоритмами и другими методами, например нечеткой логикой, в которой значения истинности лежат на интервале между 0 и 1.
Многие нейронные сети можно представить с помощью ориентированных графов: дуги будут обозначать связи между нейронами, их входы и выходы. Подобно схемам метро с линиями и станциями, с помощью графов можно составить схемы нейронных сетей. Иногда нейронную сеть удобнее представить не в виде графа, а в виде электронной таблицы. Чем больше число входных сигналов, нейронов и взаимосвязей между ними, тем сложнее процесс.
Классификацию нейронных сетей можно выполнить по аналогии с графами, разделив нейронные сети на сети прямого распространения (такие сети не содержат циклов и связей между нейронами одного слоя) и рекуррентные, в которых существует минимум один цикл. Нейронные сети также можно классифицировать по типу «обучения» или ввести другие критерии, например тип обрабатываемой ими информации (изображение, речь и так далее).