Плеер Маркировка , Оптимальный Маркировки, Используя График


Я задал этот проблема за проблемой, и я решил поделиться здесь мое решение, чтобы проверить код:

Вот условие задачи:

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

Давайте предположим, что игрок в одной вершине может только пометить другого игрока, если существует ребро между ними. Так на примере графа, игрок на В можете пометить противника на А, Б и с. Игрок на Д может пометить противника на С и Д. Каждое ребро графа должно быть покрыто.

Example graph

Ваша цель-обеспечить минимальное количество игроков, чтобы пометить всех противников, представленный график. Так, например, одним из решений этой графе может быть [1, 1, 1, 1] Что означает, у вас есть игроки, дислоцированных на А, Б, С, Д , на которой отмечены все позиции, в общей сложности 4 игроков. Однако, это не будет самым оптимальным. Решение, как [0, 1, 0, 1] это может быть лучшим решением, потому что два игрока на Б и Д представлен 1 можно отметить все другие позиции комфортно. Однако опять же это не может быть наиболее оптимальный (т. е. минимальный развертывания отметить всех игроков).

Для решения этой задачи нам понадобится функция, которая принимает график, который представляет позиции всех игроков на футбольном поле и возвращает наиболее оптимальное обозначение стратегии в форме [1, 0, X, X, ...] где 1 представляют вершины, где бы вы разместили Ваш плеер.

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

[[0, 1, 1, 0], 
 [1, 0, 1, 0], 
 [1, 1, 0, 1], 
 [0, 0, 1, 0]]

Чтобы решить эту проблему, я думал о всех алгоритмов, связанных с графами, как: глубину, поиск в ширину и Дейкстры кратчайший путь. Однако, ни один из них не подходит для этой задачи.

Поэтому я решил пойти с простой подход, используя петли.

1. Чтобы решить эту проблему, мы будем иметь функцию, которая возвращает true если набор отметин-это правильное решение для график игроков.

Вот мое решение :

def valid_markings(solution, graph):
    marked = [] # the list will contain an edge if it's marked
    for idx, i in enumerate(solution):
    # in this loop we are going to check for marked item
        if  i == 1:
            # add element as marked by him
            for edx_j, j in enumerate(graph[i]):
                if graph[idx][edx_j] == 1:
                    marked.append(edx_j)
    return list(set(marked)) == list(range(0, len(graph)))

В конце концов, мы будем сравнивать маркированный список, с перечнем всех элементов, чтобы проверить, если все элементы были промаркированы, так например:

Если graph1 = [[0, 1, 0, 0, 1], [1, 0, 1, 0, 0], [0, 1, 0, 1, 1], [0, 0, 1, 0, 0], [1, 0, 1, 0, 0]], тогда valid_markings([1, 0, 1, 0], graph1) вернется false а valid_markings([1, 0, 1, 0, 1], graph1) вернется true

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

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

def optimal_markings(input_graph):
    results_counts = []
    for combination in itertools.product([1, 0], repeat=len(input_graph)):
        results = combination
        if valid_markings(results, input_graph):
            results_counts.append((results.count(1), results))
    optimal_required = sorted(results_counts, key = lambda x : x[0] )[0][0]
    optimal_marking = list(filter( lambda x : x[0] == optimal_required, results_counts))
    return optimal_marking[0]

Поэтому одним из оптимальных разметки

optimal_markings(graph1) это (2, (0, 1, 1, 0, 0)).

Проблемы:

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

Спасибо.



Комментарии
1 ответ

Совершенствование существующих

Давайте попробуем улучшить valid_markings.

Имена

Меня очень смущает valid_markings пока я не понял i и j где не Индекс циклы, но соответствующее значение. В зависимости от контекста именования переменных ì не может быть большое дело, но вложенные циклы с enumerateэто, вероятно, лучше избегать. Я предлагаю использовать sol_elt для элементов решения и _ на значение, которое не используется (_ - обычное имя в Python для выбрасывать значений).

Избежать ООН-необходимые

В 0 значение в качестве первого аргумента в диапазоне не нужна, вы можете избавиться от него.

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

Наконец, потому что вы рассматриваете только 0 и 1, можно написать if val == 1 как if val.

Вы бы что-то вроде:

def valid_markings(solution, graph):
marked = set() # the list will contain an edge if it's marked
for i, sol_elt in enumerate(solution):
# in this loop we are going to check for marked item
if sol_elt:
# add element as marked by him
for j, _ in enumerate(graph[sol_elt]):
if graph[i][j]:
marked.add(j)
return list(marked) == list(range(len(graph)))

Упростить логику

Вместо использования enumerate чтобы получить индекс и перебрать оба solution и graphвы могли бы использовать zip.

Кроме того, вместо конвертации marked в список и сравнивать с [0, 1, 2 и др.], Можно просто считать его элементов.

Вы бы что-то вроде:

def valid_markings(solution, graph):
marked = set() # the list will contain an edge if it's marked
for sol_elt, line in zip(solution, graph):
# in this loop we are going to check for marked item
if sol_elt:
# add element as marked by him
for j, _ in enumerate(line):
if line[j]:
marked.add(j)
return len(marked) == len(graph)

Итак, попробуем улучшить optimal_markings.

Бесполезно переменной

combinations и results кажется излишним.

Упростить логику

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

Это:

sorted_results = sorted(results_counts, key = lambda x : x[0])
optimal_required = sorted_results[0][0]
optimal_marking = list(filter( lambda x : x[0] == optimal_required, results_counts))
return optimal_marking[0]

становится это:

sorted_results = sorted(results_counts, key = lambda x : x[0])
return sorted_results[0]

Другой способ, чтобы получить лучший результат

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

def optimal_markings(input_graph):
l = len(input_graph)
marking, score = [1] * l, l
for comb in itertools.product([1, 0], repeat=l):
comb_score = comb.count(1)
if comb_score < score and valid_markings(comb, input_graph):
marking, score = comb, comb_score
return (score, marking)

Еще один способ, чтобы получить лучшие результаты

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

def optimal_markings(input_graph):
l = len(input_graph)
candidates = [[1] * l]
while True:
new_candidates = []
for cand in candidates:
for i, val in enumerate(cand):
if val:
new_cand = list(cand)
new_cand[i] = 0
if valid_markings(new_cand, input_graph):
new_candidates.append(new_cand)
if new_candidates:
candidates = new_candidates
else:
return candidates[0]

Другой алгоритм

Я думал, что к тому времени, я пишу это, я бы нашел имя алгоритма, чтобы решить вашу проблему, но я еще не. :(

Проблемы реальной жизни и пример данных

В вашем описании, вы говорите


Так на примере графа, игрок на можете пометить противника в, B и C

какой смысл от того, что я знаю о баскетболе.

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

Я думаю, вы могли бы исправить это в ваших примерах матрица или как частный случай в вашем случае (спойлер: он ломает свои тесты в любом случае).

4
ответ дан 24 марта 2018 в 11:03 Источник Поделиться