Граф Тур с поиском равномерной стоимости в Java - PullRequest
Новая
       30

Граф Тур с поиском равномерной стоимости в Java

2 голосов
/ 24 апреля 2010

Я новичок в этом сайте, так что, надеюсь, вы, ребята, не против помочь начинающему.

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

http://img339.imageshack.us/img339/8907/graphr.jpg

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

Я читал, и я думаю, что то, что я ищу, это поиск A * с постоянной эвристической величиной, который я считаю поиском с равномерной стоимостью. У меня возникают проблемы, когда я не могу понять, как применить это в Java.

В основном вот что у меня есть:

Вершинный класс - 

ArrayList<Edge> adjacencies;
String name;
int costToThis;

Край класса - 

final Vertex target;
public final int weight;

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

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

Вот то, что я имею до сих пор, что довольно далеко от цели: 

public static void visitNode(Vertex vertex) {
      ArrayList<Edge> firstEdges = vertex.getAdjacencies();
      for(Edge e : firstEdges) {
         e.target.costToThis = e.weight + vertex.costToThis;
         queue.add(e.target);
      }
      Vertex next = queue.remove();
      visitNode(next);
   }

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

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

Помощь очень ценится! Джош

РЕДАКТИРОВАТЬ: Я должен отметить, что ранее посещенные пути могут быть посещены снова. В случае, если я предоставил это, это не выгодно, но может быть случай, когда посещение ранее посещенного узла, чтобы добраться до другого узла, приведет к более короткому пути (я думаю). Так что я не могу просто сделать это на основе уже посещенных узлов (это была моя первая мысль)

1 Ответ

1 голос
/ 24 апреля 2010

Два комментария:

1) Когда вы устанавливаете costToThis вершины, вы переопределяете существующее значение, и это влияет на все пути в очереди, поскольку вершина является общей для многих путей. Я бы не стал хранить стоимость в составе Vertex. Вместо этого я бы определил класс Path, который содержит общую стоимость пути плюс список узлов, составляющих его.

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

Надеюсь, это поможет ...

...