Ответы пользователя по тегу Графы
  • Каков механизм распознавания объектов через графы?

    @dmshar
    Во-первых, наверное все таки не "распознавание объектов графам", а скорее всего "распознавание объектов, которые представлены графами".
    Во-вторых, на "уровне языков программирования" - такое, на сколько я знаю, не реализовано нигде. В любом случае, вам надо средствами выбранного языка смоделировать объект типа "граф". Сегодня это позволяют сделать любой язык программирования (ну кроме совсем специализированных). А дальше делайте с этим представлением что хотите - хоть кратчайший путь ищите, хоть поиск в ширину-глубину организовывайте, хоть сравнивайте два графа между собой, хоть задачу коммивояжера решайте, хоть распознавайте в графах некоторые паттерны, хоть описывайте свои объекты (например - лица) в виде графовой модели и ищите "подобные". Для всех таких задач есть соответствующие алгоритмы, а часто - и не один, которые изучаются в таком разделе математики, который называется "теория графов". Эти алгоритмы реализуются либо в ручную, самим программистом, но в некоторых языках программирования есть библиотеки, которые решают некоторые задачи из перечисленных. Например для Python есть библиотека NetworkX, которая сильно упрощает работу с сетевыми (графовыми) структурами.
    Если вас интересует вопрос на ответ "как" выполняется распознавание с помощью графов - то тут имеется достаточно много источников, правда большинство из них не для "легкого внеклассового чтения" и требуют достаточно серьезного углубления в математику. Ну вот например,:
    https://www.litres.ru/a-a-dunaev/ispolzovanie-teor...
    https://cyberleninka.ru/article/n/primenenie-teori...
    https://scask.ru/p_book_gpr.php?id=95
    https://cyberleninka.ru/article/n/metod-gibkogo-sr...
    Последний вопрос про "предпочтения языка программирования с точки зрения мощности сервера для данной задачи "- вообще непонятен. Выбор сервера будет сильно отличаться не столько языком реализации вашей системы, сколько самой задачей - например, сегодня распознавание лица при фотографии есть в любом фотоаппарате или смартфоне, а вот если вам надо выявлять преступника на видеопотоке из метро - там совсем другие сервера придется задействовать. Хотя алгоритмы лежащие в основе и язык программирования вполне может быть одним и тем-же.
    Ответ написан
    3 комментария
  • Как можно найти все пути между вершинами графа networkx?

    @dmshar
    Если нет - легко написать самому. Рекурсия и элементарная теория графов.
    Но надо иметь ввиду, что эта задача имеет экспоненциальную сложность. Поэтому даже если напишете - не факт, что при более-менее серьезном графе решите вашу задачу за вразумительное время. (Ну, если ваш граф не на пять-десять вершин). А если граф еще и не ориентированный - то решений вообще по определению бесконечное число.
    Поэтому для практических нужд обычно формулируют ограничения, которые позволяют сократить круг рассматриваемых вариантов и решать реальные практические задачи.
    Вот тут - элементарное объяснение:
    kuimova.ucoz.ru/modul_10-grafy-bazovye_algoritmy.pdf
    Вот тут - некий драфт скрипта
    https://ru.stackoverflow.com/questions/1046271/алг...
    Вот тут - если начнете писать - некоторые полезные обсуждения и идеи
    https://coderoad.ru/2723438/Алгоритм-Графа-Для-Пои...
    www.fvn2009.narod.ru/Olympiads/Rules_Olympiads/Rul...
    www.delphikingdom.com/asp/answer.asp?IDAnswer=56734
    Ответ написан
    Комментировать
  • Как найти путь в ориентированном графе?

    @dmshar
    1. Ответ на ваш вопрос - "Можно".
    2. Предвидя ваш следующий вопрос - " а как это можно сделать" - отвечу сразу, Не знаю, какой путь вы там решили искать (вы даже не удосужились нам об этом сообщить - а зачем, все же должны бегом побежать догадываться, какую там задачу вам задали на дом и вы не осилили, - ну да ладно) - но начните поиск путей в ориентированном графе с алгоритма Дейсктры. 99% вопросов отпадут (если осилите, конечно). За остальными непонятками - возвращайтесь сюда, попробуем помочь.
    Ответ написан
    Комментировать
  • Книги про графы в не евклидовых геометриях?

    @dmshar
    На сколько мне известно, изучение теории графа проводятся в рамках алгебраических (включая линейную алгебру, спектральную теорию и теорию групп ) , комбинаторных, алгоритмических и геометрических подходов. Вот только геометрический подход никак не использует основные аксиомы Эвклида. Одно из определений гласит: геометрический граф есть геометрическая конфигурация или структура в пространстве отношений инцидентности, состоящая из множества точек, взаимосвязанных множеством непрерывных, самонепересекающихся кривых.
    Места для параллелизма и анализа его присутствия/отсутствия тут как мне кажется просто нет.

    А позвольте поинтересоваться, откуда взялся ваш вопрос и какую задачу вы пытаетесь решить?
    Ответ написан
    2 комментария
  • Как вывести на экран список ребер, считанных из файла?

    @dmshar
    То-ли я чего-то недопонимаю, то-ли вопрос - почти детский.
    В вашей постановке любой элемент матрицы, отличный от нуля соответствует ребру, индексы этого элемента - узлы связанные данным ребром, а значение - вес. Все!
    Вопрос-то в чем? Как перебрать все элементы матрицы?
    Ответ написан