Uljahn: хд
SqueeCoder: Что надо почитать, чтобы научиться пользоваться графами на с#?
Uljahn: графы на С# для чайников?
Uljahn: выглядит так, будто графы ты уже знаешь, С# знаешь, но одно с другим не можешь совместить
qbit86: SqueeCoder 1. CLRS, 2. документацию к Boost.Graph
SqueeCoder: Ну примерно я знаю что такое графы, но не разбирался, и не знаю какие использовать. Там же есть различные варианты?
SqueeCoder: Спасибо, буду qbit86, полезу разбираться.
qbit86: SqueeCoder CLRS — это книжка Кормен-Лейзерсон-Ривест-Штайн.
metahom: на ulearn.me курс лекций по с#
metahom: там же и графы
735487: SqueeCoder: ulearn.me там есть
735487: metahom: не увидел что ты уже посоветовал
SqueeCoder: Всем спасибо большое, коммьюнити здесь отзывчивое :)
Uljahn: имхо лучше начать с теории графов, если сильно плаваешь, а потом уже реализации структур и алгоритмов на с# курить
735487: ну вот на ulearn.me там как раз основы и по алгоритмам и по языку
BorisZ: надо начинать с цели - зачем мне нужны графы?
wlesavo: а чтО, апрувалы сломались?
735487: я знаете зачем вникал в графы? потому что на топкодере постоянно были на них задачи )))) так я научился dfs ))))
BorisZ: если для науки там это одно дело, а для прикладный вещей надо несколько алгоритмов
Uljahn: да, wlesavo
wlesavo: я пропустил видимо обсуждение
Uljahn: в дискорде обсуждали
wlesavo: но выглядит забавно
SqueeCoder: Для поиска пути, как я понял. Для контестов.
SqueeCoder: Для науки пока не надо :)
Uljahn: ну тогда всю теорию графов не нужно, в самом деле, но хотя бы с терминологией ознакомиться
BorisZ: SqueeCoder тогда бфс, астар и дейкстра - все что нужно
Uljahn: матрица смежности)
735487: еще dfs надо знать
BorisZ: вот по мне дфс уже сомнительно )
735487: и наверное иногда знать еще что бывают такие слова как гамильтоновы циклы
Uljahn: про клики иногда полезно знать
735487: BorisZ: задачи разные бывают. иногда и дфс нужен
Uljahn: диаметр графа и т.д., зависит от задачи
735487: тут как раз где то есть пазл на диаметр графа
Uljahn: чем больше знаешь - тем шире выбор инструментов
735487: я точно знаю что я его решил неправильно но он текущие тесты все проходит
SqueeCoder: Да понятно, что штука жутко полезная. Мне главное, чтобы зацепиться было за что на практике. Дальше, обычно. легче.
BorisZ: amurushkin во первых дфс трудно воспринять интуитивно, во вторых я думаю что либо бфс либо астар сделают тоже самое в зависимости от задачи
BorisZ: не менее эффективно
wlesavo: вчера делал расстояния для gitc, написал из общих соображений поиск пути, тупо брутфорс на упорядоченных по расстоянию списках для ранних остановок
wlesavo: вот что бывает когда лень разбираться
BorisZ: но я не настаиваю, может и есть что-то заковыристое хз
Uljahn: SqueeCoder: начни с поиска расстояний и кратчайших путей в неориентированном графе, как в задаче wlesavo
735487: BorisZ: дфс и бфс для разных задач же. и мне наоборот было понятнее начиная с дфс. он самый простой имхо
wlesavo: я вообще вчера только открыл постмортемы и понял что расстояния в gitc не линейные
Uljahn: Дейкстра, Флойд-Уоршэл
wlesavo: сам бы не подумал об этом
Uljahn: в начале же дают все расстояния
Uljahn: плюс там один ход задержки в узле
Uljahn: но всё равно через узлы прыгать бывает быстрее
Uljahn: чем напрямки
wlesavo: так дают, но то что до точки можно дойти через две другие остановки быстрее чем напрямую для меня не очевидно было
Uljahn: я ещё на контесте это заметил, а Marchete сделал красивый реплей с примером
wlesavo: ну под нелинейными я подразумеваю что не выполнятся r(AC)<=r(AB)+r(BC)
SqueeCoder: Но реализацию писать самому, или библиотеки использовать?
wlesavo: лучше один раз хотябы самому написать
wlesavo: а дальше уже как хочешь
Uljahn: тебе вроде в самом начале какие-то шарповые библиотеки советовали
Uljahn: Boost.Graph
BorisZ: SqueeCoder короче надо начинать с бфс - он очень простой, применим для 90% задач где графы не взвешанные и не огромные
BorisZ: писать самому понятно дело
735487: можно на вики посмотреть псевдокод и по нему делать
BorisZ: с его помощью и пути ищутся и расстояния и connected components
SqueeCoder: Теперь всё понятно, буду курить бфс.
735487: вот connected components через dfs наверное быстрее будут
Uljahn: https://vscode.ru/prog-lessons/programma-dlya-postroeniya-grafov.html
735487: хотя может и нет
BorisZ: тут на кодингейм почти все либо гриды, либо гексы и в общем небольшие
BorisZ: amurushkin как я понимаю дфс только одну задачу сделает быстрее чем бфс - есть ли вообще хоть какой-то путь меджу вершинами
BorisZ: а вот кратчайший он или нет - это уже надо напягаться как-то чтоб определить и скорость уже не будет та же
BorisZ: блин дернул же меня черт зайти сюда - так хорошо работалось:grimacing:
BorisZ: amurushkin я отзываю все свои аргументы и признаю поражение в дискуссии )
735487: ахаха знакомо )) пошел и я поработаю
qbit86: Uljahn Boost.Graph — это плюсовая библиотека :) Шарповых нет, пока я не допилю :)
qbit86: BorisZ DFS — это примитивный блок для кучи других алгоритмов: топологическая сортировка, поиск компонент связности, etc. В каком-то смысле он более фундаментален, чем BFS.
Uljahn: вроде какая-то есть, правда старенькая
qbit86: Uljahn Нужна обобщённая библиотека, которая не накладывает ограничения на модель. Чтобы модель можно было взять из любой другой библиотеки, или неявный граф, или бесконечный, why not.
qbit86: Представьте, что в последнем контесте туман полный, не дана карта лабиринта, кроме ближайшей окрестности. И разведывать надо «пешком».
qbit86: DFS — это как раз буквально обход, он локальный. А BFS и прочие Дейкстры — это прыжки по фронтиру.
qbit86: Чтобы использовать BFS, пакману надо ножками возвращаться в следующую вершину из очереди, которую он хочет исследовать...
qbit86: ...А в DFS используются только соседи, вот они, только руку протяни.
qbit86: Если вы попадёте в реальный лабиринт без глобальной карты, то исследовать его придётся по DFS. Если по BFS, то устанешь туда-сюда возвращаться по пройденному пути.
Uljahn: стек vs очередь, итерации vs рекурсия?
qbit86: Но DFS слжный, да. Наивная реализация из учебников и даже CLRS предполагает рекурсивные вызовы. То есть ограниченный стек. А желательна ручная реализация стека, цикл без рекурсии.
Uljahn: угумс
Uljahn: кто-нибудь юзает CG Enhancer?
Hiker: поясните ньюбу что такое бфс что такое дфс
Hiker: а, сори. гуглится оказывается
Beard: алгоритмы обхода графа, в ширину и глубину
Uljahn: https://www.codingame.com/learn/BFS
https://www.codingame.com/learn/DFS
Uljahn: https://www.codingame.com/learn/flood-fill
Uljahn: хм, в псевдокоде DFS проверку на посещение именно в этом месте имеет смысл делать или лучше при добавлении в стек?
735487: в dfs проверка на посещение для того чтобы при поиске пути не посещать уже пройденный. а если ты до поиска хочешь исключить посещенные то до вызова и помечать
Uljahn: похоже, у меня bfs головного мозга, сложно переключаться на dfs)
Beard: реши пазлик про бендера, где он на этаже деньги собирает
Uljahn: решил же, но давным-давно
Uljahn: а там нужна проверка разве?
Uljahn: граф же ориентированный, т.е. возвращаться нельзя
Uljahn: amurushkin: теперь дошло, спасибо
Beard: там можно сохранять сумму для комнаты, и отсекать продолжение пути если текущая сумма меньше чем в варианте, который уже смотрел
Uljahn: так и сделано у меня, добавляются только более перспективные варианты, и обновляется максимально достигнутый для ноды
Uljahn: результат
Beard: ну так а чего говоришь что dfs сложный)
Uljahn: да я про проверку посещённости в неориентированном графе затупил чё-т
qbit86: DFS сложный. Если по харкору, то есть ещё с классификацией рёбер как в CLRS, без рекурсии, и к тому же Enumerable/anytime (с сохранением состояния и прерыванием/продолжением обхода), без аллокаций на enumerator'ы — прям непросто.
BorisZ: qbit86 я просто применительно к контестам рассуждаю: посчитать расстояние и найти кратчайший путь - это бфс, дфс не подойдет, а это нужно практически везде
BorisZ: компоненты связности - абсолютно все равно как граф обходить, все подойдет
BorisZ: насчет топологической сортировки - наверное, я задачу представляю, но решения не помню
BorisZ: может их несколько
BorisZ: про неинтуитивность дфс я не реализацию имел ввиду в основном, а то что хрен знает в каком порядке мы граф обходим
BorisZ: а бфс - все строго в порядке расстояний, любо дорого смотреть
BorisZ: если ищем и сравниваем пути как в пакмане, то понятно что сначало нужно короткие, а потом длинные искать
BorisZ: что толку построить путь через всю карту сначала, а то что близко и не рассмотришь
BorisZ: если бфс это скачки, то дфс это пьяное блужданее по графу )
BorisZ: *блуждание
BorisZ: а в чем сложность кстати с реализацией? меняем очередь на стек и погнали, так же набор посещенных храним
Uljahn: мне в бфс нравится, что можно радиус фронтира
Uljahn: контролировать
ilt: Uljahn ты где-то писал как быстро искать победные комбинации
ilt: как этот метод называется?
ilt: я сейчас это делаю в два приема для мини-доски и для мастер-доски
Uljahn: Look-up table
Uljahn: у тебя 9 бит на игрока, т.е. всего 512 комбинаций, используешь стейт игрока как индекс и смотришь в массиве результат
Uljahn: массив получается небольшим и сидит в кэше
Uljahn: в один приём и для мини и для большой не получится, наверное
Uljahn: зато на битовых операциях можно сэкономить
Uljahn: а вообще я дно в крестиках :relieved:
ilt: ты от меня всего на 70 мест отстаешь
ilt: я помню что ты что-то умное сказал, но я не помню что
Uljahn: про масочки?
ilt: LUT
wlesavo: для больших проблема в завершенных но не выйгранных досках
Uljahn: Look-up table
Uljahn: это и есть LUT
ilt: я уже понял
ilt: спасибо
Uljahn: wlesavo: поясни, в чём проблема?
ilt: сходу непонятно лучше иметь массив размера 512 или делать 8 сравнений с числами в одной функции
ilt: поиск по индексу быстрее будет?
Uljahn: когда непонятно, то надо замерять, да и когда понятно - тоже надо :)
wlesavo: Uljahn ну чтобы не просто победа/поражение было а возможные победы/поражения на следующем ходу тоже, ну не прямо проблема, но для моего эвристического бота это много ломало
Uljahn: поиск по индексу в массиве?))
ilt: да
Uljahn: это же доступ к ячейке, к началу массива прибавляется индекс*размер элемента
Uljahn: никакого поиска
wlesavo: это не совсем поиск, да
Uljahn: у массива свойство - элементы все одного типа и лежат в памяти линейно
ilt: элементов 512
ilt: у тебя есть индекс и нужно значение для этого индекса получить
Uljahn: ну, это же элементарная индексация обычная
Uljahn: как arr[i]
Uljahn: i - это 9битный стейт минидоски для одного игрока
ilt: я от чего-то похожего избавился
ilt: оно тормозило
ilt: попробую
Uljahn: массив крошечный, должен целиком помещаться в L2 кэш по идее
Uljahn: но лучше всего две реализации сделать и профилировать
ilt: вообще MCTS для UTTT самый маленький бот из всех
ilt: без кешей вообще строк 200
ilt: размашистым почерком
ilt: так что переписывай
ilt: много времени не должно занять :grinning:
Uljahn: просто написать не интересно, мне интереснее разные варианты реализаций сравнивать между собой, а т.к. варианты возможны в разных местах кода - происходит комбинаторный взрыв :smiley:
ilt: с управлением версиями это самое то
ilt: наклепал разных вариантов и давай их сравнивать
ilt: arr[i] добавляет 20% роллаутов
BorisZ: Uljahn 07:44PM
мне в бфс нравится, что можно радиус фронтира
контролировать
BorisZ: точно - еще одна капля на мельницу полезности бфс
Uljahn: в принципе, и в дфс можно длину путей обрезать на нужной длине, наверное
Uljahn: но как-то не очень удобно
BorisZ: я в подлодках кстати делал так - длинные пути не хватало времени обсчитать, просто добавлял в конце бфс на небольшую глубину
BorisZ: а не получится что не все клетки в заданном радиусе обойдешь?
BorisZ: я чет не могу сообразить
BorisZ: про дфс трудно думать - во )
BorisZ: про бфс легко )
BorisZ: в подлобках вместо того чтобы грубо говоря путь длинной 20 считать, я считал длинной 8 а потом в конце бфс с отсечкой в 12 клеток
BorisZ: цифры не помню точно
BorisZ: для пути нормальная оценка - тяжелая какая-то, в конце довесок - чтоб в тупики не заползал на ровном месте
BorisZ: надо было число своих позиций с точки зрения врага считать и еще чего-то
BorisZ: позапрошлый контест уже затянулся туманом, как детские воспонминания
Uljahn: хм, 78 очков до следующего уровня, надо чё-нить зарешать, пока spaceХ не полетел
BorisZ: два часа еще
BorisZ: завтра посмотрю в записи, очень мне понравилось как 2 ускорителя садятся одновременно
BorisZ: но тут вроде один только основной судя по фотке
BorisZ: жалко блин
BorisZ: поменял подложку в профиле, поддержать пацанов
BorisZ: как тебе такое, Илон Маск?
Uljahn: хд
dbf: в java, кстати, с arr[i] проблема, что проверяется выход за края еще
dbf: и вроде далеко не всегда эта проверка может быть вырезана при оптимизации jitом
tutubalin: кстати, по поводу космоса.
обещают в этом году Kerbal Space Program 2.
