Задачи на графы

GeorgeL

Кто какие реальные задачи на графы знает? Понимаю, что область довольно узко-специализированная, но тем не менее. Интересуют задачи , где используются графы с большИм количеством вершин/дуг. Под реальными имеются ввиду такие задачи, где используются графы являются моделью реальных объектов (дороги города, линии водопровода и т.п.)

AlexInes

задача построения оптимального пути по:
карте дорожных развязок (yandex-пробки)
карте метрополитена (мобильные приложения Metro)

используются графы и веса (статические и динамические)

Andrey48

Задача поиска наиболее подходящего адреса.
Есть какой-то адрес(часть адреса) ищем по справочнику наиболее подходящий.

Vlad128

ну вон в анализе электрических сетей и отказоустойчивости некоторые ищут Betweenness Centrality, такая графовая задача.

GeorgeL

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

Vlad128

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

GeorgeL

хотелось бы чего то более реального)
не алгоритмы и статьи, а алгоритмы и исходники с форматами файлов и с самими файлами и как и что там делается) как то так)

Vlad128

зачем, если не секрет?

GeorgeL

посмотреть для чего на самом деле нужны графовые модели и как решаются какие нить реальные задачи, какую это приносит пользу

Kraft1

Что такое "реальный объект"? Являются ли пользователи социальной сети "реальными объектами"?
Или же для реальности объект должен быть осязаемым, а графы должны быть по крайней мере представлены в некоем формате BullshitML?

GeorgeL

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

Kraft1

Ну как раз такие задачи и решаются во всяких гуглах-фейсбуках, причем большинство алгоритмов в интернете найти достаточно легко.

Sander

хотелось бы чего то более реального)
не алгоритмы и статьи, а алгоритмы и исходники с форматами файлов и с самими файлами и как и что там делается) как то так)
ты хочешь странного
возьми любой opensource проект по своему вкусу и посмотри, как он устроен, например,
что-нибудь по кластеризации.
http://lmgtfy.com/?q=open+source+graph+clustering.
но и любая другая область, где люди стараются превзойти других - наукоемкая.
если интересен dot - возьми graphviz - тоже opensource.
у них есть раздел со статьями http://graphviz.org/Theory.php
ps
про большие задачи нет никакого смысла смотреть в сторону форматов, можно посмотреть на что-нибудь вроде http://lmgtfy.com/?q=mapreduce+graph+algorithms
или просто на статьи, которые пишут в гугле, яху, бинге про графы.
код скорее всего можно посмотреть по ключевым словам mapreduce tutorial

Damrad

перебор каких-нибудь состояний. То есть поиск пути по состояниям. Вершина = состояние. Ребра - возможные переходы.
Используется во всяких играх (текущая игровая ситуация =состояние)

ouvaroff

Кто какие реальные задачи на графы знает? Понимаю, что область довольно узко-специализированная, но тем не менее. Интересуют задачи , где используются графы с большИм количеством вершин/дуг. Под реальными имеются ввиду такие задачи, где используются графы являются моделью реальных объектов (дороги города, линии водопровода и т.п.)
интернеты же
один большой граф

Samsonnn

Социальные сети: поиск возможных друзей, моделирование путей информации

Hisstar

класс логистических задач, например, развозка хлеба по городу

geki-li

del

GeorgeL

меня не совсем правильно поняли.. меня не интересуют постановки задач - я таких могу сам найти великое множество)
интересно конкретные вещи , по типу "в городе X учёные решили оптимизировать перевозку продуктов Z, они составили граф , получилось N вершин, граф хранили в формате Y , для решения задачи воспользовалисть софтом B.."
за ссылки спасибо, посмотрю)

pilaf4

Все поиски пути во всяких гуглокартах имеют примерно такую постановку. Дорожная сетка хранится в виде графа — а как ещё ее хранить? Статью про микрософтовский алгоритм писал Andrew V. Goldberg.

GeorgeL

что значит как еще ее хранить?
я глянул, есть много форматов для хранения графов, например в вики перечислены
ки описания графов
DOT (язык)
GraphML
Trivial Graph Format
GML
GXL
XGMML
DGML

antcatt77

это скорее форматы передачи графов между приложениями, чем внутренние форматы хранения.

pilaf4

Это форматы передачи, все что оканчивается на ML — скорее всего, xml-based. В памяти граф может быть представлен как матрица или списки смежности.
Я имел ввиду, что граф — естественная абстракция для таких вещей, трудно представить, что дорожную сетку как математический объект можно представить (с дальнейшей целью поиска пути) как-то по-другому, не графом.

antcatt77

Дорожная сетка хранится в виде графа — а как ещё ее хранить?
с точки зрения алгоритмов, есть много вариантов, например, иерархический граф. такое представление часто используется при поиске пути

Banzay1

Единая система загоснабжения

GeorgeL

Единая система загоснабжения
Ссылку на описание задачи и формат файлов можно? желательно и на само ПО..

Banzay1

к сожалению, не могу(
Оставить комментарий
Имя или ник:
Комментарий: