Лабиринты

From

Nicolas Kuhtenko (2:5090/118.7)

To

Andrew Evdokimov

Date

2002-11-19T23:27:54Z

Area

RU.ALGORITHMS

 Ответ на письмо из TO_ALL

      How are you, Andrew?

 Andrew Evdokimov, ты посмел(а) написать письмо to All:

AE> Такой вот вопрос - каким образом лучше всего представлять 3-мерные
AE> лабиринты, имеющие толщину стен? Какие существуют алгоритмы поиска выхода
AE> из такого лабиринта? Интересуют варианты поиска выхода от входа и из

можно расставить точки в начале-конце и в перекрестках, построить булеву матрицу н*н, где н - число таких точек, А(i,j)=1 если из i можно попасть в j не проходя других точек, иначе 0 (это будет матрица инцидентности в графе) а потом стандартными алгоритмами ищем решение. А вот точки расставлять и матрицу делать придется руками, хотя не очень сложно можно сделать алгоритм генерации матрицы.

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

---
 * Origin: 111 (2:5090/118.7)