|
Задачка про остров
|
|||
---|---|---|---|
#18+
Каюсь. Каждый раз, когда мне эта задача встречается - у заказчика руки опускаются , он даже не может приоритеты важности расставить (привет менеджерам, это технолог делает, когда его в процесс включают, а не пилят ком. пердложения, торговые сделки). Самое примитивное. Оператор тыкает - пустить закачку из Р1 в Р5. Р1-Н2-Р5 (завдвижки я не рисовал) перекроет работу всего остального, а вот если пустить через насос Н1, то Н2 еще можно испльзовать для Р3 Н2 Р6. Р1--|___Н1--|___Р4 Р2--|___Н2--|___Р5 Р3--| |___Р6 Это комплексаная проблема, которую долго можно жевать. Пока никто даже системного подхода не описал народе: 1 Опишите в схеме потсоянные маршруты, котрые будут использоваться всегда. 2 Максимальную длину и так далее и тому подобное. Все сейчас сводится к проверке линий (аля не потекет ли бензин в ДТ, потому что задвижку забыли закрыть или не тот насос запустили). ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 20:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
В тему графов. Предложу 2 инварианта. Для данной сущности. Код: java 1. 2. 3. 4. 5. 6. 7.
1) Каков-бы не был уровень воды - уровень земли меньше либо равен уровню воды в этой ячейке. Код: sql 1.
2) Все соседние ячейки с одинаковым уровнем земли (и соседние по отношению к соседним) всегда имеют одинаковый уровень воды. (он может быть неодинаковым в вашем алгоритме на какой-то итерации. Но после достижения стационарного состояния алгоритма в целом - это будет так) Отсюда вытекает интересное преобразование. Группу связных вершин графа имеющих одинаковый параметр height мы можем заменить на 1 единственную вершину топологически связную с соседями данной группы. С точки зрения картинки - не меняется ничего. Но алгоритм упрощается. Мы выбрасываем целое "плато" столбиков с одинаковой высотой и заменяем его на 1 виртуальный столбик который имеет neightbours() существенно больше чем 4 или 6. Но для нас это неважно. Тоесть для ландшафтов с большим количеством плато объем вычислений прилиовов и отливов может быть существенно сокращен за счет такого топологического преобразования. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 20:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
На сколько моих способностей хватило изобразил пример для тестирования ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 22:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Четырехсвязный узел для графа Код: java 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 22:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник ... Р1--|___Н1--|___Р4 Р2--|___Н2--|___Р5 Р3--| |___Р6 Это комплексаная проблема, которую долго можно жевать. ... Что в задаче навроде переменных (флажки ...), а что навроде относительно статических "справочников" (содержимое Р(i) )?.............. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 00:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 АСУ ТПшник ... Р1--|___Н1--|___Р4 Р2--|___Н2--|___Р5 Р3--| |___Р6 Это комплексаная проблема, которую долго можно жевать. ... Что в задаче навроде переменных (флажки ...), а что навроде относительно статических "справочников" (содержимое Р(i) )?.............. Что-то вроде Форда Фалкерсона по расчету потока. Если вентили - неуправляемые. Если управляемые - то неясна цель управления? Максимальная загрузка? Загрузка чего? Насосов? Или всей сети? Тут нельзя так вот небрежно бросаться заданиями. Это-ж неуважение к читающему. Тут люди рады решать головоломки но зачем-же их заставлять додумывать ? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 00:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Задачи в головах. Забейте. Не тратьте время. Было бы все прописано , я бы уже озолотился. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 12:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как будет угодно. Ты если захочешь ее поставить - лучше отдельным топиком. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 12:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Четырехсвязный узел для графа Код: java 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.
Тут лучше всё таки не класс а интерфейс. Чтобы иметь разные реализации. Ябы предложил так. Код: java 1. 2. 3.
Что это дает. Это даёт обобщенный алгоритм. И возможность оптимизаций по памяти. +Шаблон Flyweight. Как оптимизация системы хранения. Нам не обязательно хранить Node для каждого пиксела картинки. Достаточно к картинке предоставлять INode интерфейс. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 16:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
задаем V = 0; 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. 2) ищем любую вершину которая не примыкает к морю и имеет только входящие ребра, причем хотя бы одно 3) если на 2 вершина не найдена, то результат в V 4) к найденной вершине добавляем к высоте 1 и увеличиваем V на 1 5) повторяем все начиная с шага 1 Можно, конечно, еще оптимизировать, если вместе с найденной вершиной захватывать все которые достижимы из неё (не по нашему графу, а просто по граням шестиугольников) и у которых текущая высота такая же как у найденной и увеличивать не на 1, а на большее значение анализируя прилегающие к ним. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 21:52 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
fkthat 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. 2) ищем любую вершину которая не примыкает к морю и имеет только входящие ребра, причем хотя бы одно ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 22:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 fkthat 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. 2) ищем любую вершину которая не примыкает к морю и имеет только входящие ребра, причем хотя бы одно Да, точно, не учел. Ну что же буду думать дальше. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 23:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
fkthat задаем V = 0; 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. Орграф нас ограничивает IMHO. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 12:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
fkthat Можно, конечно, еще оптимизировать, если вместе с найденной вершиной захватывать все которые достижимы из неё (не по нашему графу, а просто по граням шестиугольников) и у которых текущая высота такая же как у найденной и увеличивать не на 1, а на большее значение анализируя прилегающие к ним. Смотрите. По поводу любых идей оптимизирующих или трансформирующих сам граф. Вы должны доказать что ваше преобразование по complexity будет дешевле чем "лобовое" решение задачи сходу. Сюда-же до кучи моё предложение по свёртке одинаковых высот в кучу. Тоесть 2 варианта. 1) Решение задачи 1 раз в лоб любым алгоритмом. 2) Оптимизация ландшафта до некого упрощенного графа. И многокраное решение задачи прилива-отлива. Только я не уверен что автор топика такое многократное решение прилива заказывал. Понимаете да? Это как построение индекса по таблице в БД. Одноразово - неэффективно. А эффективно при периодических использованиях. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 12:47 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Итак, еще один вариант решения. 1) Находим максимальную высоту шестиугольников 2) Каждому шестиугольнику присваиваем число (назовем его "теущей высотой", в отличии от просто "высоты" заданной в условиях задачи) равное максимальной высоте из п.1 3) Начало цикла 4) Ищем любой шестиугольник который имеет "текущую высоту" больше своей "высоты" и либо: а) Граничит с морем б) Имеет хоть один соседний шестиугольник с меньшей "текущей высотой" 5) Если на п.4. мы такого шестиугольник не нашли, то выходим из цикла 6) Иначе, Если на п.4. найден шестиугольник который граничит с морем, то устанавливаем его "текущую высотуо" равную его "высоте" 7) Иначе устанавливаем значение его "текущей высоты" в значение максимальное из его "высоты" и минимальной "текущей высоты" всех его соседей. 8) Возвращаемся в начало цикла 9) Здесь мы вышли из цикла 10) Суммируем по всем шестиугольникам разницы между их "текущей высотой" и "высотой" - это и будет результат (объем луж). ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 13:41 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
вроде верно. Кстати, на определенных этапах корректировка "текущей высоты" будет распространяться от краёв, как тут 22077648 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 14:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
похоже на вариант с "текущей высотой" - сортируем ячейки по высоте, затем последовательно наполняем каждую дельту высот: Код: pascal 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. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129.
... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 16:37 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хорошая портянка, мне вот трудно читать, ибо не приучен. А суть в чем? Есть идея - а можно ли перепрыгнуть с точек и их уровней, на наклоны соединений между клетками? Ну т.е. простейший случай - 8657. Два выхода к морю в двухмерном пространстве. 8->6 наклон отрицательный. 6->5 отрицательный.7->5 отрицательный. Наклон может быть суммирующимся. Подозреваю что можно , через суммирование весов каждого наклона типа 8 против 5 - вода не вытечет, но не уверен в целессобразности. Т.е. идея какая - кратчайший путь от центра к низинам или от моря к самой высокой точке по А алгоритму с правилом каким-то, а потом веса наклонов считать. Был пьян, вспылил :D ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 18:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Для всех ячеек и их ближних соседей. Инвариант - вода течет вниз. Ивариант вода не ниже чем дно. Инвариант. Любая вода - не ниже чем океан. Всё остальное - только имплементация этих правил в виде кода + эвристики и предположения. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторИнвариант - вода течет вниз. Ивариант вода не ниже чем дно. Инвариант. Любая вода - не ниже чем океан. ТЗ какбы само собой (не очень понял при чем тут инвариант). Но вот лужа никогда не нижу уровня моря - "искусственно" несколько, почему бы и нет? Разовью мысль. "Практическое" решение уже нашлось. В области теории всего обо всем,42, оно как бы отсекает абсолютно нейтральный подход - мы не знаем чего будем анализировать. Т.е. получается уже искусственные ограничения для искусственной же задачи. Зачем? Очень уверен, что лужа глубже уровня моря может быть без значительного усложнения. Задача так-то вырождается вообще в простой вопрос. Определить области, откуда при неизменности силы притяжения и барьеров (чтобы вода не текла), остров, вынутый за ручку вверх сможет сохранить часть воды , как-то алгоритмически проанализировать и решить как можно более простым способом. наиболее понятным способом. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:23 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Хорошая портянка, мне вот трудно читать, ибо не приучен. А суть в чем? Извини, не смог уложиться в 5 строк. Суть, как сказано в преамбуле перед портянкой, в том, что мы будем вместо одной сложной задачи последовательно решать более простые задачи, по одной для каждого изменения высоты ячейки. АСУ ТПшник Есть идея - а можно ли перепрыгнуть с точек и их уровней, на наклоны соединений между клетками? Ну т.е. простейший случай - 8657. Два выхода к морю в двухмерном пространстве. 8->6 наклон отрицательный. 6->5 отрицательный.7->5 отрицательный. Наклон может быть суммирующимся. Подозреваю что можно , через суммирование весов каждого наклона типа 8 против 5 - вода не вытечет, но не уверен в целессобразности. Т.е. идея какая - кратчайший путь от центра к низинам или от моря к самой высокой точке по А алгоритму с правилом каким-то, а потом веса наклонов считать. Был пьян, вспылил :D С нетерпением жду реализации в 5 строк этой замечательной идеи. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторС нетерпением жду реализации в 5 строк этой замечательной идеи. Вода должна оставаться в луже :D А серьезно - куча реализаций может быть. Но суть в том, что ваш код даже без комментариев. Чего он там и зачем делает, концептуально непонятно, реверс инжиниринг - ну извините, лень. Тут как-то на интуитивно понятном языке обходились пока не влез ОраклДевелопер, который приделал к переменным геттеры и сеттеры ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:32 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторчто мы будем вместо одной сложной задачи последовательно решать более простые задачи, Не уследил за изложением в сообщениях. По утру попробую. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник авторС нетерпением жду реализации в 5 строк этой замечательной идеи. Вода должна оставаться в луже :D А серьезно - куча реализаций может быть. Но суть в том, что ваш код даже без комментариев. Чего он там и зачем делает, концептуально непонятно, реверс инжиниринг - ну извините, лень... Их есть у меня: Код: pascal 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:58 |
|
|
start [/forum/topic.php?fid=16&msg=39925444&tid=1339799]: |
0ms |
get settings: |
10ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
143ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
63ms |
get tp. blocked users: |
2ms |
others: | 14ms |
total: | 268ms |
0 / 0 |