Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Поиск путей, имеющего максимальное число общих пунктов с заданным 16.10.06 16:30 Число просмотров: 3725 [whiletrue]
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
|
Представим множество точек, они не имеют координат, просто каждая точка связана (двухсторонне) с одной (двумя или больше) "соседними" точками. "Путь" - это подмножество соседних (каждая, кроме крайней, непосредственно связана с предыдущей и последующей) точек, которые связаны в определённом порядке. Пусть есть множество таких путей.
Теперь возьмём один путь. Нужно ранжировать (или хотя бы найти первые N) все остальные пути по признаку совпадения с заданным путём. Совпадение мыслится как общие точки пути, следующие в том же порядке. Т.е.
Пути 1-2-3-4-5 и 2-3-4-5-6 имеют общие точки 2-3-4-5 и довольно неплохо совпадают.
А пути 1-2-3-4 и 4-3-2-1 хоть и имеют все общие точки, но совершенно не совпадают.
Соответственно нужен алгоритм быстрого поиска наиболее совпадающих путей.
Дальше хуже. Эти пути нужно хранить в реляционной БД. Этот поиск - основная задача, так что способ хранение путей в БД можно выбрать такой, какой удобно для этой задачи.
Скажите, куда копать, чего набирать в гугле и вообще.
Заранее спасибо.
|
- Поиск путей, имеющего максимальное число общих пун... - ZloyShaman 16.10.06 16:30 [3725]
|
|
|