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

Question

Проблема фоне

я в настоящее время разрабатывает рамки Ant Colony System алгоритмов. Я думал, что начну, попробовав их по первой проблеме, к которой они были применены: «Проблема с продавцом» (TSP). Я буду использовать C# для задачи.

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

Вопрос

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

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

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

UPDATE

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

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

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

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

Проблема разъяснения

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

Что касается рассматриваемой проблемы:

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

детали Исследование статья: Ant Colony System article

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

Я больше беспокоюсь о времени запуска (скорость), чем память.

Answer 1

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

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

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

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

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

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

Answer 2

Поскольку у вас есть полный график, я бы подумал, что лучшим представлением будет 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 (если у вас есть много информации для хранения о каждом узле) на основе индекса от этого узла на графике.