Назад до змісту

Вычисления в идемпотентных алгебрах

12.1 Тропические алгебры

Определены следующие тропические алгебры :

ПОЛУПОЛЯ 1) На множестве целых чисел Z определены:\ ZMaxPlus, ZMinPlus. 2) На множестве чисел R определены: RMaxPlus, RMinPlus, RMaxMult, RMinMult. 3) На множестве чисел R64 определены: R64MaxPlus, R64MinPlus, R64MaxMult, R64MinMult.

ПОЛУКОЛЬЦА 1) На множестве целых чисел Z определены:\ ZMaxMin, ZMinMax, ZMaxMult, ZMinMult. 2) На множестве чисел R определены: RMaxMin, RMinMax. 3) На множестве чисел R64 определены: R64MaxMin, R64MinMax.

Примеры тропических алгебр:

SPACE = ZMaxPlus [x, y, z];

SPACE = R64MinMult [u, v];

SPACE = RMaxMin [u, v].

Пример простой задачи в полукольце ZMaxMult.

Доки немає результату

Помимо сложения и умножения доступна операция замыкания, вызываемая командой closure(a), где a — элемент или матрица. Замыкание closure(a)=1aa2

Доки немає результату

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

Доки немає результату

12.2 Решение систем линейных алгебраических неравенств

Команда solveLAITropic(A,b) позволяет найти решение неравенства Ax b.

Доки немає результату

Доки немає результату

12.3 Решение уравнения Беллмана

Однородное уравнение Беллмана

Команда BellmanEquation(A) позволяет найти решение однородного уравнения Беллмана Ax=x.

Доки немає результату

Неднородное уравнение Беллмана

Команда BellmanEquation(A,b) позволяет найти решение неоднородного уравнения Беллмана Axb=x.

Доки немає результату

12.4 Решение неравенства Беллмана

Однородное неравенство Беллмана

Команда BellmanInequality(A) позволяет найти решение однородного неравенства Беллмана Axx.

Неднородное неравенство Беллмана

Команда BellmanInequality(A,b) позволяет найти решение неоднородного неравенства Беллмана Axbx.

12.5 Нахождение кратчайшего пути между вершинами графа

Вычисление таблицы кратчайших расстояний для всех вершин графа

Пусть A - матрица расстояний между смежными вершинами (xii=0 i; xij=, если нет ребра, соединяющего вершины i и j). Команда searchLeastDistances(A) позволяет найти наименьшие расстояния между всеми вершинами графа. В результате будет получена матрица кратчайших расстояний между вершинами.

Доки немає результату

Нахождение кратчайшего пути между двумя вершинами графа

Пусть A - матрица расстояний между смежными вершинами (xii=0 i; xij=, если нет ребра, соединяющего вершины i и j). Команда findTheShortestPath(A,i,j) позволяет найти кратчайший путь между вершинами i и j.

Доки немає результату

Назад до змісту