На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> задача спелеолога
    задача не совсем умозрительная и не совсем компьютерная.

    на днях мы ходили в пещеру. пещера "дохлобарсучья", что в тверской области. она представляет собой заброшенную каменоломню, где круглый год температура +4 градуса. сия пещера состоит из более чем 40 км ходов, причём основную часть составляют так называемые колонники, тоесь когда есь много колонн и из одной точки в другую можно попасть несколькими разными путями. кроме того, на её стенах довольно мало надписей, так что ориентироваться относительно сложно. тот, кто был в пещерах, знает, что помимо высоких ходов там есь ещё и шкурники, по которым надо передвигаться ползком и так просто каждый шкурник не облазишь, хотя бывает, что в какую-то часть системы ведёт единственный шкурник. все вышеперечисленные факторы свидетельствуют, что картирование такой пещеры - чрезвычайно трудоёмкий процесс. а картировать надо, ибо доселе мы не нашли ни одной нормальной карты. в инете валяется геологическая карта http://bp-2001.narod.ru/barsuki.JPG , однако она совершенно отвратительного качества и по ней невозможно ориентироваться. в один из прошлых разов мы сами нарисовали карту, она получилась чуть лучше геологической, но, как показала практика, она далека от действительности.

    собственно задача заключается в том, чтобы придумать метод _быстрого_ картирования пещеры.я придумал vot что: когда встретишь какуюлибо надпись, записывать в протокол ету надпись, время по москве, показания компаса, направления откуда пришёл и куда ушёл. а потом прийти домой, вложить всё ето в компьютер, написать программу для обработки таких данных и получить на выходе некоторый граф. вопрос в том, каким образом ето всё обрабатывать, ведь надо учесть, что:
    1. человеку свойственно ошибаться.
    2. к сожалению, одинаковые надписи встречаются по нескольку раз.
    3. ходы не такие прямые, как хотелось бы, а потому если ты пошёл в какомто направлении, ето ещё не значит, что следующая точка будет лежать именно в етом направлении.
    4. как я уже говорил, из одной точки в другую можно пройти разными путями.
    5. время вовсе не пропорционально расстоянию в силу наличия шкурников и остановок на пути, более того, в один конец можно проследовать за другое время, нежели в обратном направлении. но измерять расстояния - тоже не выход, ибо так время картирования несказанно возрастёт, да и измерение расстояний в пещере - не такой уж и приятный процесс.
    6. в некоторых местах компас глючит.

    также будет неплохо, если ктолибо придумает альтернативный метод быстрого картирования.

    зы. я там ищо ссылку на pascal.sources.ru оставил smile.gif
      Бери с собой в пещеру мобилу с GPS навигатором. Он сам тебе покажет карту, если пробьётся сквозь камни. laugh.gif
      У меня приятель по Моське с таким лазит - горя не знает! biggrin.gif
        там не мобила не GPS не не ловится %))
          ну если так рассуждать, то можно просто скомпасом ходить, всё равно обратную дорогу найдёшь. а меня прикалывает именно картирование. а ывшеперечисленные девайсы действительно под землёй не работают
            Время можно не записывать потому как все равно оно ничего не показывает, а вот показания компаса на каждом повороте записать было бы неплохо. По этим данным можно(вроде blink.gif ) построить граф. Длинна ходов не так важна. Надо будет попробовать smile.gif
              что можно ето я и так знаю. вопрос как? а время я думаю всётаки нужно, ибо оно хотя и неточно, но всётаки показывает длину, а ищо оно показывает вероятность изменения направления во время прожода между двумя точками. потипу чем больше время, тем больше разброс угла, под которым две точки могут находиться к друг другу.

              собственно граф наверное должен рисоваться так: составляем легендарную систему точечных масс на пружинках плюс чтобы были силы, зависящие от углов между точками. вопрос в том, как зависят жёсткости связей и углов от временного расстояния между точками и разности в углах в начальной и конечной точках. а также хорошо бы построить зависимость пространственного расстояния от временного, можно поспорить, что она будет нелинейной. ето можно сделать на основании экспериментальных данных, но эксперимент такого рода должен быть предельно чистым: ведь надо, чтобы подопытный (он же, надо полагать, и экспериментатор) не имел счастья доселе ходить по данным ходам, ибо в таком случае он пойдёт по оптимальному (не по случайному) маршруту и вся статистика нарушится. в свете етого надо учесть, что если человек идёт по ходу второй раз, он уже обладает некоторыми знаниями о нём, и опять же его выбор направления будет другим, нежели в первый раз. кстати на основании такой статистики можно будет определить и зависимость жёсткости от расстояния.

              но собирание такой статистики - ето довольно долгий процесс, связанный с измерением расстояний, что искажает статистику времени (или надо измерять расстояния постфактум, что сопряжено с поиском точного пути, по которому прошлись в первый раз). вопрос: можно ли сделать скольколибо обоснованные предположения о зависимости расстояния/жёсткости от времени только на основании теоретических рассуждений?? например в свете теории случайных блужданий, которой столь виртуозно владеет esperanto. лично я с ней не знаком, но судя по всему придётся познакомиться.
                Не думаю что время показывает здесь хоть какую-то вероятность dry.gif
                Вобще на данный момент по твоей теории кроме графа с неопределенной длинной ребер мы ничего построить не сможем, но сам граф нам уже многое дает - зная структуру ходов в них достаточно просто ориентироваться даже не зная их длину.
                  почему же с неопределённой?? я ж ведь только что написал как её определять
                  а весь остальной трактат посвящён уточнению оценки расстояния
                    Именно неопределенной. Потому что твое определение нельзя считать верным smile.gif
                    Например у тебя все ребро может быть штреком по которому бегать можно, а может быть шкурой или быть некой их помесью smile.gif

                    Предлагаю при существенном изменении скорости проходимости данного участка опять же смотреть время и азимут. И еще указывать некий "коэф. проходимости". Только его надо записывать когда пройдешь этот отрезок.

                    Но все это все равно очень не точно показывает длину, т.к. привязкак ко времени дает очень много неточностей sad.gif
                    Человек может находиться в разной физ. форме, может быть разная степень усталости... В конце концов даже настроение влияет на то с какой ты скоростью передвигаешься... Плюс эта ошибка будет накапливаться...

                    Мое резюме:
                    Все вроде хорошо, кроме расчета длины от времени. Давай попробуем реализовать такую систему, но без определения длины. Длину потом можно добавить...
                      Цитата
                      madm, 4.12.03, 17:39
                      Потому что твое определение нельзя считать верным

                      да, оно приблизительное, но всёже количественное!! собственно когда мы первый раз картировали, у нас никаких рулеток не было, не говоря уже об угломерных инструментах. с ними было бы точнее, но ещё медленнее.
                      Цитата
                      madm, 4.12.03, 17:39
                      Например у тебя все ребро может быть штреком по которому бегать можно, а может быть шкурой или быть некой их помесью

                      правильно. но уменя такая идея: если ребро обладает большим временем, то его жёсткость должна быть меньше, т е его длина более неопределена, чем у ребра с маленьким временем. тем самым оно не будет упираться при расчёте, если окажется всего лишь короткой, но труднопроходимой шкурой. вопрос насколько меньше?. коеффициент проходимости - тоже не очень хорошо, ибо его придётся количественно оценивать, лучше просто записывать, есть ли на пути шкуры.

                      и вобще, время при брождении в пещере играет куда большую роль, нежели расстояние smile.gif
                        Цитата
                        время при брождении в пещере играет куда большую роль, нежели расстояние

                        Согласен. Но не для карты...


                        Давай уже к практике потихоньку переходить. А про время/расстояние можно и потом поспорить.
                        На чем писать будем?
                          я предлагаю на паскале
                          вобщето я ето в одну харю могу написать, там ничего сложного нет.
                          хотя.....
                          если я ето напишу, оно будет представлять собой эдакую утилиту: даёшь ей на входе текстовые файлы: один с протоколом похода, другой с параметрами, а на выходе будет третий текстовый файл - с графом. ибо пишу я под дос smile.gif . конечно не обойтись без визуализации в процессе работы, ето я тоже напишу.

                          соответственно надо ещё написать сохранение в бмп файл. не буду возражать против windows - интерфейса.

                          у практики есть ещё другая сторона - надо сходить в пещеру и записать собственно материал для обработки. лично я пойду в следующий раз не раньше февраля. сессия, знаете ли.... ph34r.gif
                            Писать под дос не имеет никакого смысла.
                            Против паскаля не возражаю.
                            Вобще подробности написания можно обсудить здесь:
                            http://beguin.lipfy.ru/!forum/

                            Пиши там куда-нить.
                            Не боись не сотрут - это почти мой форум smile.gif
                            В систему я наверное в сб пойду - соберу материал smile.gif
                            А сессия - это фигня tongue.gif
                              Цитата
                              madm, 4.12.03, 19:52
                              Писать под дос не имеет никакого смысла

                              почему???? всёравно один хрен на выходе, а под виндовс я не умею
                              Цитата
                              madm, 4.12.03, 19:52
                              Вобще подробности написания можно обсудить здесь:
                              http://beguin.lipfy.ru/!forum/

                              я бы предпочёл всёже обсуждать сдесь, а не плодить много топиков по одному вопросу. я и так уже на caves.ru ето же запостил, слава богу там ничего существенного не предложили. да и обсуждать касаемо собственно программирования особо нечего. я ето за ~1 день напишу, если соберусь smile.gif
                              Цитата
                              madm, 4.12.03, 19:52
                              В систему я наверное в сб пойду - соберу материал

                              в какую именно??
                              Цитата
                              madm, 4.12.03, 19:52
                              А сессия - это фигня

                              ну не скажи! я весь семестр ничего не ботал smile.gif сегодня чудом зачёт получил
                                В виндах выглядит приличнее и на входе и на выходе, а вобще как знаешь smile.gif
                                В другой форум звал потому как сейчас мы уже слегка не алгоритмы обсуждаем cool.gif
                                А пойду я в Кисели видимо.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0565 ]   [ 15 queries used ]   [ Generated: 21.05.24, 06:58 GMT ]