1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

работа с графами

Тема в разделе "WASM.A&O", создана пользователем sambd, 6 май 2008.

  1. sambd

    sambd New Member

    Публикаций:
    0
    Регистрация:
    14 дек 2007
    Сообщения:
    60
    сам я дискретку не учил по этому ХЗ что это за теорема, по идеии разчет должен быть какойто математический на матрици смежности

    может кто знает или сталкивался с подобными вопросами?
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    5.265
    оффтоп, конечно, но не могу удержаться: зачем обходить туннели, если можно блокировать все возможные выходы и подождать, а для пущей эффективности и забавы - закидать шумовыми и дымовыми шашками:-))
     
  3. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    sambd
    минимальное количество полицейских S, гарантирующих поимку беглеца

    Это довольно известная задача с большим количеством литературы по ней. К сожалению она относится к NP-hard. Начинать можно с Википедии (http://en.wikipedia.org/wiki/Pursuit-evasion)

    Кстати если не ошибаюсь, то в первой версии поста у тебя была немного другая формулировка - "перекрыть путь", а не поймать. В этом случае речь идет о вычисление "vertex-connectivity" графа.
     
  4. sambd

    sambd New Member

    Публикаций:
    0
    Регистрация:
    14 дек 2007
    Сообщения:
    60
    ну если перекрыть то можно и поймать, хотя и есть разница но нужно найти минимум ...

    ок спасибо,

    а вот на русском есть какая нить литература? так как я чтото не нашел ничего полезно ... хотя может и плохо искал
     
  5. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    sambd
    ну если перекрыть то можно и поймать

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

    а вот на русском есть какая нить литература?

    Чего не знаю, того не знаю..
     
  6. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    sambd
    Fomin F.V. Petrov N.N. , Pursuit-evasion and search problems on graphs // Congr. Numer. 1996. Vol. 122. P. 47-58.
    Fomin F.V., Golovach P.A., Petrov N.N., Search problems on 1-skeletons of regular polyhedrons //Games Theory and Appl. Vol. III. N.Y.: Nova Science Publisher, 1997. P. 27-37.

    http://tex.imm.uran.ru/tom6/pet/
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    5.265
    Stiver
    не самое лучшее сравнение.
    --------------------------------
    а, вообще, эта задача интересная: она относится к особенностям боевых действий в замкнутых помещениях. её решение очень сильно зависит от того, на кого охота идёт. если на каждом перекрёстке ставить датчики движения иль более активные системы, то проход беглеца станет невозможным (если он не вооружён). при наличие оружия попытка поймать живым может привести к потерям среди охотников.
     
  8. sambd

    sambd New Member

    Публикаций:
    0
    Регистрация:
    14 дек 2007
    Сообщения:
    60
    (закрыто) вопрос решен!