heuristic suite

Эвристический люкс

Важное примечание

Проект больше не находится под техническим обслуживанием. Пожалуйста, посетите LINQ до* для последней версии.

Обзор

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

Внедренные алгоритмы:

• A*
• Итеративное углубление A* (IDA*)
• Лучший первый поиск
• Рекурсивный лучший первый поиск (RBFS)

Реализация полностью ориентирована на объект и получает преимущества встроенного механизма сравнения .NET Framework, такого как Icomparer (T) и iequalityComperer (T), чтобы создать большую совместимость со стандартной .NET и всей экосистемой .NET. Исходный код может быть легко доведен на другие платформы, такие как Unity и Xamarin.

Решение головоломки с помощью алгоритма

Чтобы применить алгоритм к головоломке, необходимы следующие реализации:

1. Определение шага Тип, который определяет шаг головоломки, потребуется для реализации интерфейса ISTEP (TKEY). Key свойство служит двум целям:

   • Чтобы проверить, эквивалентны ли два шага. Например: та же позиция на доске.
   • Чтобы сравнить два шага, чтобы определить, что имеет лучшую оценку. Например: расстояние между позицией A и целью, и расстояние между позицией B и целью, тем ближе оценивается лучше.

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

   • Icomplable (TKEY) реализация.
   • Индивидуальный экземпляр Icomparer (TKEY).
   • Явно заданная функция h (n) , где параметр n является Key .

3. Доступные шаги от текущего шага следующего шага могут быть предоставлены путем реализации интерфейса INextStepFactory(TKey, TStep) или предоставления делегата NextStepFactory .

После чего алгоритм может быть запущен путем вызывания метода FindSolution со from и goal в качестве параметров. Если решение существует, каждый из этапов может быть получен путем вызова метода Enumerate . Шаги могут быть Reverse D до начала перечисления.

Эвристический сравнитель и дискретный эвристический сравнитель

Проект предоставляет HeuristicComparer и DiscreteHeuristicComparer сценариям сравнения разных шагов.

• Если Key свойство можно напрямую сравнить друг с другом без явной функции h (n) , по умолчанию, DiscreteHeuristicComparer будет использоваться для более быстрого сравнения шага.
• Если функция h (n) явно необходима для сравнения каждого из шагов, HeuristicComparer будет использоваться для выполнения традиционной оценки f (n) = g (n) + h (n) .

Предпочтение эвристической функции

HeuristicFunctionPreference перечисления позволяет пользователям изменять баланс оценки F (n) = g (n) + h (n) . Когда два этапа оцениваются в одном балле, перечисление решает, какая функция, G (n) или H (n) , будет рассмотрено первым. Измененный баланс может повлиять на поведение эвристического алгоритма.

Примеры

• Обнаружение пути (Algorithmforce.example.pathfinding)

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

• 8-Puzle (algorithmforce.example.eightpuzzzle)

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

• Монеты переворачивают головоломку (algorithmforce.example.coinsflipping)

  Этот пример демонстрирует, как ИГ ИИ решает монеты, переворачивая головоломку. В головоломке можно перевернуть только пару смежных монет. Все десять монет, которые являются головой, являются целью. Загадка вдохновлена ​​Brilliant.org.

В будущем будет добавлено больше примеров.

Платформа

Проект в настоящее время нацелен на .NET Core и .NET Framework 4.5 или выше.