Тема для волосатых мужиков (задача с графом) - StarCraft FOREVER
StarCraft Forever! - 7x.ru StarCraft Information Site
История
StarCraft: История терранов StarCraft: История протоссов StarCraft: История зергов

Вернуться   StarCraft FOREVER > Общие форумы > Общий форум

Общий форум Разговор на любые темы не входящие в рамки флейма Если вы не знаете, где написать тему, создайте здесь, и модераторы переместят ее.

Ответ
 
Опции темы Опции просмотра
Старый 19.07.2011, 11:22   #1
uti
Местный
 
Аватар для uti
 
Регистрация: 16.06.2004
Сообщений: 3,752
Нарушения: 14
ICQ:
Тема для волосатых мужиков (задача с графом)

Пишу свою браузерную игру с маджонгом и гейшами. Возникла следующая проблема.

Есть поле из гексов и некий источник энергии, от которого она может распространяться по всем ячейкам. При этом поток может разделяться и объединяться сколь угодно раз. Но в нём не должно быть циклов. Проще говоря, если двигаться по любым энергетическим веткам вдоль "течения", то никогда нельзя оказаться в одной ячейке более одного раза, то есть нельзя сделать петлю.
Как детектить такое замыкание?
Зелёный - как можно. Красный - как нельзя.

p.s. На одном форуме порекомендовали топологическую сортировку, но я что-то не понял, как её тут применить.


Последний раз редактировалось uti; 19.07.2011 в 11:30.
uti вне форума   Ответить с цитированием
Старый 19.07.2011, 15:47   #2
[7x]Злобный Head
Бессмысленный и беспощяд
 
Аватар для [7x]Злобный Head
 
7x Fun
Регистрация: 10.12.2005
Адрес: Российская Олигархическая Федеративная Капиталистическая Республика
Сообщений: 4,073
Нарушения: 1
ICQ: 259950760
Отправить сообщение для [7x]Злобный Head с помощью ICQ
Полярные координаты, проверка списка точек на существующие и если совпадает, то запрещать.
__________________

Нам сказали, что Социализм - зло! Я же говорю, что Социализм, как форма правления - процветание!
Террор является уникальным инструментом для решения внутриполитических и социальных вопросов.
Чтобы произошли изменения в политике нашей Власти, необходимо уничтожить \"труп Советской Системы\" и создать новую систему, цель которой будет являться - Народ.


[7x]Злобный Head вне форума   Ответить с цитированием
Старый 19.07.2011, 16:27   #3
Dyavol
Местный
 
Аватар для Dyavol
 
Регистрация: 24.05.2006
Сообщений: 1,004
Нарушения: 0
ICQ: 296850678
Отправить сообщение для Dyavol с помощью ICQ Отправить сообщение для Dyavol с помощью Skype™
Хотел предложить один способ, но он разрешает стрелку из клетки 3.0 в 2.1
Так что надо ещё подумать.

Добавлено через 4 минуты
А хотя это ж и не проблема. Цикла то не будет.
Короче вот:

можно пометить все клетки нулями и клетку с источником в единицу. Потому клетку в которую сделан первый шаг поставить в двойку и так дальше. Таким образом число в клетке будет на единицу больше, чем количество шагов нужное, чтоб туда пройти (за исключением нуля)
Во первых при расстановке менять номер можно только если текущий меньше, чем тот, что там стоял (это если хочется лабиринт сделать и зафигачить там поиск крадчайшего пути. Для твоей задачи достаточно просто проверки на ноль)
А если есть ещё и стрелки, то правильными считать только те, у которых начало стрелки на единицу меньше конца стрелки. Остальные не правильные.

Если хочется сделать затухание энергии, то можно начинать не с единицы, а с максимальной дальности распространения энергии, и отнимать по единице.
__________________
Богат не тот у кого больше, а тот, кто нуждается в меньшем.
Dyavol вне форума   Ответить с цитированием
Старый 19.07.2011, 18:27   #4
Dyavol
Местный
 
Аватар для Dyavol
 
Регистрация: 24.05.2006
Сообщений: 1,004
Нарушения: 0
ICQ: 296850678
Отправить сообщение для Dyavol с помощью ICQ Отправить сообщение для Dyavol с помощью Skype™
К цикличности поидее будут приводить только стрелки, в которых от большего к меньшему идёт. Если от меньшего к большего или даже между одинаковыми, то циклов не будет.
__________________
Богат не тот у кого больше, а тот, кто нуждается в меньшем.
Dyavol вне форума   Ответить с цитированием
Старый 19.07.2011, 18:41   #5
uti
Местный
 
Аватар для uti
 
Регистрация: 16.06.2004
Сообщений: 3,752
Нарушения: 14
ICQ:
Но "от большего к меньшему" - недостаточное условие для зацикливания.

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

код javascript:
Код:
var edges = [
  [1],        // из 0
  [2],        // из 1
  [3],        // из 2
  [4,15],     // из 3
  [],         // из 4
  [8],        // из 5
  [7],        // из 6
  [10],       // из 7
  [10],       // из 8
  [],         // из 9
  [9],        // из 10
  [5,12],     // из 11
  [1],        // из 12 (!)
  [11],       // из 13
  [6],        // из 14
  [13,14]     // из 15
];

// true если петель нет, false если есть
alert(checkGraph(edges));

function checkGraph(edges) {
  var n = edges.length;
  var clr = new Array(n);
  var dfs = function(v) {
    if (clr[v] == 1) return true;
    if (clr[v] == 2) return false;
    clr[v] = 1;
    for (var i = 0; i < edges[v].length; i++) {
      if (dfs(edges[v][i])) return true;
    }
    clr[v] = 2;
    return false;
  };
  for (var i = 0; i < n; i++) {
    if (dfs(i)) return false;
  }
  return true;
}
А вот картинка, по которой я вершины нумеровал. Можно поэкспериментировать.

uti вне форума   Ответить с цитированием
Старый 19.07.2011, 18:49   #6
Dyavol
Местный
 
Аватар для Dyavol
 
Регистрация: 24.05.2006
Сообщений: 1,004
Нарушения: 0
ICQ: 296850678
Отправить сообщение для Dyavol с помощью ICQ Отправить сообщение для Dyavol с помощью Skype™
А придумаешь конфигурацию при которой от меньшего к большему идёт, но при этом зациклено?
__________________
Богат не тот у кого больше, а тот, кто нуждается в меньшем.
Dyavol вне форума   Ответить с цитированием
Старый 20.07.2011, 10:18   #7
uti
Местный
 
Аватар для uti
 
Регистрация: 16.06.2004
Сообщений: 3,752
Нарушения: 14
ICQ:
Не думаю, что такое возможно. Для зацикливания "поток" из клетки должен вернуться в неё же. В случае этого поля минимальный цикл может состоять из трёх стрелок, а, значит, замыкающая клетка будет минимум на два уровня выше, чем замыкаемая.
uti вне форума   Ответить с цитированием
Старый 20.07.2011, 11:04   #8
[7x]Злобный Head
Бессмысленный и беспощяд
 
Аватар для [7x]Злобный Head
 
7x Fun
Регистрация: 10.12.2005
Адрес: Российская Олигархическая Федеративная Капиталистическая Республика
Сообщений: 4,073
Нарушения: 1
ICQ: 259950760
Отправить сообщение для [7x]Злобный Head с помощью ICQ
Мега, объясни, почему незаюзать просто проверку на присутствие стрелки.
__________________

Нам сказали, что Социализм - зло! Я же говорю, что Социализм, как форма правления - процветание!
Террор является уникальным инструментом для решения внутриполитических и социальных вопросов.
Чтобы произошли изменения в политике нашей Власти, необходимо уничтожить \"труп Советской Системы\" и создать новую систему, цель которой будет являться - Народ.


[7x]Злобный Head вне форума   Ответить с цитированием
Старый 20.07.2011, 11:57   #9
uti
Местный
 
Аватар для uti
 
Регистрация: 16.06.2004
Сообщений: 3,752
Нарушения: 14
ICQ:
Что значит "проверка на присутствие стрелки"? Давай не будем говорить на языке гуманитариев. Напиши по пунктам алгоритм, который ты предлагаешь, и я поищу в нём ошибку (но, скорее всего, ты сам её найдешь, когда займёшься этим).

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

Последний раз редактировалось uti; 20.07.2011 в 12:14.
uti вне форума   Ответить с цитированием
Старый 20.07.2011, 14:32   #10
[7x]Злобный Head
Бессмысленный и беспощяд
 
Аватар для [7x]Злобный Head
 
7x Fun
Регистрация: 10.12.2005
Адрес: Российская Олигархическая Федеративная Капиталистическая Республика
Сообщений: 4,073
Нарушения: 1
ICQ: 259950760
Отправить сообщение для [7x]Злобный Head с помощью ICQ
У тебя поле, представляем как массив. Как предлагал дъявол сначала все 0, потом забиваем цифры в клетки куда идём. Когда делаем новую стрелку определяем куда она делается и проверяем наш элемент массива на число.

Это же старо как мир всё.

Добавлено через 3 минуты
Как раз таки как я предлагаю случая как в клетке 10 не будет, всё что отлично от заданой константы запрещает установку стрелки.

Добавлено через 3 минуты
к примеру есть поле 10*15
это массив двойной [10][15]
изначально где-то есть наш "источник добра", в массиве его положение соответствует строке и столбцу нашего массива, и значится например как - 1000, всё остально - 0
начинаем строить стрелки, если надо можно нумеровать их, и в массив заносить их порядковый номер. Если клетка массива,куда ставим новую стрелку, равна 0 то стрелка ставиться, если не равно 0, то всё стрелку ставить нельзя.

Так понятней?
__________________

Нам сказали, что Социализм - зло! Я же говорю, что Социализм, как форма правления - процветание!
Террор является уникальным инструментом для решения внутриполитических и социальных вопросов.
Чтобы произошли изменения в политике нашей Власти, необходимо уничтожить \"труп Советской Системы\" и создать новую систему, цель которой будет являться - Народ.


[7x]Злобный Head вне форума   Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
FP-Stream SeleCT (Terran, Korea) [Тема обновлена 08.03.2016] RusAiur Реплеи и VOD'ы 0 08.03.2016 14:38
Тема для обсуждения LotV Вселенское Зло Обсуждение 347 23.12.2015 23:05
Очередная тема из разряда "что лучше". Зилот или архон? Резидент Маан Стратегии 2 07.04.2011 16:37


Текущее время: 22:17. Часовой пояс GMT +4.


Powered by vBulletin® Version 7.7.7
Copyright ©2002 - 2020, 7x.ru information site edition. Перевод: zCarot
Копирование информации сайта без разрешения администрации преследуется по понятиям.

Яндекс.Метрика Rambler's Top100 Яндекс цитирования