Языком дисциплины является Python – один из самых распространённых в мире языков программирования. Плюсами языка являются:
Для научно-исследовательских задач рекомендуется установить платформу Anaconda.
Рабочей версией Python для этой дисциплины выберем версию 3.4 и выше.
Python отличается от большинства языков программирования одной интересной особенностью: в нём вложенные блоки кода выделяются не ключевыми словами (begin/end в Pascal) и не специальными символами ("{" и "}" в C/C++), а равными отступами. Такой подход даёт коду программы хорошо узнаваемый аккуратный вид и добавляет лаконичности. За исключением этой детали большинство конструкций Python покажутся знакомыми любому, кто имел дело с современными высокоуровневыми языками.
Операция присваивания в Python – это обычный знак равенства:
a = 5 # целочисленная переменная
b = 3.14 # переменная с плавающей точкой
c = "String-42" # строковая переменная
Обратите внимание на решётку – в Python так начинается комментарий.
result_1 = a + b # результат любой операции с участием целочисленной переменной и
# переменной с плавающей точкой -- значение с плавающей точкой
b *= 3.14 # операция "умножить на значение и записать в ту же переменную";
# есть аналоги для всех арифметических операторов
c = c + "; new string" # для строк оператор "+" склеивает строки
print(result_1) # результатом выполнения этой строки будет число 8.14, выведенное на экран
Метод format замены шаблонов в строке делает вывод сложных конструкций более удобным, чем классическая конкатенация. Сравните:
degrees = 27
drinks = ["квас", "чай"]
print("На улице {0} градусов, поэтому рекомендуем выбирать {1}.".format(degrees, drinks[0]))
print("На улице " + str(degrees) + " градусов, поэтому рекомендуем выбирать " + drinks[0] + ".")
Обе команды выведут один и тот же текст, но первая выглядит аккуратнее.
import math # такой вариант импортирует все модули, содержащиеся в библиотеке
math.sin(math.pi) # так можно использовать импортированный указанным способом модуль
Если из библиотеки требуется только одна-две функции или несколько классов, их можно импортировать с указанием их имени:
from math import sqrt
Если какой-либо модуль называется длинно и неудобно, а использовать его нужно часто, пригодится возможность создания синонимов (alias) для импортированных модулей:
import matplotlib.pyplot as plt
Полная форма условной конструкции:
if a > c:
print(a)
elif a == c:
print("Hi!")
else:
print(c)
Можно опускать как elif, так и else ветки условной конструкции. Обратите внимание на сдвиги! Все вложенные блоки обязательно сдвигаются на один и тот же отступ (по стандарту форматирования PEP 8, принятому в Python-сообществе, величина сдвига составляет 4 пробела. Ваш редактор кода, скорее всего, уже настроен на использование кнопки Tab для автоматической вставки четырёх пробелов.
Кроме того, заметьте, что все строки с ключевыми словами (if, elif, else) оканчиваются двоеточием. Оно показывает, что дальше начинается вложенный блок кода.
Допустимые операторы в условии:
Константами истинности являются True и False.
В Python есть два основных типа циклов:
Скажем, чтобы напечатать значения в диапазоне от 0 до 15, можно написать следующее выражение:
for i in range(16):
print(i)
Класс range генерирует целые числа от 0 до аргумента. Обратите внимание, что само значение аргумента не включается в последовательность.
Если вам требуется не только само значение элемента, но и его позиция в составном типе, пользуйтесь функцией enumerate:
for i, elem in enumerate([4, 7, 9]):
print("Элемент {0} имеет номер позиции {1}".format(elem, i))
Пример цикла while:
k = 0
while k < 10:
print("Это строка номер {0}".format(k))
k += 1
Функции объявляются ключевым словом def. После него следует название функции, за которым в скобках через запятую перечислены аргументы. Тип аргументов не указывается. В конце строки ставится двоеточие.
def move(direction, state):
# некоторая обработка аргументов
return new_state
После ключевого слова return прописывается возвращаемая переменная. Строки, находящиеся на том же уровне вложенности, что и return, и расположенные ниже неё не выполняются.
Если нет аргументов, то в скобках не прописываеся ничего. Если нечего возвращать, то return не используется. Пример:
def say_hi():
print("Hi!")
В Python есть слегка урезанная форма лямбда функций, которые, однако, могут пригодиться:
f = lambda x: x * 25
print("Результат выполнения лямбда-функции с аргументом, равным 10: {}".format(f(10)))
Список – самый распространенный тип данных в Python. В чём-то он напоминает динамические массивы, однако его "изнанка" совсем другая, а способов использования гораздо больше. Список задаётся перечнем элементов в квадратных скобках. Типы элементов могут быть какими угодно, даже другими списками:
list_example = ["I'm the first element (index 0)", 10, 3.1415926, -1, 'k', [1, 2, 3]]
Индексация начинается с 0. Вы можете обратиться к элементу списка, используя квадратные скобки:
print(list_example[2]) # Выведет 3.1415926
В Python работают срезы, возвращающие списки элементов:
print(list_example[1:3]) # Выведет [10, 3.1415926]. Заметьте, последний индекс не включается!
print(list_example[:3]) # Выведет ["I'm the first element (index 0)", 10, 3.1415926]
print(list_example[1:]) # Выведет [10, 3.1415926, -1, 'k', [1, 2, 3]]
Чтобы обратиться к элементу вложенного списка, индекс этого элемента указывается во вторых квадратных скобках:
print(list_example[5][1]) # Выведет 2
Длину списка (и любого другого составного типа данных) можно проверить функцией len:
print(len(list_example)) # Выведет 6
Список может менять размеры в процессе работы.
Основные методы работы со списками описаны в документации в п. 4.6.1 и п. 4.6.3.
Кортеж по функциональности совпадает со списком, однаке его элементы нельзя изменять. Кортеж записывается в круглых скобках:
tuple_example = ("Tuple", 10, "can", -1, "not", 24.1, "be", 123, "changed.")
Со строками вы уже познакомились чуть выше.
Строка во многом ведёт себя как кортеж, то есть является неизменяемой, и при этом к её элементам можно обращаться в квадратных скобках.
В строке могут содержаться специальные управляющие символы, такие как '\n' (переход на новую строку) или '\t' (символ табуляции).
Ниже кратко описаны основные полезные методы работы со строками. Пусть задана некоторая строка:
s = "Важные исследования задерживаются из-за того, что в одной области неизвестны результаты, уже давно ставшие классическими в смежной области"
Метод, разбивающий строку по указанному разделителю на подстроки:
L = s.split(',')
Результатом будет список вида
["Важные исследования задерживаются из-за того", " что в одной области неизвестны результаты", " уже давно ставшие классическими в смежной области"]
Метод, возращающий True, если вся строка содержит только числовые символы:
print(s.isdigit()) # Результатом будет False
Метод, возвращающий позицию подстроки в строке:
print(s.find('ы')) # Результатом будет 4, т.к. подстрока 'ы' встречается в строке на 4-й позиции
Если подстрока не найдена, метод find вернёт -1.
Подробнее смотрите в документации.
Словарь — одна из самых интересных и удобных структур данных, которые есть в Python. Если вам знаком формат JSON, структура и синтаксис словаря практически ему идентичны. Словарь содержит пары «ключ-значение». По ключу можно обратиться к значению. Ключом может быть любой неизменяемый тип данных.
Объявить пустой словарь можно так:
my_dict = dict()
или так
my_dict = {}
Непустой словарь выглядит, к примеру, так:
my_dict = {"First": 1, "Second": [1, 2, 3], "Fox": "rabbit", 5: '#'}
Так можно вывести значение, соответствующее ключу:
print(my_dict["Fox"])
Sokoban (Soko-Ban, яп. 倉庫番 — «кладовщик») была создана в 1981 году Хироюки Имабаяси, и издана в 1982 году для компьютеров серии NEC PC-8801. Головоломка часто попадала в фокус внимания исследователей. Например, было доказано, что в двумерном варианте игра является NP-трудной. Термин "NP-трудность" означает, что любая задача из класса NP за полиномиальное время может быть сведена к этой задаче.
Основная задача головоломки – размещение ящиков по указанным местам на уровне. Агент (игрок; мы будем часто называть игроков "агентами") может перемещаться в четырёх направлениях: вверх, вниз, влево, вправо. При перемещении агент может двигать ящик, если переместится в его направлении, находясь к нему вплотную (см. рисунок 1).
Для головоломки создано множество разнообразных уровней.
В основном, уровни хранятся в текстовом формате со стандартизированными обозначениями основных элементов:
| Символ | Обозначение |
|---|---|
| # | Стена |
| . | Пустая цель |
| @ | Игрок на полу |
| + | Игрок на цели |
| $ | Ящик на полу |
| * | Ящик на цели |
| - | Пол |
Таким образом, уровень является решённым, если на нём не осталось ни одного символа "$".
Для хранения уровней часто используют так называемый Run-Length Encoding (RLE, последовательное кодирование), при котором уровень записывается в строку. Например, уровень
###
#.###
#*$ #
# @ #
#####запишется как
3#|#.3#|#*$-#|#--@#|5#Последовательность одинаковых символов заменяется на цифру и символ, где цифра указывает общее количество последовательных символов.
Строки уровня отделяются друг от друга символом |.
Решение уровня можно представить в виде последовательности перемещений агента. Традиционно используют первые буквы английских слов, обозначающих направления: u (up, вверх), d (down, вниз), l (left, влево), r (right, вправо).
Для уровня, приведенного выше, одним из возможных решений будет строка
ludrrulЭто решение является оптимальным с точки зрения количества ходов.
Задачи на поиск оптимальной дискретной последовательности действий можно решить многими способами. К поисковым алгоритмам относят алгоритмы информированного и неинформированного поиска на графе, эволюционные методы, игровые алгоритмы.
В лабораторной работе №1 вашей задачей будет разработка и исследование одного из методов поиска на графе состояний игры Sokoban. Граф состояний – это граф, в узлах которого находятся различные конфигурации среды (в нашем случае уровня игры), а дуги (граф направленный) показывают, в какое состояние можно перевести головоломку, совершив одно из разрешённых действий. Для Sokoban разрешённым действием является премещение игрока (возможно, с ящиком) в одном из четырёх направлений. То есть в таком графе каждый узел будет иметь не больше четырёх исходящих дуг.
Рассматриваемые алгоритмы поиска:
Варианты 1-2 дадут максимум 8 баллов, варианты 3-4 – 10 баллов. Выбор варианта пройдёт на основе результатов опроса на занятии.