Отправлено Дятковский Степан 22 апреля 2006 г. 19:28 В ответ на: С рекурсией еще проще: Для каждой вершины вызываешь функцию заливки из данной. отправлено <font color=gray>Дятковский Степан</font> 22 апреля 2006 г. 19:18

Начинаешь из той вершины из которой хочешь отправиться.
1. Вызываешь для всех вершин в которые можно попасть из данной функцию заливки.
2. Если заливаемая вершина уже была залита прежде - заливку из данной осуществляешь только в том случае, если новая заливка оптимальнее старой (опитимизация по расстоянию, например). При заливке также, как и в том алгоритме надо указыать место, откуда призошла наиоптимальнейшая заливка (тоесть при перезаливке эти данные надо обновлять)
3. Если заливка происходит, то для залитой вершины осуществляешь те же самые действия, что и для данной (пункты 1-3).

Для той вершины из которой путь начинается это будет вызов одной единственной функции. Анализируешь информацию, которую туда принесла (или не принесла) волна. Выстраиваешь маршрут. Он и будет оптимальным.

• а это уже целая программа, а не простенькая функция — -=DASM=-   (22.04.2006 19:33 212.58.192.14, пустое)
  • Ну, блин ) Поиск пути это не очень-то простое занятие. А вообще, то фунцию на С можно уложить в 40-50 строк + структуры вспомогательные еще строк 20. Просто глаза стращают, наверное ;-) — Дятковский Степан   (22.04.2006 19:37 81.28.163.175, пустое)
    • что-то у меня тут не сколько рекурсия напрашивается (представляем бинарное дерево) сколько распаллеливание процессоров :-( То есть рекурсия идет вверх однобоко, а надо бы к кроне двигать горизонатльно, чтобы быстрее найти верный путь — -=DASM=-   (22.04.2006 19:50 212.58.192.14, пустое)
      • я имел в виду - на какой платформе? МК? ПК? или что ? — Дятковский Степан   (22.04.2006 20:45 81.28.174.237, пустое)
        • и МК и ПК.. какая разница... ну стека больше 30 кил все равно не хочу — -=DASM=-   (22.04.2006 20:57 212.58.192.14, пустое)
          • Кроме волнового алгоритма поиска маршрута по графу больше ниче не могу предложеть. Если получится как-то по-другому, поделишься? — Дятковский Степан   (22.04.2006 21:14 81.28.187.169, пустое)
            • по всем прикидкам мне подходит просто перебор вариантов =( — -=DASM=-   (23.04.2006 08:41 212.58.192.14, пустое)
              • Построить цепь при помощи перебора? А как будешь перебирать? Там же граф.. — Дятковский Степан   (23.04.2006 11:06 81.28.185.180, пустое)
                • так а чего ? (+) — -=DASM=-   (23.04.2006 11:59 212.58.192.14, 184 байт)
                  • Для той задачи по-моему красивее некуда :-) 0 - это идти в одну сторону 1 - в другую. Так я понял ? Только надо знать максимально возможную длину маршрута. Но вообще красиво. Чего не нравится-то ? — Дятковский Степан   (23.04.2006 15:56 81.28.162.97, пустое)
                    • тепрь все нравится =) — -=DASM=-   (23.04.2006 16:47 212.58.192.14, пустое)
      • Ну рекурсия - это просто поиск в глубину - отсюда кажущаяся однобокость. На самом деле она и "в стороны" ищет. Только к новой стороне она переходит только после того, как решит все со старой. Здесь это на самом деле немного стремно. На мой взгляд фронты очен неплохи. И распаралеливание на лицо. А на чем должен быть реализован поиск ? — Дятковский Степан   (22.04.2006 20:43 81.28.174.237, пустое)
        • тут у меня ситуация осложняется что некоторые ветви тупиковые... да и цепь замкнута.. — -=DASM=-   (22.04.2006 20:58 212.58.192.14, пустое)
          • Если ветви тупиковые заливка из заданной вершины не будет происходить. Если цепь замкнута, то когда повторно вершина тоже не будет залита, по скольку условие оптимальности для такой заливки не будет выполняться - то есть в цикл алгоритм тоже не впадет. — Дятковский Степан   (23.04.2006 16:20 81.28.162.97, пустое)
• Все зависит от средней длины маршрута. Если маршрут не большой - то лучше рекурсию. Если происходит переполнение стека - можно делать с помощью фронтов. Максимальный размер фронта в случае приведенного графа будет 10-20 вершин. — Дятковский Степан   (22.04.2006 19:31 81.28.163.175, пустое)

E-mail: info@telesys.ru