В задачах на прохождение лабиринта, когда лабиринт задан полностью, все просто. Но в некоторых контестах лабиринт не дается полностью - его надо исследовать по мере прохождения. Как называются на английском задачи на такую тематику? Какие алгоритмы используются? Что почитать можно на такую тему?

Алгоритм правой руки

или левой стенки

волновой алгоритм

(1) Об этом думал в первую очередь. Но в лабиринтах с большими комнатами он не эффективен.

это реально лабиринт
обход замкнутого контура

а если поиск на карте , это сложнее будет

вспомнилось :
компакт содержит все свои концы = замкнутое компактное множество содержит все свои точки сгущения

http://habrahabr.ru/post/162915/
https://ru.wikipedia.org/wiki/Алгоритм_поиска_A*
http://en.wikipedia.org/wiki/B*
http://habrahabr.ru/post/198266/

http://igropolis.com/articles/47103/Algoritm_poiska_puti_Igrovoi_konstruktor_chast_4.htm

"Поиск в глубину"
помнится была онлайн игра "Тайм зеро"= точка отсчета
так там видимо программист эксперементировал с оптимизацией
алгоритма поиска. Пошел по пути поиска в глубину.
И крысы циклились. Т.е. подобно буреданову ослу не могли выбрать направление.
Такой был баг. Был довольно долго. Только года через 2-3 его убрали. Но там и хозяева сменились.

(6)(7) Совсем не то. Нужно про исследование лабиринтов, карт, по мере прохождения, т.е. ничего не знаем о лабиринте. Алгоритмы поиска пути гуглятся на раз два.

(6) За "Jump Point Search" спасибо, не знал про него

(1) 100% Годится только для лабиринта в одной плоскости.

Нашел http://en.wikipedia.org/wiki/D*
входит в класс Incremental heuristic search

(11) конечно, ведь присутсвует 2-рность, если хочешь алгоритм перебора с n-м пространством, то тогда используй n-1 условий выхода