Наиболее эффективная реализация для полного неориентированного графа

Проблемный фон

В настоящее время я занимаюсь разработкой основы алгоритмов Ant Colony System. Я решил начать с первой проблемы, к которой они были применены: Задача коммивояжера (TSP). Я буду использовать C# для этой задачи.

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

Вопрос

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

Я могу предоставить дополнительную информацию, если требуется.

Спасибо за ваше время.

ОБНОВИТЬ

Весовое уточнение. Каждое ребро будет иметь два связанных с ними значения:

  1. расстояние между двумя городами ( d(i,j) = d(j,i) одинаковое расстояние в обоих направлениях)
  2. количество феромона откладывается муравьями на этом конкретном краю

Операции Небольшое резюме операций, которые я буду делать на графике:

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

Разъяснение проблемы

Алгоритмы Ant Colony Optimization могут "решить" TSP, поскольку именно там они были впервые применены. Я говорю "решить", потому что они являются частью семейства алгоритмов, называемых оптимизациями метаэвристики, поэтому они никогда не гарантируют возврата оптимального решения.

Относительно проблемы под рукой:

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

Подробности исследовательской статьи: статья о Ant Colony System

Соображения эффективности

Меня больше беспокоит время выполнения (скорость), чем память.

Источник

2 ответа

Решение

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

Вывод, я думаю, заключается в следующем: если вам часто приходится отвечать на вопрос: "Мне нужно знать расстояние или уровень феромона границы между точно узлом i и узлом j", то вам, вероятно, нужна матричная форма., поскольку на этот вопрос можно ответить за O(1) раз.

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

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

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

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

Источник

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

public class Edge
{
//change types as appropriate
  public int Distance {get;set;}
  public int Pheromone {get;set;}
}


int numNodes;
Edge[,] graph = new Edge[numNodes,numNodes];
for(int i = 0; i < numNodes; i++)
{
  for(int j = 0; j < numNodes; j++)
  {
    graph[i][j] = new Edge();
    //initialize Edge
  }
}

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

Источник
Другие вопросы по тегам