Проблема фонеНаиболее эффективная реализация для полного неориентированного графа
я в настоящее время разрабатывает рамки Ant Colony System алгоритмов. Я думал, что начну, попробовав их по первой проблеме, к которой они были применены: «Проблема с продавцом» (TSP). Я буду использовать C# для задачи.
Все экземпляры TSP будут состоять из полного неориентированного графика с двумя различными весами, связанными с каждым ребром.
Вопрос
До сих пор я использовал только смежности список представлений, но я читал, что они рекомендуются только для разреженных графов. Поскольку я не очень осведомлен о людях, когда речь заходит о структурах данных, мне было интересно, что будет самым эффективным способом реализации неориентированного полного графика?
При необходимости я могу предоставить дополнительную информацию.
Спасибо за ваше время.
UPDATE
Вес осветление. Каждое ребро будет иметь два значения, связанные с ними:
- расстояние между двумя городами (д (I, J) = D (J, I) одинаковое расстояние в обоих направлениях)
- количество феромонов, сданный на хранение муравьев на этом конкретном крае
Операции. Небольшой обзор операций я буду делать на графике:
- для каждого узла, муравей на этом конкретном узле будет перебирать значения, связанные со всеми инциденту кромками
Проблема разъяснения
Алгоритмы оптимизации колоний колоколов могут «решить» TSP, поскольку здесь они были впервые применены. Я говорю «решаю», потому что они являются частью семейства алгоритмов, называемых оптимизацией метаэвристики, поэтому они никогда не гарантируют возврат оптимального решения.
Что касается рассматриваемой проблемы:
- муравьи будут знать, как закончить тур, потому что каждый муравей будет иметь память.
- каждый раз, когда муравей посещает город, он будет хранить этот город в своей памяти.
- каждый раз, когда муравей посещает новый город, он будет искать в своей памяти и выбирать исходящий край, только если этот край не приведет его к уже посещенному городу.
- , когда больше нет краев, муравей может выбрать, что он совершил экскурсию; на этом этапе мы можем восстановить тур, созданный муравья, возвращаясь через его память.
детали Исследование статья: Ant Colony System article
соображения эффективности
Я больше беспокоюсь о времени запуска (скорость), чем память.
Нет единого «наиболее эффективного» представления. Эффективность зависит от множества операций, которые вы собираетесь предоставить, и как часто они будут вызываться. – Vlad
Если у вас есть два веса, связанных с ребрами, то у вас есть ориентированный граф, а не неориентированный (при условии, что веса для разных направлений, в противном случае это действительно один (хотя и сложный) вес) – Attila
Извините, если указанная терминология неверна: одно значение представляет расстояния между двумя городами, второе значение представляет количество феромонов, осажденных муравьями на конкретном крае.Это все еще не направлено. – Morat