Как расставить узлы произвольного дерева? [закрыт]

#алгоритм #дерево #графы

                            
             
                
                    
                        
                            Закрыт. Этот вопрос необходимо уточнить или дополнить
подробностями. Ответы на него в данный момент не принимаются.
                            
                        
                    
                
            
                    
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Добавьте больше подробностей
и уточните проблему, отредактировав это сообщение.
                        
                        Закрыт 4 года назад.
                    
                
        

Есть произвольное дерево, узлы-братья удалены друг от друга на динамически задаваемое
значение (в данном случаи 20), так же как и узлы-соседи (в данном случаи 40). В тот
момент, когда самая левая ветвь формируется, вызывается метод расстоновка_узлов в который
передается самый верхний-левый и самый верхний-правый и разница на которую увеличился
промежуток между ними (в данном случаи 20).
Вот что происходит в методе расстоновка_узлов -  

  


в цикле проходим от верхний-левой до верхней-правой и считаем промежутки (в данном
случаи это шесть пустых клеточек, которые как говорил ранее по 20, то есть сумма 120);  
делю сумму полученную на предыдущем шаге на кол-во узлов плюс один (120 / 3 = 40);  
проверяю на сколько текущий узел (я начинаю с лева на право и по этому текущий узел
это тот у которого два ребенка) удален от левого узла-брата (в данном случаи это 80).  
теперь я вычитаю из 80 - 40 = 40, это значение расстояние на которое я смещу текущую
ноду чтобы оказаться в нужном месте.
если это значение (40) больше чем то на которое увеличилось расстояние между двумя
крайними нодами, то это значение становится меньшим. То есть рассчитал что 40, но оно
больше позволенного и по этому значение меняется на 20.  
перемещаю ноду.  


  

Повторяю шесть предыдущих шагов для следующей ноды -
1. получаю 60
2. 60 / 2 = 30
3. 40
4. 30
5. 10
6. ... 

  

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

На тот случай, если у меня сначала идет узел который можно сдвинуть на "сколько-то"
(без детей), а после тот который уже нельзя сдвинуть на "сколько-то", то второй я снова
сдвигаю на максимум, но при этом выполняю алгоритм с самого начала (точнее с самой
последней удачной точки), но на время подменяю самый верхний-правый текущим.  

Я бы показал код, но я не хочу чтобы Вы смотрели его недочеты, а лишь хочу чтобы
Вы поняли смысл.  

Вот. Но дальше я столкнулся с следующей проблемой, да и возможно это только одна из ...

Входные данные те же, но все ломается. Алгоритма, как я хотел, не получилось, да
и придумать я не могу.
Ниже конечный результат - 


Что есть у нод
indent - значение на которое текущая нода удалена от предыдущей ||->||
leftOffset - это значение на которое я смещаю влево. В самом начале оно ноль
rightOffset = это то значение на которое смещаю вправо. И тоже по дефолту ноль.  

Вот. Сами ноды, как обычные ноды, ссыдка на парента, в котором они хранятся в индексированном
массиве. Есть методы для получения ноды по индексу и получение самого индекса.
    

Ответы

Ответ 1

В общем, нужно расставлять узлы уже по факту, а не извращаться с двиганием в каких-то
рамках. Есть обе константы, "братья" и "соседи", причем "соседи" определяет, насколько
должны отстоять друг от друга соседние поддеревья на уровнях ниже первого, а "братья"
- на первом. Тогда задачу нужно решать снизу вверх: для каждого поддерева вначале выстраиваем
каждое из собственных поддеревьев, после чего выстраиваем текущее подерево, вычисляя
для каждого следующего поддерева минимальное смещение относительно нуля, при котором
на каждом уровне это поддерево не будет мешать уже установленным поддеревьям. В итоге
каждое подерево будет иметь параметр "занятый диапазон" на каждом уровне, где у него
есть хоть один лист, по нему и будет идти сравнение при размещении текущего поддерева
на верхнем уровне.

Т.е. алгоритм выглядит так:

BuiltTree buildTree(Tree tree) {
    BuiltTree[] siblings;
    foreach (subTree in tree.subTrees) siblings.push(buildTree(subTree));
    BuiltTree result=new BuiltTree(); // пустое
    foreach (sibling in siblings) {
        int minRightPos=0;
        for (i=0;i

Как описать граф, где важны только рёбра?

#графы #база_данных

Планирую проект, где будет множество данных о связях между очередными двумя узлами,
и эти связи и их многочисленные свойства — главная информация, с которой вся работа.
Можно сказать, что есть граф, у которого узлы лишь идентифицируются как-то, чтобы
не перепутать, а область интереса это рёбра.
Как бы вы стали описывать и хранить такие данные?
Варианты, которые пока приходят на ум:

реляционная БД, таблица нод, таблица связей: node1id, node2id, json_properties
какая-то специфическая, может, не реляционная бд, заточенная под описание графов?

Задачи: хранить, добавлять новые связи, определять, связаны ли две ноды через цепочку
связей?    

Ответы

Ответ 1

Если я правильно понял задачу, то, как вариант - neo4j, статья на хабре


Ответ 2

Возможно ответ на Ваш вопрос Язык Анимо.


Ответ 3

Можно попробовать задать переменными PHP координаты и эти переменные в MySQL, или
если человек рисует граф в онлайне то просто в PHP

Оптимальный алгоритм на графах

#графы

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

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

Может существует более оптимальное решение?




    

Ответы

Ответ 1

А если так: 


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


Найденная компонента связности и есть искомый результат.

Найти минимальное расстояние между точками

#python #python_3x #алгоритм #графы

Нам нужно перейти из одной точки на плоскости в другую.
Но у нас есть ограничение на расстояние перехода за 1 раз

Также у нас даны координаты еще нескольких точек
Например:

1 1    
6 6    
2 3    
6 7    
3 9


Если сразу напрямую перейти нельзя(из-за огран), то придется переходить через другие
точки.Как найти минимальное расстояние?
    

Ответы

Ответ 1

Идея: строим граф, отбросив все рёбра не удовлетворяющие ограничению. Веса рёбер
- расстояния. Дальше ищем кратчайший путь.

Реализация с использованием модулей: Pandas, SciPy, NetworkX:

import pandas as pd
import networkx as nx
from scipy.spatial.distance import cdist, pdist, squareform
import matplotlib.pyplot as plt

# maximum allowed distance
max_dist = 5

# reading points coordinates CSV -> Pandas.DataFrame
df = pd.read_csv(r'c:/temp/data.csv', header=None, names=['x','y'])

# adjacency matrix of distances
adj_mx = squareform(pdist(df))
adj_mx[adj_mx > max_dist] = 0

# building a graph from the adjacency matrix
G = nx.from_numpy_matrix(adj_mx)

source = 0  # index of the source point
target = 3  # index of the target point

path = nx.shortest_path(G, source=source, target=target, weight='weight')
print(f'the shortest path between [{source}] and [{target}]: {path}')


#### drawing the graph
# node's positions
pos = nx.spring_layout(G)
edge_labels = {k:f'{v:.3}' for k,v in nx.get_edge_attributes(G, 'weight').items()}

nx.draw_networkx(G, pos, node_size=700)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

plt.show()


Вывод на печать:

the shortest path between [0] and [3]: [0, 2, 1, 3]


График:


Ответ 2

Построить граф связности точек с учетом ограничений по переходам.
Использовать А*


Ответ 3

Возможно вам поможет волновой алгоритм.
- посетите все возможные точки от начальной, отметьте их как "шаг 1"
- посетите все непосещенные точки, доступные из точек "шаг 1" и отметьте их как "шаг 2"
- повторяйте шаги, пока не посетите нужную вам точку
- когда дойдете до нужной точки - восстановите путь назад до исходной находя ближайшую
точку предыдущего шага

Сортировка точек ломаной линии на 2D плоскости

#массивы #сортировка #графы

Есть массив точек с координатами x, y.
Точки разбросаны хаотично, но если соединить каждую из них с ближайшими, то получим
ломаную, с началом и концом, пример:

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

То, что набыдлокодил я в состоянии невменяемости, выкладывать с вашего позволения
не стану.

upd: Что я попробовал: перебираю точки в массиве, для выбранной точки (пусть будет
2), ищу двух ближайших соседов, добавляю новые ребра в массив: 2-4 и 2-5. При дальнейшем
переборе ребра 4-2 и 5-2 отсеиваются как повторы. Но, для начала, ребер в некоторых
случаях получится не 5, а 6-7, например для приведенного рисунка у точки 1 будет так
же два ребра: 1-2 и 1-4, что неверно и нужна пост-обработка массива для отсеивания
лишних ребер. А потом эти ребра еще и отсортировать нужно, пока не соображу как.
    

Ответы

Ответ 1

Мне алгоритм решения задачи видится следующим образом:


Найти конец ломаной линии.
Конечную точку поместить в начало массива.
Использовать конечную точку как текущую.
Сравнить расстояния от текущей точки до всех остальных и найти ближайшую точку (если
есть несколько точек с одинаковым расстоянием, равным минимальному, можно взять любую
из них).
Переместить ближайшую точку в массиве, в позицию, следующую за текущей.
Использовать ближайшую точку как текущую.
Повторить пункты 4 - 7 для всех оставшихся точек


На выходе вы получите массив точек удовлетворяющий начальному условию.

UPD:

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


Ответ 2

Для начала определяете начальную точку (я так понимаю это будет точка с минимальными
координатам)
Далее от неё ищете ближайшую (для простоты перебором из оставшихся точек)
Исключаете точку
Повторяете пункт 2 пока есть точки


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

Для других алгоритмов, на мой взгляд, необходимы уточнения:


Критерий начальной точки
Ближайшая точка - это модуль вектора (длинна ребра) или ближайшая по оси X например?
Как правильно соединить такой набор точек:

Кратчайший путь в графе с дополнительными условиями

#python #алгоритм #графы

Задача:

Автомобилист хочет проехать от города u до города v, по стране с количеством городов
n. Известны длины дорог между всеми городами, дороги двухсторонние. Автомобиль имеет
ограниченный запас топлива k, в начале пути бак полностью заполнен. Восполнять запас
топлива до максимального k он может в некоторых городах по дороге. Нужно посчитать
сколько минимум нужно будет сделать заправок по дороге чтобы попасть из города u в город v.

Формат входных данных

Первая строка содержит пять целых чисел: k — сколько километров может проехать машина
без дозаправок, n — количество городов, m — количество дорог, u — номер города начала
дороги, и v — номер города, куда нужно доехать (1 ≤ k ≤ 500, 2 ≤ n ≤ 10 000, 0 ≤ m
≤ 10 000, 1 ≤ u,v, ≤ n, u ≠ v).

В следующих m строках задаются дороги. В i-й из этих строк записаны три числа p_i,
q_i, r_i —
номера двух городов, которые соединяет очередная двухсторонняя дорога, и её длина.
(1 ≤ p_i, q_i ≤ n, 1≤ r_i ≤ 10^9)

Следующая строка содержит целое число l — количество заправок (0 ≤ l ≤ n). Наконец,
последняя строка содержит l чисел a_1, a_2, . . . , a_i — номера городов с заправками
в порядке возрастания (1 ≤ a_1 < a_2 < ... < a_l ≤ n).

Формат выходных данных
Выведите -1, если невозможно доехать от города с номером u до города с
номером v, или минимальное количество заправок, если это возможно.

Примеры:

input #1:

3 3 3 1 3
1 2 3
1 3 4
2 3 3
2
2 3


output #1:

1


input #2:

3 3 3 1 3
1 2 2
1 3 4
2 3 2
0


output #2:

-1


input #3:

3 3 3 1 3
1 2 2
1 3 4
2 3 1
0


output #3:

0


Ограничение по времени: 2 секунды;

Ограничение по памяти: 512 мегабайт

Моё решение:

k,n,m,u,v = [int(i) for i in input().split()] 

adj = {}
for j in range(m):
    p,q,r = [int(i) for i in input().split()]
    if p-1 in adj:
        adj[p-1].append([q-1,r])
    else:
        adj[p-1] = [[q-1,r]]
    if q-1 in adj:
        adj[q-1].append([p-1,r])
    else:
        adj[q-1] = [[p-1,r]]

l = int(input())

refills = [False] * n
if not l is 0:
    for i in input().split():
        refills[int(i)-1] = True

count = [0] * n
tank = [None] * n
level = [-1] * n

def bfs(s):
    global level,charging,k
    level[s] = 0 
    queue = [s]
    tank[s] = k
    while queue: 
        v = queue.pop(0)

        for w_ in adj[v]: 
            w = w_[0]; r = w_[1];  
            if tank[w] is None:
                tank[w] = k
            if level[w] is -1 and r<=tank[v]:  

                level[w] = r+level[v]
                if refills[w]:
                    tank[w] = k
                    count[w]+=1
                else:
                    tank[w] -=r
                queue.append(w)  
bfs(u-1)
if level[v-1] is -1:
    print(-1)
else:
    print(count[v-1])


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

Подскажите, пожалуйста, что не так в алгоритме. Либо посоветуйте иной способ решения.
    

Ответы

Ответ 1

Задача на самом деле достаточно простая. Давайте посмотрим на ограничения. 10к вершин.
500км запаса хода максимум (!!). Кстати можно сразу убирать дороги длиннее k, всё равно
проехать не сможем. 

А теперь самый интересный момент - из 1 вершины {i} сделаем k вершин {(i,d)} которые
будут показывать количество заправок на маршруте от старта к i, при этом в пункте i
 осталось d км топлива. 

Оценим сложность. 10к * 500 = 5кк. По памяти это около 20 мегабайт. По времени. 5кк
вершин. Количество ребёр в сумме пусть тоже будет 5кк. Алгоритм комбинированного обхода
(или как его правильно) O( (N+M) ) ~ 10kk вполне успевает. Идея алгоритма - идём без
заправок пока можем, но складываем отдельно места где можно заправится. Потом эти места
обрабатываем в порядке очереди. 

Ну как бы и всё. Дальше дело техники сделать переход. Из i->j  переход возможен только
из вершин где топлива достаточно (обычный цикл от длины до k) без увеличения ответа.
И с увелечением ответа на 1 в k - длину. 

Ответ - минимум по всем "размноженным" последним вершинам. 

Реализацию проще делать через хранение массива [0,k] в каждой обычной вершине.

Код пока не пишу. Если возникнут вопросы по реализации - помогу.


Ответ 2

Предлагаю решение, похожее на алгоритм Дейкстры. Не уверен, можно ли в принципе уложиться
во временной лимит 2 секунды при использовании Python. Я потестировал это решение на
больших рандомных графах - 6000 городов, 9000 дорог, результаты от 0.8 до 4 секунд
в зависимости от удачности сложения графа. 

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

Алгоритм


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


если город имеет заправку, то расстояние до заправки = 0.
если не имеет, то пишем расстояние до ближайшего города с заправкой, из уже посещённых.

Города, дальше которых машина не смогла проехать из-за нехватки топлива, запоминаем
- на следующем витке алгоритма будем их заправлять в ближайшем посещённом городе (просто
вычитая расстояние до этого города из стартового запаса хода) и повторять шаги 1, 2, 3.


Другими словами: первая заправка - едем во все стороны, добавляя каждый посещённый
город в ответ. Топливо кончилось - встали в конечном городе. Пошла вторая заправка.
Все вставшие машины заправляем и опять едем до упора. Так мы доберёмся до каждого города
на карте. Или недоберёмся - заправки кончились, искомый город не нашли, возвращаем -1.

Замечание: все дороги, длина которых больше, чем максимальный запас хода (полный
бак) можно исключить в самом начале - на этапе формирования списка смежности.

source.py

def find_shortest_path():
    def make_adj_dict(roads_num, max_pos_dist):
        adj_dict = {k : {} for k in range(1, roads_num + 1)}

        while roads_num > 0:
            city_a, city_b, distance = map(int, input().split())

            if distance <= max_pos_dist:
                adj_dict[city_a][city_b] = distance
                adj_dict[city_b][city_a] = distance

            roads_num -= 1

        return adj_dict

    max_possible_distance, cities_num, roads_num, start_city, end_city = map(int,
input().split())
    adj_dict = make_adj_dict(roads_num, max_possible_distance)
    refuel_num = int(input())
    if refuel_num > 0:
        cities_with_gs = {int(num) : True for num in input().split()}
    else:
        cities_with_gs = {}

    answers = {}

    one_tank_reachable_cities = set()
    one_tank_reachable_cities.add(start_city)
    should_be_refueled_set = set()
    dist_to_last_gs = {k : 0 if k in cities_with_gs else float("inf") for k in range(1,
cities_num + 1)}

    fuel_left_dict = {k : 0 for k in range(1, cities_num + 1)}
    fuel_left_dict[start_city] = max_possible_distance

    for refuel_cnt in range(refuel_num + 1):

        if should_be_refueled_set:
            for city in should_be_refueled_set:   
                fuel_residue = max_possible_distance - dist_to_last_gs[city] 
                if fuel_residue >= 0:
                    fuel_left_dict[city] = fuel_residue 
                    one_tank_reachable_cities.add(city)    

            should_be_refueled_set = set()

        while one_tank_reachable_cities:
            city_a = one_tank_reachable_cities.pop()
            answers[city_a] = refuel_cnt

            for city_b, a_to_b_dist in adj_dict[city_a].items():
                dist_to_last_gs[city_b] = min(dist_to_last_gs[city_a] + a_to_b_dist,
dist_to_last_gs[city_b])
                if city_b in answers:
                    continue

                fuel_before_ride = fuel_left_dict[city_a]

                if a_to_b_dist <= fuel_before_ride:
                    one_tank_reachable_cities.add(city_b)
                    fuel_after_ride = fuel_before_ride - a_to_b_dist
                    fuel_left_dict[city_b] = max(fuel_after_ride, fuel_left_dict[city_b])
                else:
                    should_be_refueled_set.add(city_a)

    return answers[end_city] if end_city in answers else -1


Тестирование

cnt = 1
while True:
    try:
        print(find_shortest_path(), end='')
        print(f"\t#Case № {cnt}")
    except EOFError:
        break
    cnt += 1


input.txt

### Case № 1, output = 1
3 3 3 1 3
1 2 3
1 3 4
2 3 3
2
2 3
### Case № 2, output = 0
3 3 3 1 3
1 2 2
1 3 4
2 3 1
0
### Case № 3, output = -1
3 3 3 1 3
1 2 2
1 3 4
2 3 2
0
### Case № 4, output = 3
50 7 8 1 7
1 2 50
1 3 50
1 4 50
2 5 50
3 5 60
4 5 40
5 6 40
6 7 30
4
2 3 5 6
### Case № 5, output = 1
120 7 8 1 7
1 2 50
1 3 50
1 4 50
2 5 50
3 5 60
4 5 40
5 6 40
6 7 30
2
2 3


Строки начинающиеся с ### нужны для наглядности, перед запуском программы их надо
убрать. Я их не удаляю из файла input.txt вручную, а пропускаю через sed перед подачей
на ввод программы (пользуюсь Ubuntu):

./source.py < <(sed '/#/d' input.txt)


Output

1   #Case № 1
0   #Case № 2
-1  #Case № 3
3   #Case № 4
1   #Case № 5

Является ли граф деревом [закрыт]

#алгоритм #графы #дерево

        
             
                
                    
                        
                            Закрыт. На этот вопрос невозможно дать объективный ответ.
Ответы на него в данный момент не принимаются.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Переформулируйте вопрос,
чтобы на него можно было дать ответ, основанный на фактах и цитатах, отредактировав его.
                        
                        Закрыт 4 года назад.
                                                                                
           
                
        
Задачка: Предложите алгоритм, который определяет, является ли граф деревом.
Мое решение, которое, как оказалась, неверное 
bool is_rec( int arr[SIZE][SIZE], int current, int root, int find )
{
    bool endFlag = true;
    for(int i = 0; i < SIZE; ++i){
        if((arr[current][i] == 1)&&(i!=root)){
            if(i!=find){
                endFlag = endFlag&&is_rec(arr,i,current,find);
            }else{
                return false;
            }
        }
    }
    return endFlag;
}

bool IsTree( int arr[SIZE][SIZE] )
{
    return is_rec(arr,0,0,0);
}

Думаю, некоторым будет интересно решить :)    

Ответы

Ответ 1

Дерево - связный граф с n-1 ребром.
bool dfs(int i, int arr[SIZE][SIZE], bool col[SIZE]) {
  if (col[i]) {
    return 0;
  }
  col[i] = true;
  for (int j = 0; j < SIZE; ++j) {
    if (ar[i][j]) {
      dfs(j, arr, col);
    }
  }
}

bool IsTree(int arr[SIZE][SIZE]) {
  int edges = 0;
  for (int i = 0; i < SIZE; ++i) {
    for (int j = i + 1; j < SIZE; ++j) {
      if (arr[i][j]) {
        edges++;
      }
    }
  }
  if (edges != SIZE - 1) {
    return false;
  }
  bool col[SIZE];
  memset(col, 0, sizeof(col));
  dfs(0, arr, col);
  for (int i = 0; i < SIZE; ++i) {
    if (!col[i]) {
      return false;
    }
  }
  return true;
}


Ответ 2

Моё решение на Pascal. Граф задаётся матрицей смежности (1 - есть ребро, 0 - иначе).
maxV - максимальное число вершин
maxE - максимальное число рёбер
Храню граф списком рёбер.
const
        maxV     = 111;
        maxE     = 111111*2;

var
        n,m,i,j,x       : longint;

        ef,es,next      : array [1..maxE] of longint;
        first,last      : array [1..maxV] of longint;
        c               : longint;

        used            : array [1..maxV] of boolean;
        flag            : boolean;

procedure add(v1,v2 : longint);
        begin
                inc(c);
                ef[c] := v1; es[c] := v2;
                if last[v1] <> 0 then next[last[v1]] := c;
                if first[v1] = 0 then first[v1] := c;

                last[v1] := c;
        end;

procedure dfs(v,dad : longint);
        var
                h,e : longint;
        begin
                used[v] := true;

                h := first[v];
                while h > 0 do begin
                        e := es[h];
                        if used[e] and (e <> dad) then begin
                                flag := false;
                                exit;
                        end;
                        if e <> dad then
                                dfs(e,v);
                        if not flag then
                                exit;
                        h := next[h];
                end;
        end;

begin
        assign(input,'input.txt'); reset(input);
        assign(output,'output.txt'); rewrite(output);

        readln(n);
        for i := 1 to n do
                for j := 1 to n do begin
                        read(x);
                        if x = 1 then
                                add(i,j);
                end;

        flag := true;
        dfs(1,1);
        for i := 1 to n do
                if not used[i] then
                        flag := false;

        if not flag then
                writeln('NO')
        else
                writeln('YES');

end.


Ответ 3

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


Ответ 4

Выполняем обычный проход по графу и каждую пройденный узел заносим в список, при
этом проверяем не содержится ли он в нем уже. Если содержится то всё не дерево :-)

Графы - дорожная сеть

#графы #cpp

Как точно называется задача для покрытия дорожной сетью?

Например есть такой неограф:



Вес дуг это расстояние между городами.

Применив минимальное остовное дерево получается такая картина:
Все вершины связаны в одну большую дорогу, но если перемещаться из Рязани в Казань(по
остовному дереву), то потребуется 3+7+7+3=20 шагов.


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



То есть должны быть еще элементы оптимизации, где будет коэфицент зависимость стоимости
прокладки дороги по отношению к времени перемещения из городов(как то так).Чем выше
такой коэфицент тем больше дуг будет между вершинами.

Есть ли конкретная задача которая этим занимается?
    

Ответы

Ответ 1

В первой формулировке (без наложения вспомогательных constraint'ов на стоимость строительства
дорог) это — задача нахождения Shortest total path length spanning tree [1], для которой
доказано, что она NP-трудная. Решить эту задачу можно с помощью приближенных алгоритмов
(см., например, первую ссылку). 


Для такой же задачи, где стоимость постройки дороги не связана с длиной дороги, это
будет задача нахождения "Constrained shortest total path length spanning tree".





Нестрого говоря, эта задача не проще предыдущей, поэтому тоже является NP-трудной.
Если формально это доказывать, наверно, нужно сделать такой же переход, как сделали
вот здесь [2]  при переходе от задачи Minimum Spanning Tree → Constrained Minimum Spanning
Tree.


Думаю, что для приближенного решения этой задачи можно придумать, как совместить
подходы [1] и [2], если у вас, конечно, много свободного времени :)

Добавить вершину в граф, для построения кратчайшего обхода всех вершин

#алгоритм #графы

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

Прошу, помогите ответом. Мне подойдет как полностью раскрытый ответ, так и ссылка
на источник с материалом по вышеописанной теме или даже небольшой намек: "в какую сторону
копать"...
    

Ответы

Ответ 1

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

Разрешение зависимостей для орграфа с циклами

#графы #зависимости #dependencies #компиляция

Балуюсь, хочу сделать транслятор из BNF в код-грамматику для LEPL. Парсер написал,
код для отдельных правил генерируется, но дальше подзастрял с порядком правил.

Есть набор правил, ссылающихся друг на друга. Зависимости можно просто представить
в виде орграфа, в котором есть циклы:



Нужно разрешить зависимости относительно заданной вершины, получив список, в котором
следует записывать правила так, чтобы последующие правила уже «видели» все требуемые
им предыдущие. Если возникает цикл — нужно перед первым употреблением поместить «предварительную
декларацию.» Т.е., для примера графа выше, если, упрощая, считать, что вершины содержат
просто строки, получить что-то в духе:

>>> deps_dict = {
...    "A": {"B", "C"},
...    "B": {"D", "E"},
...    "C": {"A", "E"},
...    "E": {"E", "D"}
... }
>>> resolve_deps(deps_dict, "A")
[
    "D"              # {}
    Predeclare("E"), # ref'd by {E, B}
    "E"              # {D, E}
    "B"              # {D, E}
    Predeclare("A"), # ref'd by {C}
    "C"              # {A, E}
    "A"              # {B, C}
]


(То, что это не единственный вариант удовлетворяющего условиям результата — понятно.)

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

Если бы циклов не было — все было бы, вроде как, понятно — про топологическую сортировку
я нашел и почитал. Но как справиться с циклами — честно говоря, пока не соображу.
    

Ответы

Ответ 1

Поскольку БНФ оперирует контекстно-свободными грамматиками, то самое простое - это
использовать соответствующий раздел теории синтаксического анализа.
Самое неприятное, что может быть в произвольно взятой КС-грамматике G - это левая
рекурсия, которая, нестрого говоря, делает грамматику G недетерминированной.



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



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



  
  Если вы действительно знаете, что делаете и хотите только избавиться от циклов,
то воспользуйтесь только шагами (1) и (2) из публикации Eliminating left-recursion:
three steps.
  



Из дополнительных референсов могу порекомендовать пост Эрика Липперта по поводу CFG
и циклов в них вообще, а также набор хороших презентаций по теории формальных языков.

Какие существуют виды деревьев или классификация деревьев в теории графов?

#дерево #графы #бинарное_дерево

Пишу работу по деревьям в теории графов и немного запутался в понятиях. Мне нужно
написать, какие существуют виды деревьев или классификацию деревьев. Я нашел что существует:
ориентированное/неориентированное дерево, остовное, лес, бинарное, n-мерное, упорядоченное
дерево. Но это всё больше похоже на свойства деревьев нежели на виды (кроме бинарного
и n-мерного). 

Что из этого (если я правильно нашел и ничего не пропустил) действительно будет являться
отдельным видом дерева? Также, есть например частный случай бинарного дерева - дерево
поиска. Будет ли такое дерево относиться к теории графов или это больше структура данных
в программировании? Тот же вопрос с деревом синтаксического анализа. И последний вопрос:
относится ли обход дерева к операциям с деревьями как графами или это алгоритм для
структуры данных - дерево?
    

Ответы

Ответ 1

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

Часть того, что вы перечислили - общие понятия для графов, часть - понятия для деревьев.

Я бы на вашем месте сделал классификацию по признакам:

По направленности - ориентированное (однонаправленное, двунаправленное), неориентированное

По степени вершины (бинарное, n-арное, и т.п.)

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

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

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

Алгоритм разбиения дерева на компоненты связности

#алгоритм #графы #дерево

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

Подскажите, какой алгоритм стоит использовать? 

Пока вижу такое решение - перебор всех пар ребер, с последующей проверкой - но это
тяжелое решение по производительности.
    

Ответы

Ответ 1

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

Обозначим любую вершину дерева корнем и далее рассматриваем корневое дерево.


Будем строить наши связные компоненты путем наращивания (и объединения) множества
поддеревьев снизу-вверх, от листьев к корню. Начинаем с набора стартовых поддеревьев,
каждое из которых состоит из одной листовой вершины дерева. 
Если на каком-то этапе построения мы обнаруживаем поддерево T с суммой Starget, то
существует решение, включающее поддерево T (если у задачи вообще есть решение). Все
остальные варианты разбиения могут лишь "наращивать" T дополнительными вершинами, суммарный
вес которых равен нулю. Будем назвать поддерево с суммой Starget завершенным.
Рассмотрим незавершенное поддерево T, корневая вершина которого являются сыном вершины
P. Ясно, что P должно входить в одну и ту же связную компоненту, что и T. 
Из последнего утверждения сразу следует, что если у нас есть несколько незавершенных
поддеревьев, корневые вершины которых являются сыновьями одного и того же предка P,
то все они должны входить в одну и ту же связную компоненту, включающую также и P.


Отсюда автоматически следует, что решение задачи достаточно тривиально: 


Начинаем с набора стартовых поддеревьев T, каждое из которых состоит из одной листовой
вершины дерева.   
Циклически обрабатываем текущий набор поддеревьев T, пока у нас не останется ровно
одно поддерево:
    Если суммарный вес какого-то поддерева строго равен Starget (завершенное поддерево),
то считаем его частью результата и исключаем из дальнейшего рассмотрения (исключаем
из T и условно исключаем из исходного дерева). 
    Если в процессе такого исключения какая-то вершина исходного дерева становится
листовой, то добавляем ее в T как отдельное поддерево.
    Если у нас в T присутствуют все незавершенные поддеревья, чьи корни являются
сыновьями некоей вершины P, то объединяем их в одно поддерево с корнем P.
По завершению работы цикла 2-5 мы получим набор связных компонент, полученных на
шаге 3, а также единственное оставшееся поддерево в T. 
    Если на шаге 3 получено ровно 2 завершенных поддерева, а вес оставшегося поддерева
в T тоже равен Starget - то это наше решение. 
    Если на шаге 3 получено ровно 3 завершенных поддерева, а вес оставшегося поддерева
в T равен нулю - то объединяем оставшееся поддерево с любым из завершенных и получаем
решение.
    В противном случае задача решения не имеет.


Ответ 2

Задачка, кажущаяся на первой взгляд, переборной со сложностью  (N -- число вершин),
может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать
ниже.

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

Во-вторых, нам нужно разбить наш граф всего на 3 компоненты связности.

Теперь давайте обсудим: как это разбивать граф на компоненты связности. Мы сразу
скажем, что разбиение на компоненты связности -- это удаление некоторых рёбер. Приведу
пример разбиения на компоненты связности следующего графа:



Получим 2 компоненты связности:



Получим 3 компоненты связности:



Другой пример. Получим 2 компоненты связности (вершина 1 -- это заменена на вершину 15):



Получим 3 компоненты связности:



Как можно наблюдать, всегда при удалении 1 ребра, появляется ещё одна компонента
связности. Это можно доказать срого. Но воздержимся, дабы не загружать текст. Таким
образом, нужно удалить 2 ребра так, чтобы у нас оказалось 3 компоненты связности.

Давайте немного переформулируем задачу. Нам необходимо поставить 2 метки на рёбра
так, чтобы в каждой компоненте оказался суммарный вес одинаковым. Что же для этого
нужно сделать? ОЧЕВИДНО! Перебрать все пары рёбер. Для этого занумеруем их от 0 до
N-1. Переберём все пары рёбер. И для каждой пары будем проверять: правильное ли у нас
разбиение или нет. Напишем псевдокод:

# Перебираем все рёбра
for i in range edge:
    for j in range edge:
       # Если разбиение делит наше дерево на равные по весу части, то заканчиваем
выполнение
       if Splitting(i, j):
           break


Очевидно, что сложность такого алгоритма будет полиномиальной 

,

где g(n) -- время работы Splitting. 

Но что делаь с функцией Splitting(i, j)? Очевидно, что Splitting(i, j) может отработать
за линейное время. Запустим из каждой вершины обход в глубину, причём, если в некоторой
вершине мы уже были, то не будем туда заходить больше. Вот и получится, что мы обошли
все вершины лишь по одному разу. Т.е. мы обошли каждую компоненту связности единожды.
В таком случае, ассимптотическое время работы будет , хотя, по факту, это будет 2N.
Внутри DFS (обход в глубину) мы будем считать веса для каждой компоненты связности.

Время работы Splitting можно улучшить следующим образом. Сделаем для этого предподсчёт.
Для каждого ребра будем хранить 2 параметра: суммарный вес вершин выше ребра и суммарный
вес ниже ребра. Приведём пример:



Т.е. для ребра, соединяющего вершины 15 (она же 1, см. выше) и 3, мы можем посчитать
суммарный вес в каждом кластере. Делать это будем следующим образом. Запустим LR-обход
дерева и для каждого ребра (Замечу, что рёбра можно ассоциировать с соответствующими
вершинами. Например, ребро (11, 10) ассоциируем с вершиной 11, ребро (6, 2) ассоциируем
с вершиной 6 и т.д. Далее будем говорить о вершинах, а не о рёбрах).

Продемонстрируем пример обхода:

0 - 10 - 11 - 12 - 13 - 15 (1) - 3 - 4 - 5 - 9 - 2 - 6 - 7 - 8


При обходе будем суммировать считать вес поддерева. Под весом поддерева будем разуметь
сумму всех вершин. Пусть на i-ом шаге мы уже подсчитали вес поддерева с корнем в вершине
v. Тогда нам необходимо перейти на уровень выше и посчитать вес поддерева более высокого
уровня. Проиллюстрируем на рисунке ниже. 



Пусть мы находимся в вершине 11. И для поддерева этой вершины мы уже посчитали вес
(на рисунке она изображена листом, но будем считать, что у неё есть поддерево). Тогда
нам необходимо перейти в вершину 10 и подсчитать вес поддерева вершины 10. В порядке
LR-обхода, посетим и подсчитаем вес поддерева с корнем в вершине 12, 13. Тогда вес
поддерева с корнем в вершине 10, будет суммой весов поддеревьев 11, 12, 13:



Имеем формулу в общем случае:



Для вершины v обозначим вес дерева выше неё:



ниже неё:



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

Очевидно, что данный алгоритм вычисления вышеуказанных характеристик отработает за
время . 

Таким образом, для каждой вершины имеем вес дерева ниже неё и вес дерева выше неё.

Теперь нам необходимо научиться быстро узнавать: лежит ли данная вершина v в поддереве
другой вершины u. Введём функцию:



Для её быстрого вычисления нам понадобятся дополнительные ухищрения. И ещё один предподсчёт.

Алгоритм Дейкстры. Почему все веса должны быть больше, либо равны нулю?

#алгоритм #графы

Сидел, читал про алгоритм Дейкстры и Форда-Беллмана. В определении данных алгоритмов
есть условие - всё веса рёбер должны быть больше, либо равны нулю. Объяснения не нашел.
Почему накладывается такое условие?
    

Ответы

Ответ 1

На самом деле все по-другому.

Алгоритм Дейкстры является в некотором роде "жадным" - найдя один раз минимальный
путь до вершины, он фиксирует его как минимальный навсегда - поскольку путь через другие
вершины не может быть короче найденного.

Но в графе с отрицательными дугами это не так! Рассмотрим такой вот граф, заданный
матрицей смежности:

+---+---+---+---+
|   | А | Б | В |
+---+---+---+---+
| А |   | 4 | 2 |
+---+---+---+---+
| Б |   |   |-3 |
+---+---+---+---+
| В |   |   |   |
+---+---+---+---+


Запустим алгоритм Дейкстры из вершины А. На первом шаге у нас будут расстояния до
вершин Б и В - 4 и 2 соответственно, поэтому алгоритм решит, что уже нашел кратчайший
путь к вершине В - ведь кратчайший путь к В никак не может идти через Б, не так ли?
С сожалению, не так - очевидно, путь А-Б-В на самом деле короче чем А-В.

Поэтому алгоритм Дейкстры не может работать при наличии в графе отрицательных дуг.

Алгоритм же Форда-Беллмана (он же алгоритм Беллмана-Форда) таких предположений не
делает - а потому может работать почти на любых графах, ценой значительного замедления
по сравнению с Дейкстрой. Почему я говорю "почти на любых"? Потому что алгоритм Форда-Беллмана
все равно не может работать на графах с отрицательными циклами.

Просто потому что понятие "кратчайший путь" в таких графах не определено. Всегда
можно пройтись по отрицательному циклу еще один раз - и получить еще более короткий путь.

Тем не менее, существует модификация алгоритма Беллмана-Форда, которая позволяет
обнаружить цикл отрицательного веса в графе. Достаточно ограничить количество итераций
количеством вершин в графе - после чего сделать еще одну итерацию. До вершин, веса
которых обновились на последней итерации, не существует кратчайшего пути из-за цикла.

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


Ответ 2

А вообще я так прикинул, пусть есть отрицательные веса. Найдем ребро e с наименьшим
весом (то есть ребро с отрицательным весом максимального модуля). тогда w(e) = -n,
где n > 0. Сместим все веса на n. Запускаем алгоритм (он теперь отработает на корректных
данных) и вычитаем сколько "лишнего накручено". Или бред написал?)

Проверка графа на планарность

#алгоритм #графы

  Определение. Любой граф, гомеоморфный плоскому, называется планарным. Говорят,
что граф допускает плоскую укладку, если его можно изобразить как плоский. Например,
граф, показанный на рис.1, плоский.
  
  
  Рис. 1
  
  Существуют также и непланарные графы. На рис.2 показаны два таких графа: полный
пятивершинник и полный двудольный граф. Для них есть специальные обозначения: K5 и
K3,3 соответственно.
  
  
  Рис. 2
  
  Теорема. Граф является планарным, если не содержит в себе подграфов, гомеоморфных
K5 или K3,3.


Если ли у кого примеры реализации данной проверки? 
    

Ответы

Ответ 1

У меня это расчётная работа) Вот код:

import com.sun.org.apache.xpath.internal.SourceTree;        
import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class start{
    static List list;
    static int numOfForbidden5 = 0;
    static int numOfForbidden33 = 0;

    public static void main(String[] args) {
        clearList();
        try {
            menu();
        }
        catch(Exception ex){
            System.out.println("-\\_('_')_/-");
        }
    }

    private static void menu() throws Exception{
        boolean cheaker = true;
        while(cheaker){
            System.out.println("Choose one of the paragraphs:");
            System.out.println("1) Test 1");
            System.out.println("2) Test 2");
            System.out.println("3) Test 3");
            System.out.println("4) Test 4");
            System.out.println("5) Test 5");
            System.out.println("6) Test 6");
            System.out.println("7) Exit\n");
            Scanner vvod = new Scanner(System.in);
            int choose = vvod.nextInt();
            switch(choose){
                case 1:
                    helpForMenu(5, "test1.txt");
                    break;
                case 2:
                    helpForMenu(6, "test2.txt");
                    break;
                case 3:
                    helpForMenu(6, "test3.txt");
                    break;
                case 4:
                    helpForMenu(11, "test4.txt");
                    break;
                case 5:
                    helpForMenu(9, "test5.txt");
                    break;
                case 6:
                    helpForMenu(11, "test6.txt");
                    break;
                case 7:
                    System.out.println(" End of the program");
                    cheaker = false;
                    break;
                default:
                    System.out.println("-\\_('_')_/-");
                    break;
            }
        }
    }
    private static void helpForMenu(int n, String nameTest){
        clearList();
        try {
            fill(nameTest);
        }
        catch(Exception ex){
            System.out.println();
        }
        show();

        if(isPlanaren(n)){
            System.out.println("Граф изначально планарен!!!");
        }

        boolean oneShowing = true;
        while(!isPlanaren(n)){
            cheakPlanarnost5(n);
            cheakPlanarnost33(n);
            if(oneShowing){
                System.out.print("Фигурок типа 5 : " + numOfForbidden5 + "\n");
                System.out.print("Фигурок типа 3*3 : " + numOfForbidden33 + "\n");
                System.out.print("Минимальное кол-во рёбёр, при удалении которых
граф станет планарным : ");
                oneShowing = false;
            }
            String remove = RebroWithPartALotOfFigures();
            for(int i = 0; i < list.size(); i++){
                for(int j = 0; j < list.get(i).kolReber(); j++){
                    list.get(i).removeRebro(remove);
                }
            }
            for(int i = 0; i < list.size(); i++){
                list.get(i).resetAll();
            }
            System.out.print(remove + "  ");
        }
        System.out.println("\n");
    }

    private static void clearList(){
        list = new ArrayList<>();
        list.add(new IncedentList("0-oi element exist"));
        numOfForbidden5 = 0;
        numOfForbidden33 = 0;
        System.out.println();
    }

    private static void fill(String failname) throws Exception{
        Scanner reader = new Scanner(new File(failname));
        IncedentList incedentList = new IncedentList();

        while(reader.hasNext()){
            String value = reader.next();
            if(value.equals("-1")){
                list.add(incedentList);
                incedentList = new IncedentList();
                value = reader.next();
            }
            incedentList.setRebro(value);
        }
        reader.close();
    }
    private static void show(){
        System.out.println("Values of incident list");
        for(int i = 1; i < list.size(); i++){
            System.out.print(i + ") ");
            IncedentList help = list.get(i);
            for(int j = 0; j < help.kolReber(); j++){
                System.out.print(help.getRebro(j) + " ");
            }
            System.out.println();
        }
        System.out.println("");
    }

    private static void cheakPlanarnost5(int n){
        final int m = 5;
        Combinations.getDiapazon(m, n);
        int[] mass = null;

        while((mass = Combinations.generateCombinations(mass)) != null){
            int count = 0;
            for(int i = 0; i < mass.length; i++){
                for(int j = 0; (j < mass.length) && (j != i); j++){
                    for(int ii = 0; ii < list.get(mass[i]).kolReber(); ii++){
                        for(int jj = 0; jj < list.get(mass[j]).kolReber(); jj++){
                            if(IncedentList.compareRebra(list.get(mass[i]).getRebro(ii),
list.get(mass[j]).getRebro(jj))){
                                count++;
                            }
                        }
                    }
                }
            }
            if(count == 10){
                numOfForbidden5++;

                for(int i = 0; i < mass.length; i++){
                    for(int j = 0; (j < mass.length) && (j != i); j++){
                        for(int ii = 0; ii < list.get(mass[i]).kolReber(); ii++){
                            for(int jj = 0; jj < list.get(mass[j]).kolReber(); jj++){
                                if(IncedentList.compareRebra(list.get(mass[i]).getRebro(ii),
list.get(mass[j]).getRebro(jj))){
                                    list.get(mass[i]).incrementNumAsApartOfFigure(list.get(mass[i]).getRebro(ii));
                                }
                            }
                        }
                    }
                }
            }

        }
    }

    private static void cheakPlanarnost33(int n){
        int counter = 0;
        final int m = 3;
        Combinations.getDiapazon(m, n);
        int count = 0;
        boolean condition = true;

        int[] mass1 = null;
        while((mass1 = Combinations.generateCombinations(mass1)) != null){
            int[] mass2 = null;
            while((mass2 = Combinations.generateCombinations(mass2)) != null){
                if(!cheakComplience(mass1, mass2)){
                    continue;
                }
                count = 0;
                for(int i = 0; i < mass1.length; i++){
                    for(int j = 0; j < mass2.length; j++){
                        if(pereborReber(list.get(mass1[i]), list.get(mass2[j]))){
                            count++;
                        }
                    }
                }
                if(count == 9){
                    counter++;
                    condition = !condition;
                    if(condition){
                        for(int i = 0; i < mass1.length; i++){
                            for(int j = 0; j < mass2.length; j++){
                                for(int ii = 0; ii < list.get(mass1[i]).kolReber();
ii++){
                                    for(int jj = 0; jj < list.get(mass2[j]).kolReber();
jj++){
                                        if(IncedentList.compareRebra(list.get(mass1[i]).getRebro(ii),
list.get(mass2[j]).getRebro(jj))){
                                            list.get(mass1[i]).incrementNumAsApartOfFigure(list.get(mass1[i]).getRebro(ii));
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        numOfForbidden33 = counter/2;
    }

    private static boolean isPlanaren(int n){
        final int m = 3;
        Combinations.getDiapazon(m, n);
        int count = 0;
        boolean condition = true;

        int[] mass1 = null;
        while((mass1 = Combinations.generateCombinations(mass1)) != null){
            int[] mass2 = null;
            while((mass2 = Combinations.generateCombinations(mass2)) != null){
                if(!cheakComplience(mass1, mass2)){
                    continue;
                }
                count = 0;
                for(int i = 0; i < mass1.length; i++){
                    for(int j = 0; j < mass2.length; j++){
                        if(pereborReber(list.get(mass1[i]), list.get(mass2[j]))){
                            count++;
                        }
                    }
                }
                if(count == 9) {
                    return false;
                }
            }
        }

        final int m1 = 5;
        Combinations.getDiapazon(m1, n);
        int[] mass = null;

        while((mass = Combinations.generateCombinations(mass)) != null){
            int count1 = 0;
            for(int i = 0; i < mass.length; i++){
                for(int j = 0; (j < mass.length) && (j != i); j++){
                    for(int ii = 0; ii < list.get(mass[i]).kolReber(); ii++){
                        for(int jj = 0; jj < list.get(mass[j]).kolReber(); jj++){
                            if(IncedentList.compareRebra(list.get(mass[i]).getRebro(ii),
list.get(mass[j]).getRebro(jj))){
                                count1++;
                                //System.out.println("true");
                            }
                        }
                    }
                }
            }
            if(count1 == 10){
                return false;
            }
        }
        return true;
    }

    private static boolean cheakComplience(int mass1[], int[] mass2){
        for(int i = 0; i < mass1.length; i++){
            for(int j = 0; j < mass2.length; j++){
                if(mass1[i] == mass2[j]){
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean pereborReber(IncedentList l1, IncedentList l2){
        for(int j = 0; j < l1.kolReber(); j++){
            for(int jj = 0; jj < l2.kolReber(); jj++){
                if(IncedentList.compareRebra(l1.getRebro(j), l2.getRebro(jj))){
                    return true;
                }
            }
        }
        return false;
    }

    private static String RebroWithPartALotOfFigures(){
        int nomber = 0;
        String rebro = "";
        for(int i = 0; i < list.size(); i++){
            for(int j = 0; j < list.get(i).kolReber(); j++){
                if(list.get(i).getNumAsAPartOfFigure(list.get(i).getRebro(j)) > nomber){
                    nomber = list.get(i).getNumAsAPartOfFigure(list.get(i).getRebro(j));
                    rebro = list.get(i).getRebro(j);
                }
//                System.out.println(list.get(i).getNumAsAPartOfFigure(list.get(i).getRebro(j)));
            }
        }
        return rebro;
    }
}



import java.util.ArrayList;
import java.util.List;

public class IncedentList {
    private List rebra = new ArrayList();
    private List asAPartOfFigure = new ArrayList<>();

    public void incrementNumAsApartOfFigure(String str){
        for(int i = 0; i < rebra.size(); i++){
            if(compareRebra(str, rebra.get(i))){
                asAPartOfFigure.set(i, (asAPartOfFigure.get(i) + 1));
            }
        }
    }
    public int getNumAsAPartOfFigure(String str){
        for(int i = 0; i < rebra.size(); i++){
            if(compareRebra(str, rebra.get(i))){
                return asAPartOfFigure.get(i);
            }
        }
        return 0;
    }
    public void resetAll(){
        for(int i = 0; i < asAPartOfFigure.size(); i++){
            asAPartOfFigure.set(i, 0);
        }
    }

    public void removeRebro(String str){
        for(int i = 0; i < rebra.size(); i++){
            if(compareRebra(str, rebra.get(i))){
                rebra.remove(i);
                asAPartOfFigure.remove(i);
                break;
            }
        }
    }

    public IncedentList(String string){
        rebra.add(string);
        asAPartOfFigure.add(0);
    }
    public IncedentList(){};

    public int kolReber(){
        return rebra.size();
    }
    public String getRebro(int i){
        return rebra.get(i);
    }
    public void setRebro(String str){
        rebra.add(str);
        asAPartOfFigure.add(0);
    }

    public static boolean compareRebra(String s1, String s2){
        String half1s1 = "";
        String half2s1 = "";
        String half1s2 = "";
        String half2s2 = "";

        boolean cheaker1 = true;
        for(int i = 0; i < s1.length(); i++){
            if(cheaker1 && (s1.charAt(i) != '-')){
                half1s1 += s1.charAt(i);
            }
            if(s1.charAt(i) == '-'){
                cheaker1 = false;
                continue;
            }
            if(!cheaker1){
                half2s1 += s1.charAt(i);
            }
        }

        boolean cheaker2 = true;
        for(int i = 0; i < s2.length(); i++){
            if(cheaker2 && (s2.charAt(i) != '-')){
                half1s2 += s2.charAt(i);
            }
            if(s2.charAt(i) == '-'){
                cheaker2 = false;
                continue;
            }
            if(!cheaker2){
                half2s2 += s2.charAt(i);
            }
        }

        //System.out.println(half1s1 + " " + half2s1 + " \n" + half1s2 + " " + half2s2);

        if(half1s1.equals(half1s2) && half2s1.equals(half2s2)){
            return true;
        }

        if(half1s1.equals(half2s2) && half2s1.equals(half1s2)){
            return true;
        }
        return false;
    }
}


import java.util.Arrays;

class Combinations {
    private static int M = 3;
    private static int N = 5;

    public static void getDiapazon(int m, int n){
        M = m;
        N = n;
    }

    public static int[] generateCombinations(int[] arr) {
        if (arr == null) {
            arr = new int[M];
            for (int i = 0; i < M; i++) {
                arr[i] = i + 1;
            }
            return arr;
        }
        for (int i = M - 1; i >= 0; i--) {
            if (arr[i] < N - M + i + 1) {
                arr[i]++;
                for (int j = i; j < M - 1; j++)
                    arr[j + 1] = arr[j] + 1;
                return arr;
            }
        }
        return null;
    }
}


Вот погружаемые тесты:

1-2 1-3 1-4 1-5 -1
2-1 2-3 2-4 2-5 -1
3-1 3-2 3-4 3-5 -1
4-1 4-2 4-3 4-5 -1
5-1 5-2 5-3 5-4 -1

1-2 1-4 1-5 1-6 -1
2-1 2-3 2-4 -1
3-2 3-6 -1
4-1 4-2 4-5 -1
5-1 5-4 -1
6-1 6-3 -1

1-4 1-5 1-6 -1
2-4 2-5 2-6 -1
3-4 3-5 3-6 -1
4-1 4-2 4-3 -1
5-1 5-2 5-3 -1
6-1 6-2 6-3 -1


1-2 1-3 1-4 1-5 -1
2-1 2-3 2-4 2-5 -1
3-1 3-2 3-4 3-5 -1
4-1 4-2 4-3 4-5 -1
5-1 5-2 5-3 5-4 5-11 -1
6-9 6-10 6-11 -1
7-9 7-10 7-11 -1
8-9 8-10 8-11 -1
9-6 9-7 9-8 -1
10-6 10-7 10-8 -1
11-5 11-6 11-7 11-8 -1


1-4 1-5 1-6 -1
2-4 2-5 2-6 -1
3-4 3-5 3-6 3-7 3-8 3-9 -1
4-1 4-2 4-3 -1
5-1 5-2 5-3 -1
6-1 6-2 6-3 6-7 6-8 6-9 -1
7-3 7-6 7-8 7-9 -1
8-3 8-6 8-7 8-9 -1
9-3 9-6 9-7 9-8 -1



1-2 1-3 1-7 1-8 -1
2-1 2-3 2-7 2-8 -1
3-1 3-2 3-4 3-5 3-6 3-7 3-8 -1
4-3 4-5 4-6 4-7 -1
5-3 5-4 5-6 5-7 -1
6-3 6-4 6-5 6-7 6-9 6-10 6-11 -1
7-1 7-2 7-3 7-4 7-5 7-6 7-8 7-9 7-10 7-11 -1
8-1 8-2 8-3 8-7 8-9 8-10 8-11 -1
9-6 9-7 9-8 -1
10-6 10-7 10-8 -1
11-6 11-7 11-8 -1

Как найти наибольшую биклику, допуская неполное совпадение?

#алгоритм #графы #big_data

Дан двумерный массив булевых значений. Строки это аккаунты, столбцы – различные свойства
каждого аккаунта: «состоит в группе А», «совершал покупки» и т.п.

Надо найти максимальную биклику (полный двудольный граф) – т.е. тот наибольший набор
аккаунтов×свойств, где свойства true.

Задача NP-полная, и с её реализацией я кое-как в лоб разобрался. Но теперь два усложнения.


хочется сравнивать «нечётко»: допустить вхождение в биклику аккаунтов, у которых
недостаёт 1-2 (задаётся параметром нечеткости) свойств. Лучше посчитаем, как будто
они у них true, если это позволит включить их в наибольший набор. Неужели для каждой
найденной клики нужно зановой перебрать все данные, проверяя гипотезы о каждом свойства,
которое можно бы добавить? Подскажите алгоритм.
размер исследуемых наборов растёт. Может, вы прошли курс Machine Learning или прочие
BigData – посоветуйте методики поиска, альтернативные полному перебору? Я краем уха
слышал, есть такие, эффективно работающие на больших объёмах, пусть, дающие приблизительный
результат – объясните, пожалуйста, «на пальцах», как их можно применить к задаче?


Иллюстрации проблемы



Синие ячейки true, белые false. Нечёткая максимальная биклика обведена красным –
в каждой строке добавили по три «фантомных» ячейки (серые). Порядок строк/столбцов
не имеет значения. Максимальная биклика вовсе не обязательно будет сплошным прямоугольником,
это только для иллюстрации.



Например, здесь светло-синие ячейки были отброшены на этапе оптимизации, а оставшиеся
формируют две би-клики: строки (3,5) × столбцы (1,3,4,6) и (3,4,5)×(1,3). Однако, если
включить fuzziness на 2, то можно добавив в 4-й строке столбцы (4,6), а в строках (3,5)
столбец 5 – получить ещё большую биклику (3,4,5)×(1,3,4,5,6).
    

Ответы

Ответ 1

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

Например, в случае метрики "превышение true над false на всей биклике" (количество
заполненных против количества незаполненных клеток) и нечеткости 3 на примере с прямоугольником
максимумом окажется биклика из столбцов 1,2,6,7 прямоугольника и всех его строк, с
метрикой +8. При использовании метрики "всего истин" (число заполненных прямоугольников)
выделенный прямоугольник является максимальным. Таким образом, для задачи с нечеткостью
метрику нужно жестко задать, причем в зависимости от метрики может варьироваться сам
алгоритм выбора биклики. 

В общм случае (если метрика линейно зависит от количества строк и столбцов, участвующих
в биклике) подойдет жадный алгоритм захвата столбцов. Вначале сортируем столбцы по
количеству строк с данным атрибутом, установленным в true, потом включаем в множество
столбцов по очереди и смотрим изменение метрики. Для параметра нечеткости начальное
рассмотрение должно включать минимум (параметр нечеткости)+1 столбцов, иначе биклика
с нечеткостью захватит весь массив строк - этого нам явно не надо. После появления
набора столбцов добавляем по одному так, чтобы промежуточное значение метрики возрастало.
Количество строк в биклике будет убывать, так как не всегда у имеющихся строк будет
true в новом столбце, и какие-то из них выпадут по причине превышения false предела
нечеткости, в итоге либо добавим все, либо на каком-то этапе ни одной не получится
добавить. Проверяем, удастся ли выкинуть хоть один столбец чтобы метрика полезла вверх,
если да, выкидываем и продолжаем, пока изменение включения одного столбца не приведет
к увеличению метрики. Выдаем её как локальный максимум. Для очистки совести можно рассмотреть
наибольшую по метрике стартовую комбинацию из столбцов, не вошедших в найденную биклику
и точно так же её обработать. Если сойдется к этому же набору, его выдаем, иначе проверяем,
какая из найденных биклик больше, и если новая, проверяем ещё какую-нибудь комбинацию
на случай нескольких локальных максимумов, пока либо не придем к уже найденному локальному
максимуму, либо к меньшему, тогда возвращаем текущий локальный максимум как ответ.

Доказательство корректности алгоритма Куна для нахождения максимального паросочетания

#алгоритм #графы

Много где пишут, что его корректность очевидно следует из теоремы Бержа. Однако не
понятно, почему если увеличивающая цепь существует, алгоритм её найдет?    

Ответы

Ответ 1

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

Что лучше, выделить много памяти или много указателей на память?

#графы #память #указатели #cpp

Есть задача, нужно создать взвешенный граф в виде матрицы смежности. Нужен int-массив,
который будет одновременно означать и связь и ее "цену". Ну так вот, весь прикол в
том, что (в реале) не все элементы будут связаны друг с другом, а значит некоторый
объем памяти лежать без дела => умнее будет создать массив указателей, и те элементы
которые не используются будут = NULL, т.е. память занимать не будет...Но опять же я
занимаю много памяти под адреса. Что же лучше? Вообще, указатели же имеет "вес"?    

Ответы

Ответ 1

У Кнута в первом томе есть пример, как можно хранить такие матрицы, достаточно экономно
и с возможностью быстро индексировать.
Для хранения одного элемента используется структура
struct Node {
  int row; // это и следующее поле можно и исключить
  int col; // ниже будет описана замена.
  Node * next;
  Node * bottom;
  Data data; // а это одно (или несколько  полей), где собственно хранятся данные.
}

Поэтому получается, что на каждый элемент нужно два дополнительных указателя (8-16
байт) и, возможно, ещё 4-8-16 байт для ускорения работы (и возможно отладки).
Индексы также не обязательно хранить в int. Вполне может оказаться, что short может
оказаться достаточным.
Данные хранятся следующем виде. Каждая нода хранит ссылку на следующую ноду в строке
и следующую ноду в столбце. Если в данной строке/столбце больше правее/ниже нет нод,
то хранится ссылка на самую верхнюю/левую, то есть, зацикливаем.
Если данных 4 байта, и система 32 битная, то уже при заполнении менее, чем на треть,
уже будет выигрыш.
Как работать с такой матрицей
Заводим один вектор, который будет хранить указатели на списки строк. Что бы найти
какой-то элемент по индексу, нужно просто в векторе взять нужную строку, а потом просто
пройтись по элементам до нахождения нужного. Если нужно посчитать сумму по строке -
также не сложно - просто нужно получить строку и суммировать элементы. Нулевых нет,
но они не меняют картины.
Но если размерности матрицы большие ( к примеру 100000 на 100000), то есть смысл
просто сделать список всех существующий строк и столбцов.
Подсуммировав все, получаем такое
struct Node {
  int row; 
  int col; 
  Node * next;
  Node * bottom;
  Data data; // а это одно (или несколько  полей), где собственно хранятся данные.
}
std::list rows;
std::list cols;

// дальше алгоритмы словесные.
Node * get(int i, int j) {
   // Пройтись циклом по rows до нужной строки.
   // Если такой строки  нет, значит элемент нулевой
   // иначе проходим по строке (используя указатель next), ищем нужный элемент.
}

// Добавление элемента.
void add(Node * n) {

   // Находим нужную строку. Если строки в списке rows нет, нужно вставить.
   // добавляем этот элемент в эту строку.
   // если строка есть, то проходим циклом, что бы найти место вставки, 
   // поправляем два указателя
   // аналогичное проделываем с столбцами.
}
// удаление аналогично.

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


Ответ 2

Два стандартных представления связей в графе это 1) матрица, где элемент (i,j) указывает
есть ли связь между i-ой и j-ой вершинами и 2) массив списков, где i-ый элемент массива
содержит список связный с ним вершин. Если связи (i,j) в графе нет, то в i-ом списке
не будет элемента j.
Оба подхода имеют плюсы и минусы. Плюс второго подхода в экономии памяти.


Ответ 3

Это называется сильно разреженными матрицами, рассматривалось, к примеру, Кнутом.
Есть давнишняя книжка Писанецки строго на эту тему


Ответ 4

Просто создайте указатель на указатель ;) **

Неориентированный граф: оптимальное создание

#графы #java #алгоритм

Здравствуйте! Всем добрый день! Подскажите, пожалуйста, каким образом оптимальнее
создавать неориентированный граф, столько разных структур существует в Java:


Можно в виде матрицы смежности, создав просто 2-мерный массив (что не очень оптимально,
так что сразу был отброшен)
Можно переделать тип Iterator в Bag, сделав список смежных вершин
(тогда это будет выглядеть примерно так: http://algs4.cs.princeton.edu/13stacks/Bag.java.html,
неплохой вариант, в принципе)
Можно сделать все это с помощью Map и TreeMap (видел один пример, понравился по компактности,
но не знаю, будет ли это приемлемо, или же нет)
Также вот увидел вариант с помощью Hashmap


Вот в общем, такие у меня варианты есть. Я не силен в Java, еще только начинаю в
нем разбираться. Подскажите, каким образом решить данный вопрос. Спасибо большое заранее!
    

Ответы

Ответ 1

Конкретный язык прграммирования тут ни при чем! Видимо, если Вы не сильны в Java,
то пока не сильны и вообще в алгоритмах и структурах данных. Поэтому рекомендую не
думать на данном этапе о сверхэффективности Вашего кода.
Используйте классические структуры данных для представления графа: матрицу смежности
или списки смежности (это 1й и 2й пункты из Вашего вопроса). Возьмите хорошую книгу
и реализуйте граф так, как там описано внутри класса граф (в зоне private).
Добавьте public-интерфейс, который нужен для конкретной задачи.
Реализуйте по книге алгоритмы обхода графа. Запрогрпмируйте какую-нибудь олимпиадную
задачу с помощью Вашего класса. Если Вы сделаете обе реализации, сможете сравнить производительность.
Успехов!

Задача по поиску кратчайшего пути

Есть поле <30x30. Мы можем по этому полю проводить линии по вертикали и горизонтали, которые могут пересекаться.

Пример возможного расположения линий



Правила следующие:


Каждая клетка имеет тип 0, 1 или 2. Каждая линия тоже имеет тип 0, 1 или 2. 
Если линия проходит через свой тип, то штраф равен 0. Если через соседний (0 чере
1, 1 через 2 или наоборот), то штраф равен 1. Если через дальний (0 через 2 или наоборот), то штраф равен 5. 
Начисляется дополнительный штраф за пересечение линий равный количеству линий умноженому на константу N, при этом одним пересечением считается одна общая клетка.


На вход дается: константа N, поле с указанием типов клеток, параметры каждой линий с указанием начала, конца и типа.

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

Время работы: вообще меня устроит и 5 минут, но лучше было бы уложиться в несколько секунд (хотя бы для полей 10x10).

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

Ответы

Ответ 1

Если я правильно понимаю, вам нужно оптимизировать путь для каждой из линий. Учте
что вариантов проведения каждой линии будет (для n>2, где n это ребро поля) 4^((n-2)^2
+ 4*3^(n-2) + 8. Таким образом, я бы лично искал не "лучший путь" - выдаюший кратчайшее из возможных "растояний", так как поиск такого пути может потребовать ОЧЕНЬ МНОГО времени ,а "хороший путь" - такой, какой мы можем найти за ограниченное наперед время, но который не является обязательно "лучшим из возможных".

Пожалуй тут я вижу два подхода, что то вроде шахматной алфа-беты, правда тут прийдется поломать голову над функцией оценки. Либо, что нибудь типа муравьиного алгоритма.


Ответ 2

А почему бы не воспользоваться волновым алгоритмом? Только в классической виде необходим
найти расстояние, Вам же надо минимизировать штраф. Например, представим поле 5х5 с начальными данными для линии (2,3), (4,1), 1. Получится следующая картина:


Ответ 3

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


На этом пока всё.


Ответ 4

Ваша задача состоит из двух:


Аккуратно по заданному полю построить взвешенный граф. Это банальная вычислительная комбинаторика.
Примененить алгоритм Дейкстры.


Ответ 5

Искать пути можно алгоритмом Дейкстры, но сначала для каждой линии нужно построит
граф особого вида, назовем его граф Д. В узлах графа Д будут либо отдельные клетки с
штрафами больше 0, либо множества сопряженных "своих" клеток со штрафами 0. Множеств
"своих" клеток должны включать клетки в каждую из которох можно попасть не проходя через "чужие", тут надо следить чтобы в эти области не попадали диагональные клетки. Путь в штрафной узел будет равен штрафу ее клетки, путь в нулевые узлы будет равен собственно 0. Штрафы естественно считаются относительно целевой линии.

После того как Дейкстра отработает, нужно дополнительно в каждом "своем" узле, вошедшем в путь, строить путь от входа до выхода. Это не сложно сделать волновым алгоритмом. 

После того как пути построены нужно искать пересечения и выполнять пересчет начина
с перестроения графа Д. Перестроение будет заключаться в увеличении штрафов в "чужих" узлах и разбиении "своих" в соответсвии с пересечениями.

Тут мы подходим к главной проблеме - какие линии пересчитывать!

Забудем Дейкстру. Будем применять вариацию минимакса алгоритм альфа-бета отсечени
(подробнее или здесь). Для альфа-бета отсечения (АБС) требуется строить дерево состояний
Эти состояния будут представлены графами Д для всех линий сразу. Каждое ветвление дерева АБС это выбор очередного узла для одной из линий. На каждом ветвлении АБС граф Д нужно перестраивать и пересчитывать штрафы.

Для АБС очень важны эвристики, вот несколько пришедших мне в голову:


В случае трех линий 0, 1 и 2, линия 1 имеет то преимущество что ее штраф за чужи
клетки всегда равен 1. Поэтому при выборе линии для пересчета нужно выбирать линию 1 так как вероятность увеличения штрафа ниже.
Тоже самое с другого боку, можно подсчитывать количество клеток каждого типа и таким образом получать вероятность увеличения штрафа при пересчете линии.
При построении пути, если встречается штрафной узел, можно подсматривать в "чужой" граф Д для :


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


Ответ 6

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

Поиск кратчайшего пути в 0-1 графе

Здравствуйте. В статье про bfs сказано, что Нахождение кратчайшего пути в 0-1-графе (т.е. графе взвешенном, но с весами равными только 0 либо 1): достаточно немного модифицировать поиск в ширину: если текущее ребро нулевого веса, и происходит улучшение расстояния до какой-то вершины, то эту вершину добавляем не в конец, а в начало очереди. Как проверить улучшение расстояние до какой-то вершины за рациональную асимптотику, и как дальше с этим работать, ведь та вершина, расстояние до которой улучшилось могла быть "подожжена" чуть ли не в самом начале, а тогда придется проходить все заново. UPDATE Пытался пойти путём другой статьи. Возникает вопрос: если есть ребра из вершины 1-2(вес 1) и 1-3(вес 0) и 3-2(вес 0) и 2-1(вес 0) то алгоритм от вершины 1 поставит dist2 = 1; dist[3] = 0; а от 3 к 2 перейти не сможет, т.к. она использована. Что делать?

Ответ

В этой модификации алгоритма не нужно использовать массив used. Для каждого ребра нужно проверять не нашелся ли путь лучше, чем тот, который уже найден для конечной вершины ребра. И если новый путь лучше, добавлять вершину в начало/конец очереди в зависимости от стоимости ребра. Нетрудно показать, что в любой момент времени в очереди могут находиться только вершины, расстояние до которых равно x и, возможно, x+1. Причем все вершины с расстоянием x идут раньше всех вершин с расстоянием x+1. Из этого следует, что любая вершина попадет в очередь не более двух раз. Доказательство: если при первом попадании в очередь, в очереди не осталось вершин с меньшим расстоянием, то добавленная вершина еще раз в очередь не попадет, так как не осталось вершин, способных срелаксировать расстояние до нее. Если же в очереди еще остались вершины с расстоянием меньшим на 1, то они смогут улучшить расстояние до добавляемой только 1 раз и тогда она попадет в очередь второй раз. Таким образом сохранится асимптотика O(N + M).