Я вот думал думал, гуглил, так и не получил просветления.
Предполагаю что создается массиов в котором указываются значения типа
=> Город 1
- Пригород 1
- Пригород 2
=>Пригород 1
- Город 3
=>Город 3
А вот как реализовать поиск по этому масиву я не допер. по сути должны шагать так: из Города 1 в Пригород 1 и только тогда попадаем в Город 3.... таких *точек* примерно 20 шт. вот надо как то из любой точки в другую попадать, при этом записывать через какие другие проходим.
я не прошу вас писать скрипт, просто натолкните меня на мысль, может кто-то сталкивался уже стаким, в какую сторону копать (может в сети похожий скрипт лежит?)?
предполагаю что это осуществляется циклом с ифом, но как его прописать...
Спустя 46 минут, 47 секунд (17.02.2011 - 17:43) Michael написал(а):
для научного интереса можешь сюда капнуть.
А так вообще:
1) хранятся данные:
причем зеркально, т.е. (город1 город2 расстояние) и (город2 город1 расстояние)
2) запоминаем текущий вес найденного пути. В начале - 0. Чтобы отбрасывать менее эффективные
3) стартуем с города A.
4) работать будет рекурсия - для текущей точки перебираем соседние.
Причем для текущего шага передаем предыдущий путь и его длину
5) останов рекурсии - естественно когда не куда идти или в точку где уже был или в точку назначения.
6) При приходе в точку назначения сверяем - меньше ли прошлых найденных.
Рассуждаю не теоретически :) , делал раньше подобное: тут глянь, (Загрузить демо-план, а потом в расчет).
А так вообще:
1) хранятся данные:
город1 город2 расстояние
.. .. ..
причем зеркально, т.е. (город1 город2 расстояние) и (город2 город1 расстояние)
2) запоминаем текущий вес найденного пути. В начале - 0. Чтобы отбрасывать менее эффективные
3) стартуем с города A.
4) работать будет рекурсия - для текущей точки перебираем соседние.
Причем для текущего шага передаем предыдущий путь и его длину
5) останов рекурсии - естественно когда не куда идти или в точку где уже был или в точку назначения.
6) При приходе в точку назначения сверяем - меньше ли прошлых найденных.
Рассуждаю не теоретически :) , делал раньше подобное: тут глянь, (Загрузить демо-план, а потом в расчет).
Спустя 5 дней, 16 часов, 25 минут, 34 секунды (23.02.2011 - 10:09) gaserge написал(а):
спасибо! погулил и нашел даже готовый скрипт исходник, может кому пригодится:
http://cleonty.narod.ru/articles/graph.html
все предельно понятно единственное не разобрался в двух моментах:
1. в синтаксисе
что делает & перед $solns?
2. допустим я в исходный масив
хочу еще к каждому пункту добавить дополнительные характеристики, типа времени или координат... этот момент не получается, допустим создаю дополнение
скрипт перестает работать, я предпологаю в обработчиках этот момент надо как то обыграть... не допер.
http://cleonty.narod.ru/articles/graph.html
все предельно понятно единственное не разобрался в двух моментах:
1. в синтаксисе
function generate($path, $goal, &$solns, $graph)
что делает & перед $solns?
2. допустим я в исходный масив
$Graph = array( 'A' => array('B', 'E', 'G'),
'B' => array('C'),
'C' => array('D', 'E'),
'D' => array('F'),
'E' => array('C', 'F', 'G'),
'F' => array(),
'G' => array('A') );
хочу еще к каждому пункту добавить дополнительные характеристики, типа времени или координат... этот момент не получается, допустим создаю дополнение
'B' => array('C' => array( 'size' = 2, 'name' = 'Город1' ), и т.д.
скрипт перестает работать, я предпологаю в обработчиках этот момент надо как то обыграть... не допер.
Спустя 2 дня, 4 часа, 26 минут, 53 секунды (25.02.2011 - 14:36) Guest написал(а):
подскажите хотя бы что делает & перед $solns? с другимто разбераться можно и другим способом...