xmoonlight
@xmoonlight
https://sitecoder.blogspot.com

Как максимально быстро найти точку на верном пути прохождения лабиринта?

Всех приветствую.

Есть лабиринт:
004_3.gif
Ответ
004_3a.gif

Стрелки в шестигранниках - определяют возможные направления перемещения.
Количество стрелок в одном направлении - определяет количество шагов до остановки при движении в указанном направлении (например, три стрелки - только на три клетки).

Вход - серый шестигранник со стрелками, слева.
Выход - серый шестигранник без стрелок, справа.

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

Какой алгоритм наиболее быстро сможет решить эту задачу? (и можно ли значительно сократить время поиска, используя асинхронность или волны?)
Спасибо!
  • Вопрос задан
  • 459 просмотров
Решения вопроса 1
Дополню ответ Сергей .
Алгоритм Флойда-Уоршалла оперирует при расчете расстояниями между 3мя точками и матрицу надо будет всю просчитывать. Алгоритм Беллмана-Форда в основном применяют для графов с отрицательными весами у ребер- он ищет циклы, применение его на этом примере- ну такое. Алгоритм Дейкстры использует обход в ширину(BFS), т.е. просчитывает весь граф просто с положительными весами в отличии от Беллмана-Форда.
Поэтому если вам не важен оптимальный путь(читай кратчайший), то воспользуйтесь обходом графа в глубину(DFS)- он в среднем быстрее скажет дойдете ли вы, т.е. за минимальное кол-во проверок при поиске.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 3
@SilentFl
дополню ответ rPman - поиск в ширину в данном случае является самым быстрым. Не совсем понимаю почему
Думал уже - долгий он!
, потому как сложность O(V+E), где V - количество вершин, а E - количество ребер; для данного случая V=70, E=138, вообще копейки. Может не совсем верно его понимаете?
Покажу как я делал - для начала построил список смежности для этого графа, пронумеровал вот так:
5d7a11f738975303023774.gif
получился
список смежности
1: 2 9
2: 6 14
3: 12 22
4: 9 20
5: 7 26
6: 11 13
7: 5 3
8: 4 16
9: 8 30
10: 5 20
11: 18 7
12: 11 26
13: 8 15
14: 22 18
15: 22 24
16: 22 45
17: 5 19
18: 12 40
19: 20 29
20: 21 10
21: 42 23
22: 23 3
23: 33 21
24: 32 35
25: 8 35
26: 12 39
27: 36 48
28: 47 7
29: 28 61
30: 20 14
31: 28 54
32: 55 53
33: 30 34
34: 46 16
35: 34 46
36: 38 26
37: 29 27
38: 48 49
39: 20 65
40: 30 66
41: 64 43
42: 54 39
43: 40 14
44: 43 46
45: 33 46
46: 34 44
47: 17 28
48: 40 37
49: 47 51
50: 37 52
51: 50 27
52: 60 19
53: 65 67
54: 53 42
55: 22 70
56: 48 57
57: 56 28
58: 57 39
59: 62 30
60: 59 65
61: 58 42
62: 41 69
63: 67 31
64: 68 60
65: 69 66
66: 67 54
67: 66 53
68: 
69: 65 66
70: 69 63

и простая реализация bfs на ruby
data = File.read('input.txt').split("\n").map { |line| line.split(":") }.map {|item| [item[0].to_i, item[1].split(' ').map(&:to_i)]}.to_h
puts data # {1=>[2, 9], 2=>[6, 14], 3=>[12, 22], ...

queue = [1]
visited = [1]
prev_vertex = {1 => -1}

while queue.any?
  vertex = queue.shift
  data[vertex].each do |neightbor_vertex|
    next if visited.include?(neightbor_vertex)
    queue << neightbor_vertex
    visited << neightbor_vertex
    prev_vertex[neightbor_vertex] = vertex
  end
end

vertex = 68
path = []
while vertex != -1
  path << vertex
  vertex = prev_vertex[vertex]
end

puts path.reverse

коду на этом графе надо 68 шагов для прохода вперед, и 35 обратно (для построения списка вершин в оптимальном пути),
ответ
1
2
6
13
15
24
32
55
70
63
31
28
47
17
19
29
61
58
57
56
48
37
27
36
38
49
51
50
52
60
59
62
41
64
68
такой же.

Если я не так понял вопрос или линейная сложность - все еще долго, то стоит уточнить размерность графа, и думать в сторону parallel bfs
Ответ написан
@rPman
Обычный поиск в ширину с пометками о прохождении, так как у вас нет весов на ребрах, найдет оптимальный путь 'быстрее' всего. Вы не можете дать ответ, находится ли данная ячейка на оптимальном пути, пока его не найдете, поэтому - во время поиска в ширину у вас список текущих решений, как только хотя бы одно решение найдено, вы прекращаете поиск и проверяете, находится ли указанная вершина на одном из пути (их может быть несколько одновременно).
Ответ написан
Star_Lord
@Star_Lord
Думаю нужно создать граф где каждая клетка связана с другими на которые указывает и каким нибудь алгоритмом найти путь.

Вот такими

А может есть и лучше
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы