Отправлено Дятковский Степан 22 апреля 2006 г. 18:37 В ответ на: Найти путь. Красиво. (+) отправлено -=DASM=- 22 апреля 2006 г. 17:52

Напоминает волновой алгоритм поиска пути. Их мне известно два вида: 1 рекурсивный; 2 на основе старого и нового волновых фронтов. К этому алгоритму я частенько прибегаю. Прикрепил там ссылку на свою статью. Может поможет )
Но вообще странно, что есть только два выхода... тоесть граф вырождается в цепь, получается. Что тогда считать расстоянием ? Можно поподробнее описать задачу?

• http://gaze.narod.ru/find_way.html

• Прогнал я, что немного ниже не взглянул. Вот алгоритм: — Дятковский Степан   (22.04.2006 18:56 81.28.174.129, 1337 байт)
  • много памяти, хотелось бы с рекурсией, красиво... — -=DASM=-   (22.04.2006 19:03 212.58.192.14, пустое)
    • С рекурсией еще проще: Для каждой вершины вызываешь функцию заливки из данной. — Дятковский Степан   (22.04.2006 19:18 81.28.163.175, пустое)
      • Да со стеком ты прав. То сообщение не до конца отправилось. Вот рекурсивный алгоритм: — Дятковский Степан   (22.04.2006 19:28 81.28.163.175, 807 байт)
        • а это уже целая программа, а не простенькая функция — -=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, пустое)
      • да понятно что все просто.. но не выходит каменный цыеток.. то тут грабли, то тут stack overflow, то находит только путь по одной стороне.... а функция явно строк 20 не более должна быть — -=DASM=-   (22.04.2006 19:21 212.58.192.14, пустое)
• расстоянием считать минимальное количество изменений TMS — -=DASM=-   (22.04.2006 18:42 212.58.192.14, пустое)
  • на волновой похоже, но с реализацией чего-то торможу.. То что я написал по одной ветви нашло путь, потом пошло по другой ветке (а вдруг она короче) и зациклилась. То есть надо как-то помечать уже пройденные состояния чтобы не ходить по кругу — -=DASM=-   (22.04.2006 18:45 212.58.192.14, пустое)
    • Глянь алгоритм поиска номеров подключенных Далласовских градусников 1820, очень похоже. — Russ   (22.04.2006 19:19 85.249.59.145, пустое)
      • а где посмотреть? (я в даласе не ориентируюсь) — ы   (22.04.2006 19:20 80.92.98.211, пустое)
        • Я давно видел в датшите на 18в20 есть алгоритм — Russ   (22.04.2006 19:22 85.249.59.145, пустое)
          • аа...фунrция search rom? понял — ы   (22.04.2006 19:24 80.92.98.211, пустое)
            • Вроде, не открыть датшит, 7 ридер глючит — Russ   (22.04.2006 19:28 85.249.59.145, пустое)

E-mail: info@telesys.ru