Цитата:
Задан произвольный ненаправленный граф:
Множество вершин(станций): [A,B,C,D....]
а также, множество связей(перегонов): [{start: A, end: B},{start: D, end: A}, {start: B, end: C}....]
(start и end роли не играют, т.е. start: A, end: B равносильно start: B, end A). Связи разумеется уникальны, т.е. две любых вершины может связывать только одна связь.
- (задача 2) Необходимо разработать алгоритм, который графически представит данный граф,
причем расставит вершины и соединит их линиями так, что количество пересечений между связями(линиями),
соединяющими вершины графа должно быть в идеале минимально возможным.
- (задача 1) Предварительно необходимо разработать алгоритм, наиболее точно рассчитывающий
минимально возможное количество пересечений между линиями в (задаче 2) для заданного набора вершин и связей.
- (задача 3) Необходимо разработать алгоритм - модель поезда метро, который пытается проехать
максимальное количество перегонов между станциями(связей между вершинами графа) так, чтобы
не попасть дважды на одну станцию(в одну вершину). За одну итеррацию объект может переместиться на любую соседнюю вершину.
- (задача 4) Необходимо разработать алгоритм - модель поезда метро, который пытается проехать все перегоны между станциями так, чтобы
минимальное суммарное количество раз попадать на одну и ту же станцию(речь идет о каждом повторном попадании на разных вершинах, а не об одной какой-то вершине).
- (задача 5) Необходимо разработать алгоритм, при котором поезд метро должен попасть кратчайшим возможным путем из А в Б(если это возможно), причем дополнительно может быть задано сколько угодно пунктов С, Д, Е из множества вершин графа,
попадения в которые поезд должен избежать.
- (задача 6) Необходимо разработать алгоритм, расчитывающий количество возможных маршрутов из А в Б при условии непопадания в одну вершину дважды
- (задача 7) Необходимо разработать алгоритм, при котором из двух разных точек А1 и А2 одновременно для каждой итеррации движутся два поезда. В сумме они должны объехать максимальное количество станций так,
чтобы на любой из станций мог побывать лишь один из них и исключительно один раз.
- (задача 8) Необходимо разработать алгоритм, при котором поезд движется из А в Б, причем некоторое количество от общего вершин графа(эти вершины выбираются случайным образом) работает так, что при попадении на такую вершину
поезд телепортируется назад в вершину А. Про положение вершин-ловушек заранее поезду ничего неизвестно.
- (задача 9) Необходимо разработать алгоритм, при котором поезд должен проехать все станции, причем поезд достаточнно странный - при движении он всегда перепрыгивает через 1 соседнюю станцию, не попадая на нее.
Если поезд находится на станции и из соседней больше некуда ехать(соответственно перепрыгнуть он не может), только тогда поезд попадает на соседнюю станцию.
- (задача 10) Необходимо разработать алгоритм расчета маршрута при котором два поезда должны попасть из А1 и А2 в Б, причем сделать это так, чтобы в одной вершине мог побывать только один из них и только один раз.
В качестве примера графа можете использовать например карту московского метро, впрочем граф и непосредственно входные данные используемые в задаче могут быть заданы любые.