Замыкание транзитивного бинарного отношения

Какое-нибудь описание.

Домашнее задание

  1. {i} Почитать про Алгоритм Флойда–Уоршелла и Алгоритм Дейкстры в Википедии

  2. Дана таблица, содержащая стоимость проезда из города i в город k по N городам (необязательно симметричная). Проезд стоит от 1 до 1000р, если проезда нет, в таблице записано N**2*1000. Вводятся два номера городов -- A и B. Вычислить минимальную стоимость проезда из A в B с учётом пересадок.
    • Решение фактически совпадает с описанием алгоритма floyd-warshell.py

  3. Решить данным алгоритмом задачу о длине минимального пути в лабиринте
    • Алгоритм придётся модифицировать с учётом доступности клеток лабиринта. Получится алгоритм Дейкстры (см. выше) labdijkstra.py

    • Новая версия генератора лабиринтов (третий параметр включает непроходимость): labpur.py

Условные обозначения


CategoryClass CategoryVmsh

LecturesVMSH/2011-12-07 (last edited 2011-12-14 10:37:36 by FrBrGeorge)