Вы можете основывать свое решение на алгоритмах, найденных в «Введение в алгоритмы» Кормена, Лизерсона, Ривеста и Стейна, 2-е издание. В главе 24 они анализируют алгоритм «кратчайшие пути из одного источника», а в 24.3 у вас есть Дейкстра.
Я буду использовать псевдокод здесь. Вы можете заменить приведенную ниже очередь с минимальным приоритетом другой структурой данных, такой как карта в Java. Это не будет быстро, но это будет работать, и это может быть удовлетворительной первой попыткой. У меня также есть Java-реализация очереди с минимальным приоритетом, если хотите.
Скажем, у вас есть лабиринт, представленный двумерным массивом, как в вашем коде: int [M] [N] лабиринт. Первый индекс - это индекс строки, а второй - индекс столбца, начиная с нуля. Таким образом происходит от 0 до M-1 для строк и от 0 до N-1 для столбцов. Значение лабиринт [строка] [столбец] представляет опасность, связанную с комнатой в (строка, столбец). Нам нужно удобное представление, чтобы определить вес между двумя комнатами в лабиринте и узнать, какие комнаты соседствуют с конкретной комнатой.
Идея состоит в том, чтобы сгладить массив и поместить каждую строку рядом: row1, row2, ..., rowM. Тогда мы можем дать индекс i для каждой комнаты. Чтобы использовать эту идею, нам нужно преобразовать координаты разных типов: (строка, столбец) -> i и i -> (строка, столбец).
convert_to_index(row, column) ::= row * N + column
convert_to_pair(i) ::= (i div N, i modulo N)
Скажите РАЗМЕР M * N, общее количество комнат в лабиринте.
Теперь мы можем создать матрицу смежности, представляющую лабиринт со значениями опасности: int [SIZE] [SIZE] adjacency_matrix, первый индекс - FROM, второй - TO. В клетке мы находим стоимость или вес, чтобы перейти из одной комнаты в другую. Обратите внимание, что с учетом конкретной комнаты, есть только несколько комнат, которые примыкают к этой комнате. Другие комнаты в лабиринте не доступны из этой комнаты. По соглашению мы будем использовать самое большое целое число, чтобы указать это, и использовать константу INFINITY. Другие значения представляют опасность и находятся в диапазоне от 0 до 9. Матрица будет разреженной, и существуют методы для ее оптимизации.
Когда у нас есть комната, расположенная в (r, c), какие комнаты рядом с ней? Мы хотим, чтобы вектор индексов использовался непосредственно в нашем алгоритме. Если мы не принимаем во внимание границы лабиринта, мы имеем: (r-1, c-1), (r-1, c), (r-1, c + 1), (r, c-1) , (r, c + 1), (r + 1, c-1), (r + 1, c) и (r + 1, c + 1). Затем мы можем применить convert_to_index к каждому из них, проверить, что они находятся в диапазоне 0..SIZE-1, и инициализировать матрицу с этим. Таким образом, например, переход от (r, c) к (r-1, c-1) имеет стоимость или опасность лабиринта [r-1, c-1] и переход от (r-1, c-1) к (r, c) имеет стоимость лабиринта [r, c]. Но переход из (r, c) в другую отдаленную комнату стоит 10, он недоступен, и обратное верно.
adjacent_rooms(r, c) ::=
Given the vector [(r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1,c+1)]
Filter it by deleting pairs whose row is not in 0..M-1 or whose column is not in 0..N-1
Then apply the function convert_to_index to each resulting pair (map operation)
Return the result
for i in 0..SIZE-1 loop
for j in 0..SIZE-1 loop
adjacency_matrix[i, j] := -1
end loop
end loop
for i in 0..SIZE-1 loop
(current_r, current_c) := convert_to_pair(i)
adjacent_room_indexes := adjacent_rooms(current_r, current_c)
for j in 0..SIZE-1 loop
if adjacency_matrix[i, j] == -1 then
(r, c) := convert_to_pair(j)
if i == j then adjacency_matrix[i, j] := 0
elsif j in adjacent_room_indexes then adjacency_matrix[i, j] := maze[r, c]; adjacency_matrix[j, i] := maze[current_r, current_c]
else adjacency_matrix[i, j] := INFINITY
end if
end loop
end loop
Далее нам нужны векторные оценки кратчайших путей (см. Стр. 585 книги) и вектор предшественников (см. Стр. 584 книги).
for i in 0..SIZE-1 loop
predecessors[i] := NONE
estimates[i] := INFINITY
end loop
Переход от начала к началу стоит 0.
estimates[0] := 0
Инициализировать набор вершин, принадлежащих MST (минимальное связующее дерево)
mst := empty set
Инициализирована очередь с минимальным приоритетом q
for i in 0..SIZE-1 loop
q.add(i, estimates[i])
end loop
until q.empty? loop
u, u_d = q.delete_min
mst.add(u)
(current_r, current_c) := convert_to_pair(i)
adjacent_room_indexes := adjacent_rooms(current_r, current_c)
for i in 0..adjacent_room_indexes.length-1 loop
v := adjacent_room_indexes[i]
cost = adjacency_matrix[u, v]
if cost < q[v]
predecessors[v] = u
estimates[v] = c
q[v] = c
end
end loop
end loop
Работа выполнена. У нас наш путь в predecessors с затратами в estimates.
Это может быть излишним, а A * может быть лучше. Но я думаю, что использование Dijkstra было требованием вашей домашней работы. Если вы хотите изучить A *, я предлагаю вам взглянуть на A * Pathfinding для начинающих и Amit's A * Pages .