@ChrisTaker

Помогите пожалуйста написать алгоритм А*

0

@Cyborg Drone

Поиском по форуму пользуйтесь.

Поиск пути (алгоритм А* / Дейкстра)

0

@ChrisTaker

Спасибо)

0

@ChrisTaker

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

0

@Cyborg Drone

Так отобразите граф на матрицу. Какая разница, где путь искать. Ну выводит же, именно через все вершины, которые он проходит. Старт - светло-зелёный, сам путь - зелёный, финиш - красный.

Добавлено через 13 минут
Да, а как у Вас задаётся граф?

0

@ChrisTaker

вообщем задача состоит в том, что у нас есть граф перелетов, ребра имеют вес=время перелта+ожидание, на вершинах указано время ожидания
матрица имеет размерность 33, начало 1 и конец в 33, задаю все константой, остальное задаю большим числом, к примеру миллионом
нужно реализовать алгоритм, по которому на основе время ожидания, будет обходить граф

0

@Cyborg Drone

Что за матрица?

0

@ChrisTaker

вот какая)

Миниатюры

 

0

@Cyborg Drone

Всё думаю-думаю, и никак не могу сообразить, каким образом применить маршрутный алгоритм (которым A* и является) к задаче коммивояжера... Неувязочка получается из-за различного веса рёбер и узлов графа. В принципе, можно, наверное, только вот пока никак не соображу, каким образом впихнуть даже не сам граф, а его элементы, в маршрутный алгоритм...

0

@ChrisTaker

получается если граф денежный, то эвристическая оценкой будет 10 мин лжидания = 1 рубль, првязать так
а вес ребер будет стоимость перелета
агде граф временный то там эвристической оценкой будет являться время ожидания, а вес графа время ожидания+время перелета

0

@Cyborg Drone

В том-то и дело, что разный вес рёбер и вершин... В классическом A* вес рёбер одинаковый, а весов вершин (если это так можно назвать) только два: вершина проходима (вес равен, к примеру, 1) и вершина непроходима (вес вершины равен бесконечности).

И ещё, отображение графа на сетку (необходимое для A*) не всегда может быть изоморфным, даже если увеличить количество измерений сетки или применить какое-либо аффинное преобразование, поскольку если отображение гомоморфное, то, как над ним не колдуй, оно, скорее всего, таковым и останется. А раз так, то возможно ложное отсечение ветвей графа из-за образования островков клеток открытого списка среди клеток закрытого списка. Тогда найденный путь вполне может быть не кратчайшим, ошибка, по сути, будет возникать из-за того, что кратчайший путь далеко не всегда содержит рёбра с минимальным весом.

Ну и... Пока никаких идей нет. Если просто с графом - тогда никакого A*, Гамильтоновы циклы и куча алгоритмов на выбор. Если A* - тогда непротык с самим алгоритмом, особенно если граф непредставим в виде дискретной сетки из-за того, что все веса не являются (равномерно дискретным) счётным множеством, и / или если рёбра графа не позволяют отобразить его на сетку с конечным и целым количеством измерений.

0