Архив форумов ЦИТФорума

[Splint]

У кого-нить есть идеи по решению этой задачи.
Задача: Необходимо решить с помощью рекурсии.
Имеется n населенных пунктов, пронумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Определить, можно ли попасть по этим дорогам из 1-го пункта в n-й. Информация о дорогах задается в виде последовательности пар чисел i и j (i<j), указывающих, что i-й и j-й пункты соединены дорогой.

Заранее СПАСИБО!

[Bjorndalen]

Я бы решал эту задачу следующим образом:
1. Встаем на пункт 1;
2. Выбираем ближайший путь (например из 1-7, 1-3 и 1-48 выбираем 1-3);
3. Переходим по выбранному пути на следующий пункт (в нашем случае 3), при этом сохраняем всю последовательность(П) пунктов от начала до текущего (то есть храним 1, 3);
4. Для каждого следующего пункта придерживаемся правил:
а) Если доступных путей нет, то возвращаемся в предыдущий пункт, последний использованный путь удаляем из списка доступных и корректируем последовательность(П);
б) Проверяем не встречался ли этот пункт в нашей последовательности (П), если да (зацикливание), то выполняем те же действия, что при условии "а)";
в) Берем ближайший доступный путь и переходим по нему (см. 2);
5. Действия повторяем до тех пор, пока либо не достигнем пункта N либо не останется доступных путей из пункта 1.

[Mytilus Galloprovincialis]

Одновременно с этим ведем точно такой маршрут от конечного пункта к начальному и ищем совпадения в обоих маршрутах. Тогда положительный ответ (если он существует) найдется быстрее.

[Bjorndalen]

[Mytilus Galloprovincialis]

Действительно, некорректно выразился. Я имел в виду что чередовать движения "от начального - к конечному" и "от конечного к начальному", например, пошагово.

[Bjorndalen]

-> Mytilus Galloprovincialis
Возможна такая ситуация, что существует более одного пути и тогда может получиться, что мы по разным путям придем к концу (началу), затратив при этом вдвое больше времени! Или вообще придем в тупик в одном из направлений...
Так что на, мой взгляд, так делать не следует!