Привет. Дали задание "Написать программу нахождения пути из города А в город Х с использованием алгоритма А*. Количество городов не менее 10. Программу написать на языке программирования C#". До этого было задание сделать решение лабиринта на основе бинарной матрицы с использованием слепого рекурсивного поиска в глубину и оно проблем не вызвало. А над этим уже несколько дней голову ломаю. Насколько я понял, прошлую программу не переделаешь под это задание, так как, скорее всего, бинарная матрица тут уже не подойдет и нужен будет граф, а эвристический поиск должен включать в себя стоимость каждого из путей. Я пытался найти уже готовый код, но там никто не указывает заранее стоимость путей. Да и в целом, код завуалирован и только варианты на пайтоне кажутся не сложными. Но переводить код с языка, где нет жесткой типизации сложно, особенно не понимая, что происходит. Может у Вас есть какие - то мысли?

Алгоритм А* в качестве входных данных требует оценку

Отсюда вопрос: в каком виде представлены входные данные?

На это ограничения нет. Но я представлял реализацию в виде ориентированного графа. Вершины графа - города. Стоимостью может считаться либо расстояние города либо стоимость проезда в город.

Либо двумерный массив с городами и у каждого [i][j] есть стоимость

Вы понимаете, что если бы для произвольного графа можно было построить эту оценку, то алгоритм А* не требовал бы построение оценки на вход?

Я на данном этапе мало чего понимаю. Но на Википедии есть подобный пример.

а что тут нарисовано вы понимаете? h(x) и веса графа это геометрическое расстояние между точками на рисунке

алгоритм А* для этого случая работает, собственно, как дейкстра по "аномалии" геометрического расстояния - весом ребра вместо d(from, to) считается d(from, to) + d(to, target) - d(from, target)

А что за минус в конце? Или это тире/равенство?

Ничего, что это вообще-то от способа хранения матрицы зависит, от языка программирования немного?
И от способа кэширования ещё? Нет?

неправильно.

Кормен Лейзерсон, Риверст Штайн.

конечно зависит. Я говорил о хранении "как сишный типа двумерный массив"

А там было в вопросе слово "СИШНЫЙ" ?

Компьютер, архитектура указывались?

нет, но человека мой ответ удовлетворил

Когда уже поймёте, что кэш -- это неуправляемая и абсолютно прозрачная для работы программы структура, бессмысленно предсказывать его поведение.

А , ну да, ну  да

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