|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Если все нужны, тогда и циклы нужны, и комбинации циклов. А так да, алгоритмов дофига, и зачем было здесь спрашивать? ... |
|||
:
Нравится:
Не нравится:
|
|||
15.10.2021, 17:03 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Имя пользователя1 как я понял, нужны все пути в заданные вершины, а не только кратчайшие. Тогда простая рекурсия. Но она зациклится есть есть хоть одно кольцо. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.10.2021, 13:56 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Имя пользователя1 Dimitry Sibiryakov Ищет кратчайшие пути из заданной вершины графа в любую другую. "всех" путей может оказаться бесконечно много. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.10.2021, 16:01 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Если хороводы кругами не не накручивать, бесконечностей не будет. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.10.2021, 22:21 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
exp98 Если хороводы кругами не не накручивать, бесконечностей не будет. Тогда в задаче следует указать "не накручивая хороводы". Иначе непонятно будет чего хотят. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.10.2021, 00:09 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
Сделал примерно так: Поиск в глубину запоминает альтернативные вершины для продолжения поиска в стеке. При прохождении вершины в ней запоминается глубина стека. На каждом шаге сначала проверяем это значение для новой вершины - В. Если вершину не посещали - запоминаем глубину и продолжаем. Иначе просматриваем все вершины и заменяем значение в них на мин(В, значение вершины) (**) И специальные значения если через вершину (не) проходит путь ведущий к выходу. Проблематично как мне видится действие (**). Просмотр всех N вершин в худшем случае выполнится N раз. В итоге O(N^2) Можно ли сделать быстрее? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 09:12 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
В коде нагляднее. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 09:25 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, вот вы упёртый, почитайте описание Алгоритм Бржозовского, это всего лишь модифицированный алгоритм распрастранения в вашем случае он выполняется за O(N) выполняется он максимум в 4 цикла, каждый из которых имеет асимптотику O(N) 1 цикл - ищите все переходы в ассоциативный массив <куда, откуда> 2 цикл - на старте помещаете в стек\очередь все результатные состояния и с помощью ассоциативного массива из первого цикла "обжигаете" пока стек не исчезнет, на выходе должны получиться "обожжённые пути" 3 цикл : из "обожённых" путей со второго цикла, нужно составить ассоциативный массив <откуда, куда> (его можно заполнить и во втором цикле) 4 цикл фактически тот же алгоритм что и во 2-м, но уже с использованием мапы<откуда, куда> от точек старта PS: множества <куда, откуда> и <откуда, куда> естественно MultiMap (т.е. позволяют хранить несколько ключей) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 10:15 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), Для начала вы описываете здесь какой-то "отжигной" алоритм, но не алгоритм Бржозовского. Или я чего-то не вижу? Про Бржозовского цитата из текста, на который вы линкнули: С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. Уже это уже противоречит вашему утверждению про "всего 4 цикла". Ну и в заключениу к вашему "отжигному" алгоритму - достижимые конечные состояния нужно сначала найти. Это 5 цикл O(N) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 11:23 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), про Алгоритм Бржозовского - применим для НКА и ДКА. Из вики про КАПри работе на вход КА поступают последовательно входные воздействия, а на выходе КА формирует выходные сигналы. В моей задаче нету входного сигнала следователно это не КА, следовательно методы для ДКА и НКА не применимы. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 11:47 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan) _дух_, вот вы упёртый вы можете вести диалог на уровне, без оскорблений и перехода на личности? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 12:34 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
_дух_, есть такой анекдот авторЗадача I Пусть у нас есть пустой чайник, кран с водой, спички, газовая конфорка. Перед физиком и математиком ставят задачу вскипятить воду. Действуют они одинаково. 1. Наливают воду в чайник. 2. Зажигают конфорку. 3. Ставят чайник на огонь и ждут, пока закипит. Модифицируем Задачу I в Задачу II. У нас уже есть чайник, наполненный водой и зажженная конфорка. Цель та же: вскипятить воду. Физик ставит чайник на огонь и ждет, пока вода закипит. Математик выключает огонь, выливает воду из чайника и говорит: теперь задача сводится к предыдущей. (В некоторых интерпретациях математик после этого ждет, пока придет физик и вскипятит воду))) Доказывается применимость очень просто, вот давайте сделаем как математики у вас есть набор путей <откуда, куда> а давай туда условие перехода добавим инкрементально (1, 2, 3 и т.д), т.е. на каждый переход у нас получится единственное неповторимое условие и что мы увидим? КА причём, ДКА, так как условия переходов у нас уникальные а дальше что делать? - мы знаем ... теперь по асимптотике, говорится, что алгоритм может быть экспоненциальным, но в самом алгоритме мы видим только циклы по количеству элементов O(N). Экспоненциальность получается в subset construction, при преобразовании из НКА в ДКА. Но у нас уже ДКА, следовательно количество элементов может только уменьшаться!!! следовательно алгоритм O(N) для нашего случая Всё просто? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 13:20 |
|
Задача оптимизации
|
|||
---|---|---|---|
#18+
kealon(Ruslan), А есть ещё поговорка - если у бабушки есть член то он уже дедушка. Да, как вы написали сделать можно, но это как бы сказать -странно- привести задачу к общему случаю для того что бы реализовать решение для частного случая. И третий пункт задачи минимизации ДКА нам не нужен. Ну да бог с ним, а вот алгоритм который вы описали - частный случай - мне подходит / спасибо. Буду думать о компактном представлении реверснутого графа. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2021, 19:26 |
|
|
start [/forum/topic.php?fid=16&msg=40105271&tid=1339622]: |
0ms |
get settings: |
10ms |
get forum list: |
11ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
151ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
48ms |
get tp. blocked users: |
1ms |
others: | 265ms |
total: | 504ms |
0 / 0 |