Алгоритм поиска графика
Короче говоря,
В фрагменте объявите Fragment fragment = this;
после этого используйте fragment.startActivityForResult.
Результат вернется в activityResult.
5 ответов
Принятие Вас не имеет никакой эвристики, изменение алгоритма dijkstra должно быть достаточным вполне прилично. Каждый раз Вы рассматриваете новый край, храните информацию о ее "предках". Затем проверьте на инвариант (только одно изменение направления), и отслеживание в обратном порядке, если это нарушено.
Предки здесь являются всеми краями, которые были пересечены для получения до текущего узла вдоль кратчайшего пути. Один хороший способ хранить информацию предка был бы как пара чисел. Если U произошел, и D снижается, предки конкретного края могли бы быть UUUDDDD, который был бы парой 3, 4. Вам не будет нужно третье число из-за инварианта.
Так как мы использовали алгоритм dijkstra, нахождение, что несколько кратчайших путей уже заботятся о.
Возможно, можно преобразовать график в нормального ориентированного графа и затем использовать существующие алгоритмы.
Один путь состоял бы в том, чтобы разделить график на два графика, один с весь края и один с весь вниз края и с ориентированными ребрами между всеми узлами на графике один и соответствующим узлом на графике два.
Сначала решите для запуска в графике один и окончание в графике два и затем наоборот, затем проверьте самое короткое решение.
* со специально обработанной стоимостью (G счет) и эвристика (H счет) функция может обработать его.
Для стоимости Вы могли отслеживать количество изменений направления в пути и добавить бесконечную стоимость на втором изменении (т.е. отключить поиск тех ответвлений).
Эвристика берет еще некоторую мысль, особенно когда Вы хотите сохранить эвристику допустимой (никогда не переоценивает минимальное расстояние до цели), и монотонный. (Только способ гарантировать* находит оптимальное решение.)
Возможно, существует больше информации о домене, доступном для создания эвристики? (т.е. x, y координаты узлов в графике?)
Конечно, в зависимости от размера графика Вы хотите решить, Вы могли сначала попробовать более простые алгоритмы как поиск в ширину или алгоритм Dijkstra: в основном каждый алгоритм поиска сделает, и для всех, кого Вам будет нужна функция стоимости (или подобный) так или иначе.
Можно было бы думать, что Ваш стандартный BFS должен работать здесь. Каждый раз, когда Вы добавляете узел к открытому списку, можно перенести его в структуру, которая содержит, какое направление он использует (или вниз) и булев флаг, указывающий, переключил ли он направления уже. Они могут использоваться для определения, какие исходящие края от того узла допустимы.
Для нахождения всех кратчайших путей равной длины включайте количество краев, пересеченных до сих пор в структуре. Когда Вы находите свой первый самый короткий путь, обращаете внимание на длину пути и прекращаете добавлять узлы к открытому списку. Продолжайте проходить остающиеся узлы в списке, пока Вы не проверили все пути текущей длины, затем остановитесь.
Если у вас есть стандартная функция поиска по графу, скажем Graph.shortest (from, to) в библиотеке, вы можете выполнить цикл и свести к минимуму в C # / псевдокоде:
[ (fst.shortest(A, C) + nxt.shortest(C, B))
for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)
Если вам нужно запомнить минимальный путь / пути и так случилось, что ваша стандартная функция возвращает вам данные, вы также можете произнести
[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)
, где myMin должен сравнить два [fst, nxt , C, AC, BD] кортежей и оставьте тот, который имеет меньшее расстояние, или и то, и другое, и предполагая, что reduce является умной функцией.
Это имеет некоторые накладные расходы на память, если наши графики большие и не использовать память вообще (что возможно, если они генерируются динамически), но на самом деле никаких накладных расходов на скорость, imho.