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

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

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

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

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

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

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

Какой алгоритм наиболее быстро сможет решить эту задачу? (и можно ли значительно сократить время поиска, используя асинхронность или волны?)
Спасибо!
  • Вопрос задан
  • 372 просмотра
Пригласить эксперта
Ответы на вопрос 4
@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
Ответ написан
Дополню ответ Сергей .
Алгоритм Флойда-Уоршалла оперирует при расчете расстояниями между 3мя точками и матрицу надо будет всю просчитывать. Алгоритм Беллмана-Форда в основном применяют для графов с отрицательными весами у ребер- он ищет циклы, применение его на этом примере- ну такое. Алгоритм Дейкстры использует обход в ширину(BFS), т.е. просчитывает весь граф просто с положительными весами в отличии от Беллмана-Форда.
Поэтому если вам не важен оптимальный путь(читай кратчайший), то воспользуйтесь обходом графа в глубину(DFS)- он в среднем быстрее скажет дойдете ли вы, т.е. за минимальное кол-во проверок при поиске.
Ответ написан
@rPman
Обычный поиск в ширину с пометками о прохождении, так как у вас нет весов на ребрах, найдет оптимальный путь 'быстрее' всего. Вы не можете дать ответ, находится ли данная ячейка на оптимальном пути, пока его не найдете, поэтому - во время поиска в ширину у вас список текущих решений, как только хотя бы одно решение найдено, вы прекращаете поиск и проверяете, находится ли указанная вершина на одном из пути (их может быть несколько одновременно).
Ответ написан
Star_Lord
@Star_Lord
Думаю нужно создать граф где каждая клетка связана с другими на которые указывает и каким нибудь алгоритмом найти путь.

Вот такими

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

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

Войти через центр авторизации
Похожие вопросы
от 80 000 до 140 000 руб.
Poteha Labs Москва
от 100 000 до 160 000 руб.
HttpLab Ростов-на-Дону
от 60 000 до 150 000 руб.