 |  | ||
 главная | избранное | настройки | об ALT-форуме |
Страницы форума: ← Назад | 1 … 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 … 600 | Дальше →
Опять рекурсия.. | ||
osatuk | 15.08.04 20:19 / 20:21 www.parser.ru → | ответить → | | |
Опять рекурсия.. | ||
| Подскажите пожалуйста алгоритм. Задачка следующая. Есть карта с комнатами (схематично ниже =] ), между некоторыми есть переходы, между некоторыми нет. Надо отыскать путь из любой выбранной комнаты в любую. Я сделал таблицу со всеми "дверьми" комнат: id from to 1 1 2 2 1 5 3 2 1 4 3 7 5 4 8 6 5 1 7 5 9.. и так все. Но дальше, как бы я не вызывал рекурсивно функцию она выдает ошибку endless рекурсии.. Подскажите, плз.. .---. .---. .---. .---. | 1 |=| 2 | | 3 | | 4 | .-|-. .---. .-|-. .-|-. .-|-. .---. .-|-. .-|-. | 5 | | 6 |=| 7 |=| 8 | .-|-. .-|-. .---. .-|-. .-|-. .-|-. .---. .-|-. | 9 |=| 10| | 11|=| 12| .---. .---. .---. .---. | ||
| osatuk | → osatuk [1] | 15.08.04 20:45 www.parser.ru → | ответить → | | |
Вроде разобрался, но появился другой вопрос.. | ||
Для начала, грубо, получилась следующая функция:@find[f;t][tbl] $tbl[^table::sql{select * from tower where _from = $f}] ^if($f == $t){$ok[1]} ^if($ok == 0){ ^tab.append{$f} ^tbl.menu{ ^if(!^tab.locate[old;$tbl._to]){ ^find[$tbl._to;$t]} } } , но вопрос в том, как сохранить только правильный путь и отбросить ветви приводящие в тупик? Да, комнат всего 60, а не 12 как в примере, так что есть тупики.. | ||
| Oleg | → osatuk [2] | 15.08.04 23:35 www.parser.ru → | ответить → | | |
Что такое тупик? | ||
| начальный пункт != конечному | ||
| serglif | → osatuk [2] | 16.08.04 14:34 www.parser.ru → | ответить → | | |
| У меня был похожий курсовик лет 5 назад. Алгоритма не найду, не сохранился, но кое-что могу рассказать: 1. Не берусь утверждать за оптимальность подхода, но теория предлагала нам решать такие задачи через матрицы смежности из теории графов. В вашем случае вершины графа это комнаты, а ребра двери меду ними. Матрица смежности это таблица, где в i-ой строке и j-ом столбце стоит 1, если вершины i и j смежны. В вашем случае для вершин 1-2-3-4-5-6-7-8 имеем что-то типа: . 1 . . 1 . . . 1 . . . . . . . . . . . . . 1 . . . . . . . . 1 1 . . . . . . . . . . . . . 1 . . . 1 . . 1 . 1 . . . 1 . . 1 . Вот с такими таблицами обычно работают в данных случаях. 2. Я насколько помню обходился без рекурсии. Строил динамический массив путей, который в цикле продлевал по матрице смежности. 3. Тупик очевидно при таком подходе - когда в строке матрицы нет единиц, кроме как в позиции, равной предыдущему пункту пути. Вообщем и целом - вам очевидно нужна теория графов. :) | ||
| Temp | → osatuk [1] | 16.08.04 19:59 www.parser.ru → | ответить → | | |
сведем задачу к предыдущей (графы, сэр!) :) | ||
| ваша задачка - это не что иное как классическая задача «Задача о кратчайших путях» на графах. Почитать для вас тут | ||
| |||
 | |||