|
OFF: Неисследованные лабиринты, туман. Какие алгоритмы используются? |
☑ |
0
Aceforg
04.03.15
✎
14:59
|
В задачах на прохождение лабиринта, когда лабиринт задан полностью, все просто. Но в некоторых контестах лабиринт не дается полностью - его надо исследовать по мере прохождения. Как называются на английском задачи на такую тематику? Какие алгоритмы используются? Что почитать можно на такую тему?
|
|
1
Волшебник
модератор
04.03.15
✎
15:00
|
Алгоритм правой руки
|
|
2
Волшебник
модератор
04.03.15
✎
15:00
|
или левой стенки
|
|
3
Ёпрст
гуру
04.03.15
✎
15:03
|
волновой алгоритм
|
|
4
Aceforg
04.03.15
✎
15:04
|
(1) Об этом думал в первую очередь. Но в лабиринтах с большими комнатами он не эффективен.
|
|
5
СвинТуз
04.03.15
✎
15:05
|
это реально лабиринт
обход замкнутого контура
а если поиск на карте , это сложнее будет
вспомнилось :
компакт содержит все свои концы = замкнутое компактное множество содержит все свои точки сгущения
|
|
6
Ненавижу 1С
гуру
04.03.15
✎
15:07
|
*
*
|
|
7
СвинТуз
04.03.15
✎
15:07
|
|
|
8
СвинТуз
04.03.15
✎
15:11
|
"Поиск в глубину"
помнится была онлайн игра "Тайм зеро"= точка отсчета
так там видимо программист эксперементировал с оптимизацией
алгоритма поиска. Пошел по пути поиска в глубину.
И крысы циклились. Т.е. подобно буреданову ослу не могли выбрать направление.
Такой был баг. Был довольно долго. Только года через 2-3 его убрали. Но там и хозяева сменились.
|
|
9
Aceforg
04.03.15
✎
15:15
|
(6)(7) Совсем не то. Нужно про исследование лабиринтов, карт, по мере прохождения, т.е. ничего не знаем о лабиринте. Алгоритмы поиска пути гуглятся на раз два.
|
|
10
Aceforg
04.03.15
✎
15:48
|
(6) За "Jump Point Search" спасибо, не знал про него
|
|
11
Grekos2
04.03.15
✎
15:48
|
(1) 100% Годится только для лабиринта в одной плоскости.
|
|
12
Aceforg
04.03.15
✎
16:02
|
Нашел *
входит в класс Incremental heuristic search
|
|
13
Krendel
04.03.15
✎
16:09
|
(11) конечно, ведь присутсвует 2-рность, если хочешь алгоритм перебора с n-м пространством, то тогда используй n-1 условий выхода
|
|