|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nicolas Kuhtenko 2:5090/118.7 20 Nov 2002 00:27:54
To : Andrew Evdokimov
Subject : Лабиринты
--------------------------------------------------------------------------------
How are you, Andrew?
Andrew Evdokimov, ты посмел(а) написать письмо to All:
AE> Такой вот вопрос - каким образом лучше всего представлять 3-мерные
AE> лабиринты, имеющие толщину стен? Какие существуют алгоритмы поиска выхода
AE> из такого лабиринта? Интересуют варианты поиска выхода от входа и из
можно расставить точки в начале-конце и в перекрестках, построить булеву матрицу
н*н, где н - число таких точек, А(i,j)=1 если из i можно попасть в j не проходя
других точек, иначе 0 (это будет матрица инцидентности в графе) а потом
стандартными алгоритмами ищем решение. А вот точки расставлять и матрицу делать
придется руками, хотя не очень сложно можно сделать алгоритм генерации матрицы.
Хотя подумав второй раз придумал решение чисто числовое, хотя и ресурсоемкое:
делаем то-же, что и в первом случае, только точки ставим предельно часто
(растояние между соседними должно быть меньше чем самый маленький проход в
лабиринте) тогда их расстановку можно доверить компьютеру и алгоритм составления
матрицы упрощается (ставим точки только на постоянном растоянии друг от друга,
при соблюдении постоянной взаимной ориентации соседних). Теперь у нас есть
большущая матрица, ее отличие в том, что в графе который ею кодируется от входа
до выхода можно пройти разными путями - по стандартному алгоритму (кажется
Дейкстры и т.п.) находим кратчайшее расстояние.
---
* Origin: 111 (2:5090/118.7)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Лабиринты 
