Как мне создать график из этой структуры данных? - PullRequest
Новая
       20

Как мне создать график из этой структуры данных?

1 голос
/ 31 декабря 2010

Я взял эту структуру данных из этого A * учебника : 

public interface IHasNeighbours<N>
{
    IEnumerable<N> Neighbours { get; }
}

public class Path<TNode> : IEnumerable<TNode>
{
    public TNode LastStep { get; private set; }
    public Path<TNode> PreviousSteps { get; private set; }
    public double TotalCost { get; private set; }
    private Path(TNode lastStep, Path<TNode> previousSteps, double totalCost)
    {
        LastStep = lastStep;
        PreviousSteps = previousSteps;
        TotalCost = totalCost;
    }
    public Path(TNode start) : this(start, null, 0) { }
    public Path<TNode> AddStep(TNode step, double stepCost)
    {
        return new Path<TNode>(step, this, TotalCost + stepCost);
    }
    public IEnumerator<TNode> GetEnumerator()
    {
        for (Path<TNode> p = this; p != null; p = p.PreviousSteps)
            yield return p.LastStep;
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

}

Я не знаю, как создать простой график с помощью.

Как мнедобавьте что-то вроде следующего неориентированного графа, используя C #:

alt text

В основном я хотел бы знать, как соединить узлы.У меня есть свои собственные структуры данных, которые я уже могу определить, соседи и расстояние.Теперь я хотел бы преобразовать это в эту опубликованную структуру данных, чтобы я мог запустить ее с помощью алгоритма AStar.

Я искал что-то более похожее на: 

 Path<EdgeNode> startGraphNode = new Path<EdgeNode>(tempStartNode);
 startGraphNode.AddNeighbor(someOtherNode, distance);

Ответы [ 2 ]

0 голосов
/ 31 декабря 2010

но я понятия не имею, как использовать этот, созданный для A *.

Вот в чем дело. Нет «этого, созданного для А *».Класс Path является generic , как он говорит:

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

Вы можете использовать любой класс Node, какой пожелаете, при условии, что он одинаков для каждого узла в графе.Код не заботится о том, как работает ваш класс Node, потому что он не использует интерфейс Node .Все, что он делает - это сохраняет Paths, то есть последовательности (ссылки на) Node s.(В частности, он делает это путем создания навязчивого связанного списка, но он также добавляет стоимость пути по мере продвижения.) Вы создаете новый Path и используете AddStep, чтобы добавить Node s к Пути, итогда вы можете использовать Path как IEnumerable.

. Вы можете продолжать использовать Node s в обычном режиме.Все, что вам нужно, это убедиться, что ваши Узлы имеют какой-то способ представления «стоимости» ребра на графике, чтобы вы могли передать эту информацию в AddStep.

0 голосов
/ 31 декабря 2010

Это потому, что вы используете неправильную структуру для представления графика.A * (и путь здесь) используются, чтобы найти путь между двумя узлами в графе.Путь изначально направлен и может быть сведен к одной линии.Например, на приведенном выше графике единственный возможный путь, который будет проходить через все узлы, начинается с 3 и заканчивается на 2 (обратите внимание, что последний будет добавлен дважды на вашем пути, независимо от того, погода это или нет, во многом это зависит от вашей проблемыпытаясь решить.

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

Самая базовая форма графика - это в основномузел со списком членов соседних узлов. Затем вы можете попробовать на нем A *. Определить начальный узел и конечный узел и найти путь между ними

...