Замыкание транзитивного бинарного отношения
Какое-нибудь описание.
- Подтема 1
Подтема 2
Домашнее задание
Почитать про Алгоритм Флойда?Уоршелла и Алгоритм Дейкстры в Википедии - Дана таблица, содержащая стоимость проезда из города i в город k по N городам (необязательно симметричная). Проезд стоит от 1 до 1000р, если проезда нет, в таблице записано N**2*1000. Вводятся два номера городов -- A и B. Вычислить минимальную стоимость проезда из A в B с учетом пересадок.
Решение фактически совпадает с описанием алгоритма floyd-warshell.py
- Решить данным алгоритмом задачу о длине минимального пути в лабиринте
Алгоритм придется модифицировать с учетом доступности клеток лабиринта. Получится алгоритм Дейкстры (см. выше) labdijkstra.py
Новая версия генератора лабиринтов (третий параметр включает непроходимость): labpur.py
Условные обозначения
- ? тема по Linux
?? необязательная тема - ? теоретическое задание
? тема для самостоятельного изучения