Структура данных для представления графика - PullRequest
0 голосов
/ 27 марта 2019

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

graph

Мой вопрос такой, поскольку это, вероятно, оченьОбщая проблема, есть ли алгоритм или уже созданная структура данных, чтобы представить это?Язык программирования не важен (хотя я бы предпочел java).

Ответы [ 3 ]

1 голос
/ 27 марта 2019

То, что вы ищете, на самом деле является генератором всех перестановок .Если вы сохраняете один город в качестве первого (Лондон, на вашей диаграмме), то вам нужно сгенерировать все перестановки в списке всех оставшихся узлов (Варшава, Лодзь, Берлин).

Часто такоеАлгоритм выполняется рекурсивно, зацикливаясь на всех элементах, извлекая его и делая это рекурсивно для остальных элементов.Часто для этого используются библиотеки, например, itertools.permutations в Python.

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

{ a: { b: { c: d,
            d: c },
       c: { b: d,
            d, b },
       d: { b: c,
            c: b } } }
1 голос
/ 27 марта 2019

Ваша проблема кажется очень близкой к проблеме коммивояжера , классика среди классиков.
Как вы и сделали, интуитивно, граф, который будет представлять все возможные решения, действительно является деревом (пути от корня до любого его листа должны представлять решение).
Оттуда вы можете задать себе несколько вопросов:

  • Является ли первый город, в котором я побываю, важной информацией или важен только порядок? Например, Лондон-Варшава-Берлин-Лидз эквивалентен Варшаве-Берлин-Лидз-Лондон?
    Обычно мы считаем, что эти решения эквивалентны решению TSP, но это может быть не так.

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

С учетом этих двух моментов мы можем подумать о том, как создать такое дерево. Хорошая стратегия работы с деревьями - думать рекурсивно.
У нас есть частичное решение, означающее k первые города. Затем следующим возможным городом может быть любой из оставшихся n-k городов. Это дает следующий псевдокод.

get_all_permutations(TreeNode node, Set<int>not_visited){
    for (city in not_visited){
        new_set = copy(not_visited);
        new_set.remove(city);
        new_node = new TreeNode();
        new_node.city = city;
        node.add_child(new_node);
        get_all_permutations(new_node, new_set);
    }
}

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

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

1 голос
/ 27 марта 2019

Это дерево плохое.В нем есть избыточные данные.Например, соединение между узлами 2 и 4 происходит три раза в дереве.Вам нужна «структура», которая автоматически дает решение вашей проблемы, чтобы вам было легче, но это не так, как работает решение проблем.Входные данные - это один набор данных, выходные данные - это другой набор данных, и они могут выглядеть одинаково, но они также могут быть совершенно разными.

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...