Cool Folders ® :: Форум Игротека :: Кто может подказать алгоритм

Кто может подказать алгоритм

Дата : 20-08-06, Вск, 08:52:14

Привет всем умным. Есть вопрос. Кто сможет выработать алгоритм для раскраски следуюшего графа. (см. приложенный файл). Для начала надо представить что этот граф имеет ребра как показано, но они не окрашены... Я долго ломаю голову над этим вопросом. если кто поможет будет супер.
Спасибо заранее.

Кто может подказать алгоритм

№ 2

Танкист

Дата : 20-08-06, Вск, 13:51:02

Только не подумайте что я умный. Какой раскраски?

Не соблазняйтесь, если, зачешутся вдруг руки,
Одеть чего не надо куда-то не туда.
[ 20-08-06, Вск, 20:51:22 Отредактировано: Танкист ]
[ 20-08-06, Вск, 20:53:44 Отредактировано: Танкист ]

Кто может подказать алгоритм

№ 3

Тигра

Дата : 20-08-06, Вск, 14:01:39

BFS

Кто может подказать алгоритм

№ 4

Briska

Дата : 20-08-06, Вск, 15:38:45

Автор: Танкист
Дата : 20-08-06, Вск, 20:51:02

Только не подумайте что я умный. Какой раскраски?

привет.
вообше то надо в лубое кол-во цветов, но для начала пусть будет 2.

Кто может подказать алгоритм

№ 5

Briska

Дата : 20-08-06, Вск, 15:40:33

Автор: Тигра
Дата : 20-08-06, Вск, 21:01:39

BFS

Tigra, БФС я бы мог если бы знал что граф так расположен, но у меня есть толко vertices and edges и никакой другой инфы по spacial distribution.

Кто может подказать алгоритм

№ 6

Танкист

Дата : 20-08-06, Вск, 17:58:31

Тупею на глазах

Какая дoлжна быть закономерноость расположения цветов и какие параметры графа?

Не соблазняйтесь, если, зачешутся вдруг руки,
Одеть чего не надо куда-то не туда.
[ 21-08-06, Пнд, 00:59:38 Отредактировано: Танкист ]

Кто может подказать алгоритм

№ 7

Briska

Дата : 20-08-06, Вск, 18:03:50

Автор: Танкист
Дата : 21-08-06, Пнд, 00:58:31

Тупею на глазах Какая дoлжна быть закономерноость расположения цветов и какие параметры графа?

Привет. Спасибо за ответ.
значит раскраска должна проиcодить следующим образом:

кол-во edges каждого из цветов должна быть примерно одинакова, и verteces к которым РАЗНЫХ цветов edges инциденты минимизирована.

Например в той картинке что я аплоадил видно что и красных и зеленых рёбер по 14, то есть хороший баланс достигнут.
И есть три вершины к которым подходят и красные и зеленые рёбра.

В общем, эта проблема типа Graph (or Hypergraph) partitioning problem. Только вместо того чтоб разделять вершины, окрашиваются edges.

надеюсь разъяснил подробно.

Спасибо.

[ 21-08-06, Пнд, 01:29:58 Отредактировано: Briska ]

Кто может подказать алгоритм

№ 8

Krasnaja Shapka

Дата : 21-08-06, Пнд, 12:11:24

я ниче не понял, можно разъяснить?

я понял так: есть граф, о котором мы ничего не знаем, и есть начальная вершина графа, от которой мы пляшем, и все?

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

Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
[ 21-08-06, Пнд, 19:12:45 Отредактировано: Krasnaja Shapka ]

Кто может подказать алгоритм

№ 9

Briska

Дата : 22-08-06, Втр, 05:29:19

Автор: Krasnaja Shapka
Дата : 21-08-06, Пнд, 19:11:24

я ниче не понял, можно разъяснить?

OK давай попробую обьяснить дальше..

Про граф нам известно следуюшее...

Мы знаем что вершины прономерованы 1 до N. Мы знаем что каждая вершина имеет соединения с другими вершинами и мы их знаем. То есть, к примеру возмем вершину помеченую r3 то известно что она соединяется с вершинами с8 и с3.

Хоть вершины считаются он 1 до N. на этом графе они показаны как r1 - r8 (1 - 8) u c1-c8 (9 - 16). Однако если эта информация как то помогает, то можно и пользовать те названия.

Кто может подказать алгоритм

№ 10

Krasnaja Shapka

Дата : 23-08-06, Срд, 06:21:01

я вообще-то потом перечитал (например про бфс в инете) и врулил что главное минимизировать кол-во вершин с разными цветами, ес? а эта задача кроме как перебором вообще решается? или проблема даже осуществить перебор?

Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.

Кто может подказать алгоритм

№ 11

Танкист

Дата : 23-08-06, Срд, 16:08:59

Briska, я так понимаю нужен приближенный алгоритм?
С Graph partitioning не понял, там надо разделить вершины например на две группы так, что бы любое ребро соединяло две вершины из разных групп.
Здесь, если рассматривать ребра как вершины, а вершины как ребра Hypergraph, то надо найти две группы новых вершин так, чтоб они соединялись минимальным количеством гиперребер (что-то в этом роде). Это скорее похоже Flow problem и нахождение минимального сечения (Minimal Cut).

Нет?
Так давно это учил, что уже плохо помню.

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

Кто может подказать алгоритм

№ 12

Briska

Дата : 24-08-06, Чтв, 19:56:12

Автор: Krasnaja Shapka
Дата : 23-08-06, Срд, 13:21:01

я вообще-то потом перечитал (например про бфс в инете) и врулил что главное минимизировать кол-во вершин с разными цветами, ес? а эта задача кроме как перебором вообще решается? или проблема даже осуществить перебор?

Шапка, примерно так. но минимизорование не должно нарушать баланс - число ребер каждого света должно быт как можно ближе приравнено к average.

Автор: Танкист
Дата : 23-08-06, Срд, 23:08:59

Briska, я так понимаю нужен приближенный алгоритм?
С Graph partitioning не понял, там надо разделить вершины например на две группы так, что бы любое ребро соединяло две вершины из разных групп.
Здесь, если рассматривать ребра как вершины, а вершины как ребра Hypergraph, то надо найти две группы новых вершин так, чтоб они соединялись минимальным количеством гиперребер (что-то в этом роде). Это скорее похоже Flow problem и нахождение минимального сечения (Minimal Cut).

Нет?
Так давно это учил, что уже плохо помню.

Танкист. Спасибо за ответ. Я вижу вы человек знаюший о чем звук в большом смысле. Как раз таки нужен приближенный алгоритм ибо, сама проблема, также как и Graph i Hypergraph partiotioning да и Flow problem являются NP-Complete.
На счет Hypergraph... эта работа что я делаю , по краинеи мере ее идея, побить скорость алгоритма с использованиями Hypergraphs. ибо Графы нуждаются в прошше heuristics.

Кто может подказать алгоритм

№ 13

Briska

Дата : 03-09-06, Вск, 13:32:53

че то все затихло..
а помоч все еше надо..

Кто может подказать алгоритм

№ 14

Танкист

Дата : 11-09-06, Пнд, 08:47:45

А в рамках чего вам надо решить задачу? Что бы дать совет сходу надо специализироваться в этой области. А решение такой задачи выглядит на уровне научной статьи... Можно конечно кидать фразы, типа попробовать ..., но толку-то, от этого задача не решится. Готового ответа у меня нет, а заниматься решением - это научное исследование. В общем несколько странная задача в рамках такого форума. Но если мне что-то придет в голову, обязательно напишу.

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